Vaucanson: tropical_semiring.hxx Source File

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