Vaucanson  1.4.1
implementation/semiring/tropical_semiring.hxx
1 // tropical_semiring.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2011 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HXX
18 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HXX
19 # include <vaucanson/config/system.hh>
20 # include <vaucanson/algebra/implementation/semiring/tropical_semiring.hh>
21 # include <vaucanson/misc/random.hh>
22 # include <vaucanson/misc/limits.hh>
23 
24 namespace vcsn {
25 
26  namespace algebra {
27 
28  /*---------------.
29  | Identity value |
30  `---------------*/
31  template<class TropicalKind, typename T>
32  T identity_value(SELECTOR(algebra::TropicalSemiring<TropicalKind>), SELECTOR(T))
33  {
34  return T(0);
35  }
36 
37  template<class TropicalKind, typename T>
38  bool show_identity_value(SELECTOR(algebra::TropicalSemiring<TropicalKind>),
39  SELECTOR(T))
40  {
41  // Always show the identity weights for tropical semirings,
42  // otherwise reading the automaton is too confusing.
43  return true;
44  }
45 
46  template<typename T>
47  T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(T))
48  {
49  return misc::limits<T>::min();
50  }
51 
52  template<>
53  inline
54  float zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(float))
55  {
56  return -misc::limits<float>::infinity();
57  }
58 
59  template<>
60  inline
61  double zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(double))
62  {
63  return -misc::limits<double>::infinity();
64  }
65 
66  template<typename T>
67  T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(T))
68  {
69  return misc::limits<T>::max();
70  }
71 
72  template<>
73  inline
74  float zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(float))
75  {
76  return misc::limits<float>::infinity();
77  }
78 
79  template<>
80  inline
81  double zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(double))
82  {
83  return misc::limits<double>::infinity();
84  }
85 
86  /*------------.
87  | op_contains |
88  `------------*/
89  template<class TropicalKind, typename T>
90  bool op_contains(const algebra::TropicalSemiring<TropicalKind>&, T c)
91  {
92  return true;
93  }
94 
95  /*--------------------.
96  | Multiplication is + |
97  `--------------------*/
98  template<class TropicalKind, typename T, typename U>
99  void op_in_mul(const algebra::TropicalSemiring<TropicalKind>&,
100  T& dst, U arg)
101  {
102  if ((dst == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
103  SELECT(T))) ||
104  (arg == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
105  SELECT(U))))
106  dst = zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>), SELECT(T));
107  else
108  dst += arg;
109  }
110 
111  template<class TropicalKind, typename T, typename U>
112  T op_mul(const algebra::TropicalSemiring<TropicalKind>&, T a, U b)
113  {
114  if ((a == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
115  SELECT(T))) ||
116  (b == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
117  SELECT(U))))
118  return zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>), SELECT(T));
119  return a + b;
120  }
121 
122  /*---------.
123  | Addition |
124  `---------*/
125  template<typename T, typename U>
126  void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMax>&,
127  T& dst, U arg)
128  {
129  dst = std::max(dst, arg);
130  }
131 
132  template<typename T, typename U>
133  void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMin>&,
134  T& dst, U arg)
135  {
136  dst = std::min(dst, arg);
137  }
138 
139  template<typename T, typename U>
140  T op_add(const algebra::TropicalSemiring<algebra::TropicalMax>&, T a, U b)
141  {
142  return std::max(a, b);
143  }
144 
145  template<typename T, typename U>
146  T op_add(const algebra::TropicalSemiring<algebra::TropicalMin>&, T a, U b)
147  {
148  return std::min(a, b);
149  }
150 
151  /*-----.
152  | Star |
153  `-----*/
154  template <typename T>
155  bool
156  op_starable(const algebra::TropicalSemiring<algebra::TropicalMin>&, T b)
157  {
158  if (b < T(0))
159  return false;
160  return true;
161  }
162 
163  template <class T>
164  void
165  op_in_star(const algebra::TropicalSemiring<algebra::TropicalMin>&, T& b)
166  {
167  if (b >= T(0))
168  {
169  b = T(0);
170  return;
171  }
172  assertion(! "star not defined.");
173  }
174 
175  // Specialization for Boolean tropical semiring.
176  template <>
177  inline bool
178  op_starable(const algebra::TropicalSemiring<algebra::TropicalMin>&, bool)
179  {
180  return true;
181  }
182 
183  template <>
184  inline void
185  op_in_star(const algebra::TropicalSemiring<algebra::TropicalMin>&, bool& b)
186  {
187  b = 0;
188  }
189 
190 
191  template <typename T>
192  bool
193  op_starable(const algebra::TropicalSemiring<algebra::TropicalMax>&, T b)
194  {
195  if (b > T(0))
196  return false;
197  return true;
198  }
199 
200  template <class T>
201  void
202  op_in_star(const algebra::TropicalSemiring<algebra::TropicalMax>&, T& b)
203  {
204  if (b <= T(0))
205  {
206  b = T(0);
207  return;
208  }
209  assertion(! "star not defined.");
210  }
211 
212  template <class TropicalKind, class T>
213  Element<algebra::TropicalSemiring<TropicalKind>, T>
214  op_choose(const algebra::TropicalSemiring<TropicalKind>& set, SELECTOR(T))
215  {
216  return Element<algebra::TropicalSemiring<TropicalKind>, T>
217  (set, misc::random::generate<T>());
218  }
219 
220  template <class TropicalKind, typename T>
221  bool
222  op_can_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>&,
223  SELECTOR(T))
224  {
225  return true;
226  }
227 
228  template <class TropicalKind, class T>
229  Element<algebra::TropicalSemiring<TropicalKind>, T>
230  op_choose_starable(const algebra::TropicalSemiring<TropicalKind>& set,
231  SELECTOR(T))
232  {
233  T r;
234  do
235  r = op_choose(set, SELECT(T));
236  while (!op_starable(set, r));
237  return r;
238  }
239 
240  template <class TropicalKind, class T>
241  Element<algebra::TropicalSemiring<TropicalKind>, T>
242  op_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>& set,
243  SELECTOR(T))
244  {
245  T r;
246  do
247  r = op_choose(set, SELECT(T));
248  while (!op_starable(set, r));
249  return r;
250  }
251 
252  /*---------------.
253  | Pretty printer |
254  `---------------*/
255  template<typename St, typename T>
256  St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMax>&, St& st, const T& v)
257  {
258  if (v == zero_value(SELECT(algebra::TropicalSemiring<algebra::TropicalMax>), SELECT(T)))
259  st << "-oo";
260  else
261  st << v;
262  return st;
263  }
264 
265  template<typename St, typename T>
266  St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMin>&, St& st, const T& v)
267  {
268  if (v == zero_value(SELECT(algebra::TropicalSemiring<algebra::TropicalMin>), SELECT(T)))
269  st << "+oo";
270  else
271  st << v;
272  return st;
273  }
274 
275  } // algebra
276 
277 } // vcsn
278 
279 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HXX
Generated on Sat Jul 14 2012 18:46:41 for Vaucanson by   doxygen 1.8.1.1