Vaucanson: cyclic_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_CYCLIC_SEMIRING_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_CYCLIC_SEMIRING_HXX
00019 # include <vaucanson/config/system.hh>
00020 # include <vaucanson/algebra/implementation/semiring/cyclic_semiring.hh>
00021 # include <vaucanson/misc/random.hh>
00022 # include <vaucanson/misc/limits.hh>
00023 # include <boost/swap.hpp>
00024 # include <boost/tuple/tuple.hpp>
00025 
00026 namespace vcsn {
00027 
00028   namespace algebra {
00029 
00039     inline
00040     boost::tuple<unsigned int, int, int>
00041     ext_gcd (unsigned int a, unsigned int b)
00042     {
00043       unsigned int q, r;
00044       int x1 = 0;
00045       int x2 = 1;
00046       int y1 = 1;
00047       int y2 = 0;
00048       int x, y;
00049 
00050       if (a < b)
00051         {
00052           boost::swap (a, b);
00053           boost::swap (x1, x2);
00054           boost::swap (y1, y2);
00055         }
00056 
00057       if (b == 0)
00058         return boost::tuple<unsigned int, int, int> (a, 1, 0);
00059 
00060       while (b > 0)
00061         {
00062           q = a / b;
00063           r = a - q * b;
00064           x = x2 - q * x1;
00065           y = y2 - q * y1;
00066           a = b;
00067           b = r;
00068           x2 = x1;
00069           x1 = x;
00070           y2 = y1;
00071           y1 = y;
00072         }
00073 
00074       return boost::tuple<unsigned int, int, int> (a, x2, y2);
00075     }
00076 
00077     /*---------------.
00078     | Identity value |
00079     `---------------*/
00080 
00081     template<unsigned int n, typename T>
00082     T identity_value(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
00083     {
00084       return T(1);
00085     }
00086 
00087     template<unsigned int n, typename T>
00088     bool show_identity_value(SELECTOR(algebra::CyclicSemiring<n>),
00089                              SELECTOR(T))
00090     {
00091       return false;
00092     }
00093 
00094     template<unsigned int n, typename T>
00095     bool
00096     is_positive_semiring(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
00097     {
00098       return false;
00099     }
00100 
00101     template<unsigned int n, typename T>
00102     T zero_value(SELECTOR(algebra::CyclicSemiring<n>), SELECTOR(T))
00103     {
00104       return T(0);
00105     }
00106 
00107     /*------------.
00108     | op_contains |
00109     `------------*/
00110     template<unsigned int n, typename T>
00111     bool op_contains(const algebra::CyclicSemiring<n>&, T c)
00112     {
00113       return true;
00114     }
00115 
00116     /*---------------.
00117     | Multiplication |
00118     `---------------*/
00119     template<unsigned int n, typename T, typename U>
00120     void op_in_mul(const algebra::CyclicSemiring<n>&,
00121                    T& dst, U arg)
00122     {
00123       dst = (dst * arg) % n;
00124       dst = (dst < 0) ? dst + n : dst;
00125     }
00126 
00127     template<unsigned int n, typename T, typename U>
00128     T op_mul(const algebra::CyclicSemiring<n>&, T a, U b)
00129     {
00130       T res = (a * b) % n;
00131       return ((res < 0) ? res + n : res);
00132     }
00133 
00134     /*-----------------------.
00135     | Mutiplication for Z/2Z |
00136     `-----------------------*/
00137 
00138     inline
00139     void op_in_mul(const algebra::CyclicSemiring<2>&,
00140                                   bool& dst, bool arg)
00141     {
00142       dst = dst && arg;
00143     }
00144 
00145     inline
00146     bool op_mul(const algebra::CyclicSemiring<2>&, bool a, bool b)
00147     {
00148       return (a && b);
00149     }
00150 
00151     /*---------.
00152     | Addition |
00153     `---------*/
00154     template<unsigned int n, typename T, typename U>
00155     void op_in_add(const algebra::CyclicSemiring<n>&,
00156                    T& dst, U arg)
00157     {
00158       dst = ((dst + arg) + (2 * n)) % n;
00159     }
00160 
00161     template<unsigned int n, typename T, typename U>
00162     T op_add(const algebra::CyclicSemiring<n>&, T a, U b)
00163     {
00164       return ((a + b) + (2 * n)) % n;
00165     }
00166 
00167     /*------------------.
00168     | Addition for Z/2Z |
00169     `------------------*/
00170 
00171     inline
00172     void op_in_add(const algebra::CyclicSemiring<2>&,
00173                                   bool& dst, bool arg)
00174     {
00175       dst = dst ^ arg;
00176     }
00177 
00178     inline
00179     bool op_add(const algebra::CyclicSemiring<2>&, bool a, bool b)
00180     {
00181       return a ^ b;
00182     }
00183 
00184     /*---------.
00185     | Division |
00186     `---------*/
00187 
00188     template<unsigned int n, typename T, typename U>
00189     void op_in_div (const algebra::CyclicSemiring<n>& s1,
00190                     T& dst, U arg)
00191     {
00192       boost::tuple<unsigned int , int, int> res = ext_gcd (dst, arg);
00193       if (res.get<0> () == 1)
00194         {
00195           op_in_mul (s1, dst, res.get<2> ());
00196           return;
00197         }
00198 
00199       assertion(! "tried to divide by a number"
00200                 " without multiplicative inverse.");
00201     }
00202 
00203     template<unsigned int n, typename T, typename U>
00204     T op_div (const algebra::CyclicSemiring<n>& s, T a, U b)
00205     {
00206       boost::tuple<unsigned int , int, int> res = ext_gcd (a, b);
00207       if (res.get<0> () == 1)
00208         return (op_mul (s, a, res.get<2> ()));
00209 
00210       assertion(! "tried to divide by a number"
00211                 " without multiplicative inverse.");
00212     }
00213 
00214     /*------------------.
00215     | Division for Z/2Z |
00216     `------------------*/
00217 
00218     inline
00219     void op_in_div (const algebra::CyclicSemiring<2>& s1,
00220                                    bool& dst, bool arg)
00221     {
00222       if (arg == 1)
00223         return;
00224       assertion (! "Division by zero.");
00225     }
00226 
00227     inline
00228     bool op_div (const algebra::CyclicSemiring<2>& s, bool a, bool b)
00229     {
00230       if (b == 1)
00231         return (a);
00232       assertion(! "Division by zero.");
00233     }
00234 
00235     /*-------------.
00236     | Substraction |
00237     `-------------*/
00238 
00239     template<unsigned int n, typename T, typename U>
00240     void op_in_sub(const algebra::CyclicSemiring<n>& s1,
00241                    T& dst, U arg)
00242     {
00243       dst = (dst - arg) % n;
00244       dst = (dst < 0) ? dst + n : dst;
00245     }
00246 
00247     template<unsigned int n, typename T, typename U>
00248     T op_sub(const algebra::CyclicSemiring<n>& s,
00249              T a, U b)
00250     {
00251       T res = (a - b) % n;
00252       return ((res < 0) ? res + n : res);
00253     }
00254 
00255     /*----------------------.
00256     | Substraction for Z/2Z |
00257     `----------------------*/
00258 
00259     inline
00260     void op_in_sub(const algebra::CyclicSemiring<2>& s1,
00261                                    bool& dst, bool arg)
00262     {
00263       dst = dst ^ arg;
00264     }
00265 
00266     inline
00267     bool op_sub(const algebra::CyclicSemiring<2>& s,
00268                 bool a, bool b)
00269     {
00270       return (a ^ b);
00271     }
00272 
00273     /*-----.
00274     | Star |
00275     `-----*/
00276 
00277     template <unsigned int n, typename T>
00278     bool
00279     op_starable(const algebra::CyclicSemiring<n>&, T b)
00280     {
00281       if (b == T(0))
00282         return true;
00283       return false;
00284     }
00285 
00286     template <unsigned int n, class T>
00287     void
00288     op_in_star(const algebra::CyclicSemiring<n>&, T& b)
00289     {
00290       if (b == T(0))
00291         {
00292           b = T(1);
00293           return;
00294         }
00295       assertion(! "star not defined.");
00296     }
00297 
00298     template <unsigned int n, class T>
00299     Element<algebra::CyclicSemiring<n>, T>
00300     op_choose(const algebra::CyclicSemiring<n>& set, SELECTOR(T))
00301     {
00302       return Element<algebra::CyclicSemiring<n>, T>
00303         (set, misc::random::generate<T>());
00304     }
00305 
00306     template <unsigned int n, typename T>
00307     bool
00308     op_can_choose_non_starable(const algebra::CyclicSemiring<n>&,
00309                                SELECTOR(T))
00310     {
00311       return true;
00312     }
00313 
00314     template <unsigned int n, class T>
00315     Element<algebra::CyclicSemiring<n>, T>
00316     op_choose_starable(const algebra::CyclicSemiring<n>& set,
00317                        SELECTOR(T))
00318     {
00319       T r;
00320       do
00321         r = op_choose(set, SELECT(T));
00322       while (!op_starable(set, r));
00323       return r;
00324     }
00325 
00326     template <unsigned int n, class T>
00327     Element<algebra::CyclicSemiring<n>, T>
00328     op_choose_non_starable(const algebra::CyclicSemiring<n>& set,
00329                            SELECTOR(T))
00330     {
00331       T r;
00332       do
00333         r = op_choose(set, SELECT(T));
00334       while (op_starable(set, r));
00335       return r;
00336     }
00337 
00338     /*---------------.
00339     | Pretty printer |
00340     `---------------*/
00341     template<unsigned int n, typename St, typename T>
00342     St& op_rout(const algebra::CyclicSemiring<n>&, St& st, const T& v)
00343     {
00344       st << v;
00345       return st;
00346     }
00347 
00348   } // algebra
00349 
00350 } // vcsn
00351 
00352 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SEMIRING_CYCLIC_SEMIRING_HXX