numerical_semiring.hxx

00001 // numerical_semiring.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_NUMERICAL_SEMIRING_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_NUMERICAL_SEMIRING_HXX
00019 
00020 # include <cmath>
00021 # include <vaucanson/algebra/concept/semiring_base.hh>
00022 # include <vaucanson/algebra/implementation/semiring/numerical_semiring.hh>
00023 # include <vaucanson/misc/random.hh>
00024 # include <vaucanson/misc/limits.hh>
00025 # include <vaucanson/misc/contract.hh>
00026 
00027 namespace vcsn {
00028 
00029   template<typename T>
00030   bool op_contains(const algebra::NumericalSemiring&, T)
00031   {
00032     return true;
00033   }
00034 
00035   template<typename T, typename U>
00036   void op_in_mul(const algebra::NumericalSemiring&,
00037                  T& dst, U arg)
00038   {
00039     dst *= arg;
00040   }
00041 
00042   template<typename T, typename U>
00043   void op_in_add(const algebra::NumericalSemiring&,
00044                  T& dst, U arg)
00045   {
00046     dst += arg;
00047   }
00048 
00049   // FIXME: there should be specializations of op_add_traits and
00050   // op_mul_traits giving the type of the result depending on the
00051   // type of the arguments.
00052 
00053   template<typename T, typename U>
00054   T op_mul(const algebra::NumericalSemiring&, T a, U b)
00055   {
00056     return a * b;
00057   }
00058 
00059   template<typename T, typename U>
00060   T op_add(const algebra::NumericalSemiring&, T a, U b)
00061   {
00062     return a + b;
00063   }
00064 
00065   template<typename T>
00066   T identity_value(SELECTOR(algebra::NumericalSemiring), SELECTOR(T))
00067   {
00068     return T(1);
00069   }
00070 
00071   template<typename T>
00072   T zero_value(SELECTOR(algebra::NumericalSemiring), SELECTOR(T))
00073   {
00074     return T(0);
00075   }
00076 
00077   template <class T>
00078   Element<algebra::NumericalSemiring, T>
00079   op_choose(const algebra::NumericalSemiring& set, SELECTOR(T))
00080   {
00081     return
00082       Element<algebra::NumericalSemiring, T>
00083         (set, misc::random::generate<T>());
00084   }
00085 
00086   /*-----------------------------.
00087   | specializations for integers |
00088   `-----------------------------*/
00089 
00090   inline
00091   bool
00092   op_can_choose_non_starable(const algebra::NumericalSemiring&,
00093                               SELECTOR(int))
00094   {
00095     return true; // Every integer excepted Zero is non-starable
00096   }
00097 
00098   inline
00099   Element<algebra::NumericalSemiring, int>
00100   op_choose_starable(const algebra::NumericalSemiring& set, SELECTOR(int))
00101   {
00102     // 0 is the only one integer to be starable. So we have no choice !
00103     return Element<algebra::NumericalSemiring, int>(set, 0);
00104   }
00105 
00106   inline
00107   Element<algebra::NumericalSemiring, int>
00108   op_choose_non_starable(const algebra::NumericalSemiring& set,
00109                          SELECTOR(int))
00110   {
00111     int r = misc::random::generate<int>();
00112     if (!r)
00113       r = 1;
00114     return Element<algebra::NumericalSemiring, int>(set, r);
00115   }
00116 
00117   /*-----------------------------.
00118   | specializations for Booleans |
00119   `-----------------------------*/
00120   template<typename T>
00121   void op_in_mul(const algebra::NumericalSemiring&,
00122                         bool& dst, bool src)
00123   {
00124     dst = dst && src;
00125   }
00126 
00127   inline bool op_mul(const algebra::NumericalSemiring&, bool a, bool b)
00128   {
00129     return a && b;
00130   }
00131 
00132   inline void op_in_add(const algebra::NumericalSemiring&,
00133                         bool& dst, bool src)
00134   {
00135     dst = dst || src;
00136   }
00137 
00138   inline bool op_add(const algebra::NumericalSemiring&, bool a, bool b)
00139   {
00140     return a || b;
00141   }
00142 
00143   inline bool identity_value(SELECTOR(algebra::NumericalSemiring),
00144                              SELECTOR(bool))
00145   {
00146     return true;
00147   }
00148 
00149   inline bool zero_value(SELECTOR(algebra::NumericalSemiring),
00150                          SELECTOR(bool))
00151   {
00152     return false;
00153   }
00154 
00155   inline bool op_starable(const algebra::NumericalSemiring&, bool)
00156   {
00157     return true;
00158   }
00159 
00160   inline void op_in_star(const algebra::NumericalSemiring&, bool& b)
00161   {
00162     b = true;
00163   }
00164 
00165   inline
00166   Element<algebra::NumericalSemiring, bool>
00167   op_choose_starable(const algebra::NumericalSemiring& set, SELECTOR(bool))
00168   {
00169     // Every Boolean is starable !
00170     return op_choose(set, SELECT(bool));
00171   }
00172 
00173   inline
00174   Element<algebra::NumericalSemiring, bool>
00175   op_choose_non_starable(const algebra::NumericalSemiring& set,
00176                          SELECTOR(bool))
00177   {
00178     assertion_(false, "Cannot choose non-starable boolean: all boolean are starable.");
00179     return Element<algebra::NumericalSemiring, bool>(set, false);
00180   }
00181 
00182   /*--------------------------------------------.
00183   | specialization for floating point numbers.  |
00184   `--------------------------------------------*/
00185 
00186   template<typename T>
00187   bool op_starable(const algebra::NumericalSemiring&, T v)
00188   {
00189     return v == 0;
00190   }
00191 
00192   inline bool op_starable(const algebra::NumericalSemiring&,
00193                            const float& f)
00194   {
00195     return (-1.0 < f) && (f < 1.0);
00196   }
00197 
00198   inline bool op_starable(const algebra::NumericalSemiring&,
00199                            const double& f)
00200   {
00201     return (-1.0 < f) && (f < 1.0);
00202   }
00203 
00204   inline void op_in_star(const algebra::NumericalSemiring&, float& f)
00205   {
00206     static_assertion(misc::limits<float>::has_infinity,
00207                      float_has_infinity);
00208     if (f < 1.0)
00209       f = (1.0 / (1.0 - f));
00210     else
00211       f = misc::limits<float>::infinity();
00212   }
00213 
00214   inline void op_in_star(const algebra::NumericalSemiring&, double& f)
00215   {
00216     if (f < 1.0)
00217       f = (1.0 / (1.0 - f));
00218     else
00219       assertion(! "star not defined.");
00220   }
00221 
00222   inline
00223   bool
00224   op_can_choose_non_starable(const algebra::NumericalSemiring&,
00225                               SELECTOR(float))
00226   {
00227     return true; // Every float which is less than -1 or greater than 1 is
00228                  // non-starable.
00229   }
00230 
00231   inline
00232   Element<algebra::NumericalSemiring, float>
00233   op_choose_starable(const algebra::NumericalSemiring& set,
00234                      SELECTOR(float))
00235   {
00236     float res = misc::random::generate<float>(-1, 1);
00237 
00238     while (res == -1)
00239       res = misc::random::generate<float>(-1, 1);
00240     return
00241       Element<algebra::NumericalSemiring, float>
00242         (set, res);
00243   }
00244 
00245   inline
00246   Element<algebra::NumericalSemiring, float>
00247   op_choose_non_starable(const algebra::NumericalSemiring& set,
00248                          SELECTOR(float))
00249   {
00250     float res = misc::random::generate<float>() * 1000.;
00251     while (op_starable(set, res))
00252       res = misc::random::generate<float>() * 1000.;
00253     return Element<algebra::NumericalSemiring, float>(set, res);
00254   }
00255 
00256   inline
00257   bool
00258   op_can_choose_non_starable(const algebra::NumericalSemiring&,
00259                               SELECTOR(double))
00260   {
00261     return true; // Every float which is less than -1 or greater than 1 is
00262                  // non-starable.
00263   }
00264 
00265   inline
00266   Element<algebra::NumericalSemiring, double>
00267   op_choose_starable(const algebra::NumericalSemiring& set,
00268                      SELECTOR(double))
00269   {
00270     double res = misc::random::generate<double>(-1, 1);
00271 
00272     while (res == -1)
00273       res = misc::random::generate<double>(-1, 1);
00274     return
00275       Element<algebra::NumericalSemiring, double>
00276         (set, res);
00277   }
00278 
00279   inline
00280   Element<algebra::NumericalSemiring, double>
00281   op_choose_non_starable(const algebra::NumericalSemiring& set,
00282                          SELECTOR(double))
00283   {
00284     double res = misc::random::generate<double>() * 1000.;
00285     while (op_starable(set, res))
00286       res = misc::random::generate<double>() * 1000.;
00287     return Element<algebra::NumericalSemiring, double>(set, res);
00288   }
00289   // FIXME: add some more operators as syntactic sugar
00290 
00291 
00292   /*------------------------------------.
00293   | specialization for rational numbers |
00294    `------------------------------------*/
00295 
00296   inline algebra::RationalNumber
00297   identity_value(SELECTOR(algebra::NumericalSemiring),
00298                  SELECTOR(algebra::RationalNumber))
00299   {
00300     return algebra::RationalNumber(1);
00301   }
00302 
00303   inline algebra::RationalNumber
00304   zero_value(SELECTOR(algebra::NumericalSemiring),
00305              SELECTOR(algebra::RationalNumber))
00306   {
00307     return algebra::RationalNumber(0);
00308   }
00309 
00310   inline bool op_starable(const algebra::NumericalSemiring&,
00311                           const algebra::RationalNumber& r)
00312   {
00313     int denom = r.denom();
00314     return abs(r.num()) < denom;
00315   }
00316 
00317   inline void op_in_star(const algebra::NumericalSemiring&,
00318                          algebra::RationalNumber& r)
00319   {
00320     int denom = r.denom();
00321     algebra::RationalNumber one = algebra::RationalNumber(1, 1);
00322     if (denom > abs(r.num()))
00323       r = (one / (r - one));
00324     else
00325       assertion(! "star not defined.");
00326   }
00327 
00328   inline
00329   bool
00330   op_can_choose_non_starable(const algebra::NumericalSemiring&,
00331                               SELECTOR(algebra::RationalNumber))
00332   {
00333     return true; // Every rational number which is greater than 1 and
00334                  // less than -1 is non-starable
00335   }
00336 
00337   inline
00338   Element<algebra::NumericalSemiring, algebra::RationalNumber>
00339   op_choose_starable(const algebra::NumericalSemiring& set,
00340                      SELECTOR(algebra::RationalNumber))
00341   {
00342     algebra::RationalNumber min = algebra::RationalNumber(-1, 1);
00343     algebra::RationalNumber max = algebra::RationalNumber(1, 1);
00344     return
00345       Element<algebra::NumericalSemiring, algebra::RationalNumber>
00346         (set, misc::random::generate<algebra::RationalNumber>(min, max));
00347   }
00348 
00349   inline
00350   Element<algebra::NumericalSemiring, algebra::RationalNumber>
00351   op_choose_non_starable(const algebra::NumericalSemiring& set,
00352                          SELECTOR(algebra::RationalNumber))
00353   {
00354     algebra::RationalNumber res = algebra::RationalNumber(1, 1);
00355     int denom;
00356     do
00357       {
00358         res = misc::random::generate<algebra::RationalNumber>();
00359         denom = res.denom();
00360       }
00361     while (denom > abs(res.num()));
00362     return
00363       Element<algebra::NumericalSemiring, algebra::RationalNumber>
00364       (set, res);
00365   }
00366 
00367 } // vcsn
00368 
00369 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_NUMERICAL_SEMIRING_HXX

Generated on Sun Jul 29 19:35:28 2007 for Vaucanson by  doxygen 1.5.2