Vaucanson: krat.hh Source File

00001 // krat.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, 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_SERIES_KRAT_HH
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HH
00019 
00020 # include <list>
00021 
00022 # include <vaucanson/algebra/implementation/series/series.hh>
00023 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
00024 # include <vaucanson/algebra/implementation/series/rat/dump_visitor.hh>
00025 
00026 namespace vcsn {
00027 
00028   namespace algebra {
00029 
00030     /*------------------.
00031     | Series compliance |
00032     `------------------*/
00033 
00034     template<typename Tm, typename Tw>
00035     struct series_traits<rat::exp<Tm, Tw> >
00036     {
00037       typedef Tm        monoid_elt_value_t;
00038       typedef Tw        semiring_elt_value_t;
00039       typedef std::list<monoid_elt_value_t> support_t;
00040     };
00041 
00042     template <class Tm, class Tw, class W, class M>
00043     struct mute_series_impl<rat::exp<Tm, Tw>, W, M>
00044     {
00045       typedef rat::exp<M, W>    ret;
00046     };
00047 
00048   } // algebra
00049 
00050  /*---------------------------------------------.
00051  | MetaElement<Series<W, M>, rat::exp<Tm, Tw> > |
00052  `---------------------------------------------*/
00053   template<typename W, typename M, typename Tm, typename Tw>
00054   struct MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >
00055     : MetaElement<algebra::SeriesBase<algebra::Series<W, M> >,
00056                   rat::exp<Tm, Tw> >
00057   {
00058     static const bool dynamic_value = true;
00059 
00060     void        accept(const rat::ConstNodeVisitor<Tm, Tw>& v) const;
00061     size_t      depth() const;
00062   };
00063 
00064 
00065   namespace algebra {
00066 
00067     template<typename W, typename M, typename Tm, typename Tw>
00068     bool op_contains(const algebra::Series<W, M>& s,
00069                      const rat::exp<Tm, Tw>& m);
00070 
00071     template<typename W, typename M, typename Tm, typename Tw>
00072     bool op_is_finite_app(const algebra::Series<W, M>& s,
00073                           const rat::exp<Tm, Tw>& m);
00074 
00075     template <typename W, typename M, typename Tm, typename Tw>
00076     Tm op_choose_from_supp(const algebra::Series<W, M>& s,
00077                            const rat::exp<Tm, Tw>& m);
00078 
00079     template<typename W, typename M, typename Tm, typename Tw>
00080     const rat::exp<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
00081                                            SELECTOR2(rat::exp<Tm, Tw>));
00082 
00083     template<typename W, typename M, typename Tm, typename Tw>
00084     bool show_identity_value(SELECTOR2(algebra::Series<W, M>),
00085                              SELECTOR2(rat::exp<Tm, Tw>));
00086 
00087 
00088     template<typename W, typename M, typename Tm, typename Tw>
00089     const rat::exp<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
00090                                        SELECTOR2(rat::exp<Tm, Tw>));
00091 
00092 
00093     template<typename W, typename M, typename Tm, typename Tw>
00094     void op_in_add(const algebra::Series<W, M>& s,
00095                    rat::exp<Tm, Tw>& dst,
00096                    const rat::exp<Tm, Tw>& arg);
00097 
00098     template<typename W, typename M, typename Tm, typename Tw>
00099     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00100                             const rat::exp<Tm, Tw>& a,
00101                             const rat::exp<Tm, Tw>& b);
00102 
00103     template<typename W, typename M, typename Tm, typename Tw>
00104     void op_in_mul(const algebra::Series<W, M>& s,
00105                    rat::exp<Tm, Tw>& dst,
00106                    const rat::exp<Tm, Tw>& arg);
00107 
00108     template<typename W, typename M, typename Tm, typename Tw>
00109     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00110                             const rat::exp<Tm, Tw>& a,
00111                             const rat::exp<Tm, Tw>& b);
00112 
00113 
00114     /*---------------------.
00115     | foreign constructors |
00116     `---------------------*/
00117 
00118     template<typename Tm, typename Tw, typename M, typename W>
00119     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00120                                 SELECTOR2(rat::exp<Tm, Tw>),
00121                                 const Tm& m_value);
00122 
00123     template<typename Tm, typename Tw, typename M, typename W>
00124     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00125                                 SELECTOR2(rat::exp<Tm, Tw>),
00126                                 char m_value);
00127 
00128     template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00129     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00130                                 SELECTOR2(rat::exp<Tm, Tw>),
00131                                 SELECTOR(M),
00132                                 const oTm& m_value);
00133 
00134     template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00135     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00136                                 SELECTOR2(rat::exp<Tm, Tw>),
00137                                 SELECTOR(W),
00138                                 const oTw& w_value);
00139 
00140     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00141     void op_assign(const algebra::Series<W, M>& s,
00142                    const M& monoid,
00143                    rat::exp<Tm, Tw>& dst,
00144                    const oTm& src);
00145 
00146     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00147     void op_assign(const algebra::Series<W, M>& s,
00148                    const W& semiring,
00149                    rat::exp<Tm, Tw>& dst,
00150                    const oTw& src);
00151 
00152     /*-----.
00153     | star |
00154     `-----*/
00155 
00156     template<typename W, typename M, typename Tm, typename Tw>
00157     bool op_starable(const algebra::Series<W, M>& s,
00158                       const rat::exp<Tm, Tw>& dst);
00159 
00160     template<typename W, typename M, typename Tm, typename Tw>
00161     void op_in_star(const algebra::Series<W, M>& s,
00162                     rat::exp<Tm, Tw>& dst);
00163 
00164     template<typename W, typename M, typename Tm, typename Tw>
00165     rat::exp<Tm, Tw>
00166     op_star(const algebra::Series<W, M>& s,
00167             const rat::exp<Tm, Tw>& src);
00168 
00169   } // algebra
00170 
00171     /*--------------------------------------.
00172     | foreign addition with monoid elements |
00173     `--------------------------------------*/
00174 
00175   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00176   struct op_add_traits<M, algebra::Series<W, M>, oTm, rat::exp<Tm, Tw> >
00177   {
00178     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00179   };
00180 
00181   namespace algebra {
00182 
00183     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00184     void op_in_add(const algebra::Series<W, M>& s,
00185                    const M& monoid,
00186                    rat::exp<Tm, Tw>& dst,
00187                    const oTm& src);
00188 
00189     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00190     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00191                             const M& monoid,
00192                             const rat::exp<Tm, Tw>& a,
00193                             const oTm& b);
00194 
00195     template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00196     rat::exp<Tm, Tw> op_add(const M& monoid,
00197                             const algebra::Series<W, M>& s,
00198                             const oTm& a,
00199                             const rat::exp<Tm, Tw>& b);
00200 
00201   }
00202 
00203   /*---------------------------------------.
00204   | foreign addition with semiring elements |
00205   `---------------------------------------*/
00206 
00207   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00208   struct op_add_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00209   {
00210     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00211   };
00212 
00213   namespace algebra {
00214 
00215     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00216     void op_in_add(const algebra::Series<W, M>& s,
00217                    const W& semiring,
00218                    rat::exp<Tm, Tw>& dst,
00219                    const oTw& src);
00220 
00221     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00222     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00223                             const W& semiring,
00224                             const rat::exp<Tm, Tw>& a,
00225                             const oTw& b);
00226 
00227     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00228     rat::exp<Tm, Tw> op_add(const W& semiring,
00229                             const algebra::Series<W, M>& s,
00230                             const oTw& a,
00231                             const rat::exp<Tm, Tw>& b);
00232 
00233   }
00234 
00235   /*-------------------------------------------.
00236   | foreign multiplication by semiring elements |
00237   `-------------------------------------------*/
00238 
00239   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00240   struct op_mul_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00241   {
00242     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00243   };
00244 
00245   namespace algebra {
00246 
00247     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00248     void op_in_mul(const algebra::Series<W, M>& s,
00249                    const W& semiring,
00250                    rat::exp<Tm, Tw>& ret,
00251                    const oTw& w);
00252 
00253     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00254     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00255                             const W& semiring,
00256                             const rat::exp<Tm, Tw>& a,
00257                             const oTw& w);
00258 
00259     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00260     rat::exp<Tm, Tw> op_mul(const W& semiring,
00261                             const algebra::Series<W, M>& s,
00262                             const oTw& w,
00263                             const rat::exp<Tm, Tw>& b);
00264 
00265     /*---------------.
00266     | Series methods |
00267     `---------------*/
00268     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00269     Tw op_series_get(const algebra::Series<W, M>& s,
00270                      const rat::exp<Tm, Tw>& p,
00271                      const oTm& m);
00272 
00273     template<typename W, typename M, typename Tm,
00274              typename Tw, typename oTm, typename oTw>
00275     void op_series_set(const algebra::Series<W, M>& s,
00276                        const rat::exp<Tm, Tw>& p,
00277                        const oTm& m,
00278                        const oTw& w);
00279 
00280     template <class W, class M, class Tm, class Tw>
00281     Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00282     op_choose(const algebra::Series<W,M>& s,
00283               SELECTOR2(rat::exp<Tm,Tw>));
00284 
00285     template <typename W, typename M, typename Tm, typename Tw, typename St>
00286     St&
00287     op_rout(const algebra::Series<W, M>&,
00288             St& st,
00289             const rat::exp<Tm, Tw>&);
00290 
00291     /*----------.
00292     | Transpose |
00293     `----------*/
00294 
00295     template <typename W, typename M, typename Tm, typename Tw>
00296     void op_in_transpose(const algebra::Series<W, M>& s,
00297                          rat::exp<Tm, Tw>& dst);
00298 
00299 
00300   } // algebra
00301 
00302   template<typename W, typename M, typename Tm, typename Tw>
00303   struct semiring_traits<algebra::Series<W, M>, rat::exp<Tm, Tw> >
00304   {
00305     enum { is_positive = 1 };
00306   };
00307 
00308 } // vcsn
00309 
00310 
00311 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00312 # include <vaucanson/algebra/implementation/series/krat.hxx>
00313 #endif // VCSN_USE_INTERFACE_ONLY
00314 
00315 
00316 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HH