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