Vaucanson  1.4.1
implementation/semiring/numerical_semiring.hxx
1 // numerical_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, 2008, 2009, 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_NUMERICAL_SEMIRING_HXX
18 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_NUMERICAL_SEMIRING_HXX
19 
20 # include <cmath>
21 # include <vaucanson/algebra/concept/semiring_base.hh>
22 # include <vaucanson/algebra/implementation/semiring/numerical_semiring.hh>
23 
24 # include <vaucanson/misc/random.hh>
25 # include <vaucanson/misc/limits.hh>
26 # include <vaucanson/misc/contract.hh>
27 
28 namespace vcsn {
29 
30  namespace algebra {
31 
32  template<typename T>
33  bool op_contains(const algebra::NumericalSemiring&, T)
34  {
35  return true;
36  }
37 
38  template<typename T, typename U>
39  void op_in_mul(const algebra::NumericalSemiring&,
40  T& dst, U arg)
41  {
42  dst *= arg;
43  }
44 
45  template<typename T, typename U>
46  void op_in_add(const algebra::NumericalSemiring&,
47  T& dst, U arg)
48  {
49  dst += arg;
50  }
51 
52  // FIXME: there should be specializations of op_add_traits and
53  // op_mul_traits giving the type of the result depending on the
54  // type of the arguments.
55 
56  template<typename T, typename U>
57  T op_mul(const algebra::NumericalSemiring&, T a, U b)
58  {
59  return a * b;
60  }
61 
62  template<typename T, typename U>
63  T op_add(const algebra::NumericalSemiring&, T a, U b)
64  {
65  return a + b;
66  }
67 
68  template<typename T>
69  T identity_value(SELECTOR(algebra::NumericalSemiring), SELECTOR(T))
70  {
71  return T(1);
72  }
73 
74  template<typename T>
75  bool show_identity_value(SELECTOR(algebra::NumericalSemiring), SELECTOR(T))
76  {
77  return false;
78  }
79 
80  template<typename T>
81  T zero_value(SELECTOR(algebra::NumericalSemiring), SELECTOR(T))
82  {
83  return T(0);
84  }
85 
86  template <class T>
87  Element<algebra::NumericalSemiring, T>
88  op_choose(const algebra::NumericalSemiring& set, SELECTOR(T))
89  {
90  return
91  Element<algebra::NumericalSemiring, T>
92  (set, misc::random::generate<T>());
93  }
94 
95  /*-----------------------------.
96  | specializations for integers |
97  `-----------------------------*/
98 
99  inline
100  bool
101  op_can_choose_non_starable(const algebra::NumericalSemiring&,
102  SELECTOR(int))
103  {
104  return true; // Every integer excepted Zero is non-starable
105  }
106 
107  inline
108  Element<algebra::NumericalSemiring, int>
109  op_choose_starable(const algebra::NumericalSemiring& set, SELECTOR(int))
110  {
111  // 0 is the only one integer to be starable. So we have no choice !
112  return Element<algebra::NumericalSemiring, int>(set, 0);
113  }
114 
115  inline
116  Element<algebra::NumericalSemiring, int>
117  op_choose_non_starable(const algebra::NumericalSemiring& set,
118  SELECTOR(int))
119  {
120  int r = misc::random::generate<int>();
121  if (!r)
122  r = 1;
123  return Element<algebra::NumericalSemiring, int>(set, r);
124  }
125 
126  /*-----------------------------.
127  | specializations for Booleans |
128  `-----------------------------*/
129  template <typename T>
130  void op_in_mul(const algebra::NumericalSemiring&, bool& dst, bool src)
131  {
132  dst = dst && src;
133  }
134 
135  inline bool op_mul(const algebra::NumericalSemiring&, bool a, bool b)
136  {
137  return a && b;
138  }
139 
140  inline void op_in_add(const algebra::NumericalSemiring&,
141  bool& dst, bool src)
142  {
143  dst = dst || src;
144  }
145 
146  inline bool op_add(const algebra::NumericalSemiring&, bool a, bool b)
147  {
148  return a || b;
149  }
150 
151  inline bool identity_value(SELECTOR(algebra::NumericalSemiring),
152  SELECTOR(bool))
153  {
154  return true;
155  }
156 
157  inline bool zero_value(SELECTOR(algebra::NumericalSemiring),
158  SELECTOR(bool))
159  {
160  return false;
161  }
162 
163  inline bool op_starable(const algebra::NumericalSemiring&, bool)
164  {
165  return true;
166  }
167 
168  inline void op_in_star(const algebra::NumericalSemiring&, bool& b)
169  {
170  b = true;
171  }
172 
173  inline
174  Element<algebra::NumericalSemiring, bool>
175  op_choose_starable(const algebra::NumericalSemiring& set, SELECTOR(bool))
176  {
177  // Every Boolean is starable !
178  return op_choose(set, SELECT(bool));
179  }
180 
181  inline
182  Element<algebra::NumericalSemiring, bool>
183  op_choose_non_starable(const algebra::NumericalSemiring& set,
184  SELECTOR(bool))
185  {
186  assertion_(false, "Cannot choose non-starable boolean: all boolean are starable.");
187  return Element<algebra::NumericalSemiring, bool>(set, false);
188  }
189 
190  /*--------------------------------------------.
191  | specialization for floating point numbers. |
192  `--------------------------------------------*/
193 
194  inline float op_sub(const algebra::NumericalSemiring&, const float& a, const float& b)
195  {
196  return a - b;
197  }
198 
199  inline double op_sub(const algebra::NumericalSemiring&, const double& a, const double& b)
200  {
201  return a - b;
202  }
203 
204  inline float op_div(const algebra::NumericalSemiring&, const float& a, const float& b)
205  {
206  return a / b;
207  }
208 
209  inline double op_div(const algebra::NumericalSemiring&, const double& a, const double& b)
210  {
211  return a / b;
212  }
213 
214  inline bool op_eq(const algebra::NumericalSemiring&, float& a, float& b)
215  {
216  return std::abs(a - b) < 0.00001;
217  }
218 
219  inline bool op_eq(const algebra::NumericalSemiring&, double& a, double& b)
220  {
221  return std::abs(a - b) < 0.00001;
222  }
223 
224  template<typename T>
225  bool op_starable(const algebra::NumericalSemiring&, T v)
226  {
227  return v == 0;
228  }
229 
230  inline bool op_starable(const algebra::NumericalSemiring&,
231  const float& f)
232  {
233  return (-1.0 < f) && (f < 1.0);
234  }
235 
236  inline bool op_starable(const algebra::NumericalSemiring&,
237  const double& f)
238  {
239  return (-1.0 < f) && (f < 1.0);
240  }
241 
242  inline void op_in_star(const algebra::NumericalSemiring&, float& f)
243  {
244  static_assertion(misc::limits<float>::has_infinity,
245  float_has_infinity);
246  if (f < 1.0)
247  f = (1.0 / (1.0 - f));
248  else
249  f = misc::limits<float>::infinity();
250  }
251 
252  inline void op_in_star(const algebra::NumericalSemiring&, double& f)
253  {
254  if (f < 1.0)
255  f = (1.0 / (1.0 - f));
256  else
257  assertion(! "star not defined.");
258  }
259 
260  inline
261  bool
262  op_can_choose_non_starable(const algebra::NumericalSemiring&,
263  SELECTOR(float))
264  {
265  return true; // Every float which is less than -1 or greater than 1 is
266  // non-starable.
267  }
268 
269  inline
270  Element<algebra::NumericalSemiring, float>
271  op_choose_starable(const algebra::NumericalSemiring& set,
272  SELECTOR(float))
273  {
274  float res = misc::random::generate<float>(-1, 1);
275 
276  while (res == -1)
277  res = misc::random::generate<float>(-1, 1);
278  return
279  Element<algebra::NumericalSemiring, float>
280  (set, res);
281  }
282 
283  inline
284  Element<algebra::NumericalSemiring, float>
285  op_choose_non_starable(const algebra::NumericalSemiring& set,
286  SELECTOR(float))
287  {
288  float res = misc::random::generate<float>() * 1000.;
289  while (op_starable(set, res))
290  res = misc::random::generate<float>() * 1000.;
291  return Element<algebra::NumericalSemiring, float>(set, res);
292  }
293 
294  inline
295  bool
296  op_can_choose_non_starable(const algebra::NumericalSemiring&,
297  SELECTOR(double))
298  {
299  return true; // Every float which is less than -1 or greater than 1 is
300  // non-starable.
301  }
302 
303  inline
304  Element<algebra::NumericalSemiring, double>
305  op_choose_starable(const algebra::NumericalSemiring& set,
306  SELECTOR(double))
307  {
308  double res = misc::random::generate<double>(-1, 1);
309 
310  while (res == -1)
311  res = misc::random::generate<double>(-1, 1);
312  return
313  Element<algebra::NumericalSemiring, double>
314  (set, res);
315  }
316 
317  inline
318  Element<algebra::NumericalSemiring, double>
319  op_choose_non_starable(const algebra::NumericalSemiring& set,
320  SELECTOR(double))
321  {
322  double res = misc::random::generate<double>() * 1000.;
323  while (op_starable(set, res))
324  res = misc::random::generate<double>() * 1000.;
325  return Element<algebra::NumericalSemiring, double>(set, res);
326  }
327  // FIXME: add some more operators as syntactic sugar
328 
329 
330  /*------------------------------------.
331  | specialization for rational numbers |
332  `------------------------------------*/
333 
334 
335  inline RationalNumber
336  op_sub(const algebra::NumericalSemiring&, const RationalNumber& a, const RationalNumber& b)
337  {
338  return a - b;
339  }
340 
341  inline RationalNumber
342  op_div(const algebra::NumericalSemiring&, const RationalNumber& a, const RationalNumber& b)
343  {
344  return a / b;
345  }
346 
347 
348  inline algebra::RationalNumber
349  identity_value(SELECTOR(algebra::NumericalSemiring),
350  SELECTOR(algebra::RationalNumber))
351  {
352  return algebra::RationalNumber(1);
353  }
354 
355  inline algebra::RationalNumber
356  zero_value(SELECTOR(algebra::NumericalSemiring),
357  SELECTOR(algebra::RationalNumber))
358  {
359  return algebra::RationalNumber(0);
360  }
361 
362  inline bool
363  op_starable(const algebra::NumericalSemiring&,
364  const algebra::RationalNumber& r)
365  {
366  return std::abs(r.num_get()) < r.den_get ();
367  }
368 
369  inline bool
370  op_starable(const algebra::NumericalSemiring&,
371  algebra::RationalNumber& r)
372  {
373  return std::abs(r.num_get()) < r.den_get ();
374  }
375 
376  inline void op_in_star(const algebra::NumericalSemiring&,
377  algebra::RationalNumber& r)
378  {
379  if (std::abs(r.num_get()) < r.den_get ())
380  {
381  algebra::RationalNumber one = algebra::RationalNumber(1);
382  r = one / (one - r);
383  }
384  else
385  assertion(! "vcsn::algebra::RationalNumber: star not defined.");
386  }
387 
388  inline
389  bool
390  op_can_choose_non_starable(const algebra::NumericalSemiring&,
391  SELECTOR(algebra::RationalNumber))
392  {
393  return true; // Every rational number which is greater than 1 and
394  // less than -1 is non-starable
395  }
396 
397  inline
398  Element<algebra::NumericalSemiring, algebra::RationalNumber>
399  op_choose_starable(const algebra::NumericalSemiring& set,
400  SELECTOR(algebra::RationalNumber))
401  {
402  algebra::RationalNumber min = algebra::RationalNumber(-1, 1);
403  algebra::RationalNumber max = algebra::RationalNumber(1, 1);
404  return
405  Element<algebra::NumericalSemiring, algebra::RationalNumber>
406  (set, misc::random::generate<algebra::RationalNumber>(min, max));
407  }
408 
409  inline
410  Element<algebra::NumericalSemiring, algebra::RationalNumber>
411  op_choose_non_starable(const algebra::NumericalSemiring& set,
412  SELECTOR(algebra::RationalNumber))
413  {
414  algebra::RationalNumber res;
415  do
416  {
417  res = misc::random::generate<algebra::RationalNumber> ();
418  }
419  while (res.den_get () >= std::abs(res.num_get ()));
420  return Element<algebra::NumericalSemiring, algebra::RationalNumber> (set, res);
421  }
422 
423  } // algebra
424 
425 } // vcsn
426 
427 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_NUMERICAL_SEMIRING_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1