Vaucanson: tropical_semiring.hh Source File

00001 // tropical_semiring.hh: 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, 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_HH
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HH
00019 
00020 # include <vaucanson/algebra/concept/tropical_semiring.hh>
00021 
00022 namespace vcsn {
00023 
00024   namespace algebra {
00025 
00026     // We provide a generic implementation of tropical semirings
00027     // formed with C++-builtins and standard operations (std::min,
00028     // std::max, +).
00029 
00030     /*---------------.
00031     | Identity value |
00032     `---------------*/
00033     template<class TropicalKind, typename T>
00034     T identity_value(SELECTOR(algebra::TropicalSemiring<TropicalKind>),
00035                      SELECTOR(T));
00036 
00037     template<class TropicalKind, typename T>
00038     bool show_identity_value(SELECTOR(algebra::TropicalSemiring<TropicalKind>),
00039                              SELECTOR(T));
00040 
00041 
00042     template<typename T>
00043     T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMax>),
00044                  SELECTOR(T));
00045 
00046     template<typename T>
00047     T zero_value(SELECTOR(algebra::TropicalSemiring<algebra::TropicalMin>),
00048                  SELECTOR(T));
00049 
00050     /*------------.
00051     | op_contains |
00052     `------------*/
00053     template<class TropicalKind, typename T>
00054     bool op_contains(const algebra::TropicalSemiring<TropicalKind>& s, T c);
00055 
00056     /*--------------------.
00057     | Multiplication is + |
00058     `--------------------*/
00059     template<class TropicalKind, typename T, typename U>
00060     void op_in_mul(const algebra::TropicalSemiring<TropicalKind>& s1,
00061                    T& dst, U arg);
00062 
00063     template<class TropicalKind, typename T, typename U>
00064     T op_mul(const algebra::TropicalSemiring<TropicalKind>& s, T a, U b);
00065 
00066     /*---------.
00067     | Addition |
00068     `---------*/
00069     template<typename T, typename U>
00070     void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMax>& s1,
00071                    T& dst, U arg);
00072 
00073     template<typename T, typename U>
00074     void op_in_add(const algebra::TropicalSemiring<algebra::TropicalMin>& s1,
00075                    T& dst, U arg);
00076 
00077     template<typename T, typename U>
00078     T op_add(const algebra::TropicalSemiring<algebra::TropicalMax>& s,
00079              T a, U b);
00080 
00081     template<typename T, typename U>
00082     T op_add(const algebra::TropicalSemiring<algebra::TropicalMin>& s,
00083              T a, U b);
00084 
00085     /*-----.
00086     | Star |
00087     `-----*/
00088     template <typename T>
00089     bool
00090     op_starable(const algebra::TropicalSemiring<algebra::TropicalMin>&, T b);
00091 
00092     template <class T>
00093     void
00094     op_in_star(const algebra::TropicalSemiring<algebra::TropicalMin>& s, T& b);
00095 
00096     template <typename T>
00097     bool
00098     op_starable(const algebra::TropicalSemiring<algebra::TropicalMax>&, T b);
00099 
00100     template <class T>
00101     void
00102     op_in_star(const algebra::TropicalSemiring<algebra::TropicalMax>&, T& b);
00103 
00104     template <class TropicalKind, class T>
00105     Element<algebra::TropicalSemiring<TropicalKind>, T>
00106     op_choose(const algebra::TropicalSemiring<TropicalKind>& set, SELECTOR(T));
00107 
00108     template <class TropicalKind, typename T>
00109     bool
00110     op_can_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>&
00111                                set, SELECTOR(T));
00112 
00113     template <class TropicalKind, typename T>
00114     Element<algebra::TropicalSemiring<TropicalKind>, T>
00115     op_choose_starable(const algebra::TropicalSemiring<TropicalKind>& set,
00116                        SELECTOR(T));
00117 
00118     template <class TropicalKind, typename T>
00119     Element<algebra::TropicalSemiring<TropicalKind>, T>
00120     op_choose_non_starable(const algebra::TropicalSemiring<TropicalKind>& set,
00121                            SELECTOR(T));
00122 
00123     /*---------------.
00124     | Pretty printer |
00125     `---------------*/
00126     template<typename St, typename T>
00127     St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMax>& s,
00128                 St& st, const T& v);
00129 
00130     template<typename St, typename T>
00131     St& op_rout(const algebra::TropicalSemiring<algebra::TropicalMin>& s,
00132                 St& st, const T& v);
00133 
00134   } // algebra
00135 
00136   template<class TropicalKind, typename T>
00137   struct semiring_traits<algebra::TropicalSemiring<TropicalKind>, T>
00138   {
00139     enum { is_positive = 1 };
00140   };
00141 
00142 
00143 } // vcsn
00144 
00145 
00146 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00147 #  include <vaucanson/algebra/implementation/semiring/tropical_semiring.hxx>
00148 # endif // VCSN_USE_INTERFACE_ONLY
00149 
00150 
00151 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_TROPICAL_SEMIRING_HH