tropical_semiring.hxx

00001 // tropical_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 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_TROPICAL_SEMIRING_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HXX
00019 # include <vaucanson/config/system.hh>
00020 # include <vaucanson/algebra/implementation/semiring/tropical_semiring.hh>
00021 # include <vaucanson/misc/random.hh>
00022 # include <vaucanson/misc/limits.hh>
00023 
00024 namespace vcsn {
00025 
00026   /*---------------.
00027   | Identity value |
00028   `---------------*/
00029   template<class TropicalKind, typename T>
00030   T identity_value(SELECTOR(algebra::TropicalSemiring<TropicalKind>), SELECTOR(T))
00031   {
00032     return T(0);
00033   }
00034 
00035   template<typename T>
00036   T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(T))
00037   {
00038     return utility::limits<T>::min();
00039   }
00040 
00041   template<>
00042   inline
00043   float zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(float))
00044   {
00045     return -utility::limits<float>::infinity();
00046   }
00047 
00048   template<>
00049   inline
00050   double zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>), SELECTOR(double))
00051   {
00052     return -utility::limits<double>::infinity();
00053   }
00054 
00055   template<typename T>
00056   T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(T))
00057   {
00058     return utility::limits<T>::max();
00059   }
00060 
00061   template<>
00062   inline
00063   float zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(float))
00064   {
00065     return utility::limits<float>::infinity();
00066   }
00067 
00068   template<>
00069   inline
00070   double zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>), SELECTOR(double))
00071   {
00072     return utility::limits<double>::infinity();
00073   }
00074 
00075   /*------------.
00076   | op_contains |
00077   `------------*/
00078   template<class TropicalKind, typename T>
00079   bool op_contains(const algebra::TropicalSemiring<TropicalKind>&, T c)
00080   {
00081     return true;
00082   }
00083 
00084   /*--------------------.
00085   | Multiplication is + |
00086   `--------------------*/
00087   template<class TropicalKind, typename T, typename U>
00088   void op_in_mul(const algebra::TropicalSemiring<TropicalKind>&,
00089                  T& dst, U arg)
00090   {
00091     if ((dst == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
00092                            SELECT(T))) ||
00093         (arg == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
00094                            SELECT(U))))
00095       dst = zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>), SELECT(T));
00096     else
00097       dst += arg;
00098   }
00099 
00100   template<class TropicalKind, typename T, typename U>
00101   T op_mul(const algebra::TropicalSemiring<TropicalKind>&, T a, U b)
00102   {
00103     if ((a == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
00104                          SELECT(T))) ||
00105         (b == zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>),
00106                          SELECT(U))))
00107       return zero_value(SELECT(algebra::TropicalSemiring<TropicalKind>), SELECT(T));
00108     return a + b;
00109   }
00110 
00111   /*---------.
00112   | Addition |
00113   `---------*/
00114   template<typename T, typename U>
00115   void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMax>&,
00116                  T& dst, U arg)
00117   {
00118     dst = std::max(dst, arg);
00119   }
00120 
00121   template<typename T, typename U>
00122   void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMin>&,
00123                  T& dst, U arg)
00124   {
00125     dst = std::min(dst, arg);
00126   }
00127 
00128   template<typename T, typename U>
00129   T op_add(const algebra::TropicalSemiring<algebra::TropicalMax>&, T a, U b)
00130   {
00131     return std::max(a, b);
00132   }
00133 
00134   template<typename T, typename U>
00135   T op_add(const algebra::TropicalSemiring<algebra::TropicalMin>&, T a, U b)
00136   {
00137     return std::min(a, b);
00138   }
00139 
00140   /*-----.
00141   | Star |
00142   `-----*/
00143   template <typename T>
00144   bool
00145   op_starable(const algebra::TropicalSemiring<algebra::TropicalMin>&, T b)
00146   {
00147     if (b < 0)
00148       return false;
00149     return true;
00150   }
00151 
00152   template <class T>
00153   void
00154   op_in_star(const algebra::TropicalSemiring<algebra::TropicalMin>&, T& b)
00155   {
00156     if (b >= 0)
00157       {
00158         b = 0;
00159         return;
00160       }
00161     assertion(! "star not defined.");
00162   }
00163 
00164   // Specialization for Boolean tropical semiring.
00165   template <>
00166   inline bool
00167   op_starable(const algebra::TropicalSemiring<algebra::TropicalMin>&, bool)
00168   {
00169     return true;
00170   }
00171 
00172   template <>
00173   inline void
00174   op_in_star(const algebra::TropicalSemiring<algebra::TropicalMin>&, bool& b)
00175   {
00176     b = 0;
00177   }
00178 
00179 
00180   template <typename T>
00181   bool
00182   op_starable(const algebra::TropicalSemiring<algebra::TropicalMax>&, T b)
00183   {
00184     if (b > 0)
00185       return false;
00186     return true;
00187   }
00188 
00189   template <class T>
00190   void
00191   op_in_star(const algebra::TropicalSemiring<algebra::TropicalMax>&, T& b)
00192   {
00193     if (b <= 0)
00194       {
00195         b = 0;
00196         return;
00197       }
00198     assertion(! "star not defined.");
00199   }
00200 
00201   template <class TropicalKind, class T>
00202   Element<algebra::TropicalSemiring<TropicalKind>, T>
00203   op_choose(const algebra::TropicalSemiring<TropicalKind>& set, SELECTOR(T))
00204   {
00205     return Element<algebra::TropicalSemiring<TropicalKind>, T>
00206       (set, utility::random::generate<T>());
00207   }
00208 
00209   template <class TropicalKind, typename T>
00210   bool
00211   op_can_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>&,
00212                              SELECTOR(T))
00213   {
00214     return true;
00215   }
00216 
00217   template <class TropicalKind, class T>
00218   Element<algebra::TropicalSemiring<TropicalKind>, T>
00219   op_choose_starable(const algebra::TropicalSemiring<TropicalKind>& set,
00220                      SELECTOR(T))
00221   {
00222     T r;
00223     do
00224       r = op_choose(set, SELECT(T));
00225     while (!op_starable(set, r));
00226     return r;
00227   }
00228 
00229   template <class TropicalKind, class T>
00230   Element<algebra::TropicalSemiring<TropicalKind>, T>
00231   op_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>& set,
00232                          SELECTOR(T))
00233   {
00234     T r;
00235     do
00236       r = op_choose(set, SELECT(T));
00237     while (!op_starable(set, r));
00238     return r;
00239   }
00240 
00241   /*---------------.
00242   | Pretty printer |
00243   `---------------*/
00244   template<typename St, typename T>
00245   St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMax>&, St& st, const T& v)
00246   {
00247     if (v == zero_value(SELECT(algebra::TropicalSemiring<algebra::TropicalMax>), SELECT(T)))
00248       st << "-oo";
00249     else
00250       st << v;
00251     return st;
00252   }
00253 
00254   template<typename St, typename T>
00255   St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMin>&, St& st, const T& v)
00256   {
00257     if (v == zero_value(SELECT(algebra::TropicalSemiring<algebra::TropicalMin>), SELECT(T)))
00258       st << "+oo";
00259     else
00260       st << v;
00261     return st;
00262   }
00263 } // vcsn
00264 
00265 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HXX

Generated on Fri Jul 28 12:18:55 2006 for Vaucanson by  doxygen 1.4.6