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 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     const rat::exp<Tm, Tw>& zero_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     void op_in_add(const algebra::Series<W, M>& s,
00090                    rat::exp<Tm, Tw>& dst,
00091                    const rat::exp<Tm, Tw>& arg);
00092 
00093     template<typename W, typename M, typename Tm, typename Tw>
00094     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00095                             const rat::exp<Tm, Tw>& a,
00096                             const rat::exp<Tm, Tw>& b);
00097 
00098     template<typename W, typename M, typename Tm, typename Tw>
00099     void op_in_mul(const algebra::Series<W, M>& s,
00100                    rat::exp<Tm, Tw>& dst,
00101                    const rat::exp<Tm, Tw>& arg);
00102 
00103     template<typename W, typename M, typename Tm, typename Tw>
00104     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00105                             const rat::exp<Tm, Tw>& a,
00106                             const rat::exp<Tm, Tw>& b);
00107 
00108 
00109     /*---------------------.
00110     | foreign constructors |
00111     `---------------------*/
00112 
00113     template<typename Tm, typename Tw, typename M, typename W>
00114     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00115                                 SELECTOR2(rat::exp<Tm, Tw>),
00116                                 const Tm& m_value);
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                                 char m_value);
00122 
00123     template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00124     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00125                                 SELECTOR2(rat::exp<Tm, Tw>),
00126                                 SELECTOR(M),
00127                                 const oTm& m_value);
00128 
00129     template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00130     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00131                                 SELECTOR2(rat::exp<Tm, Tw>),
00132                                 SELECTOR(W),
00133                                 const oTw& w_value);
00134 
00135     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00136     void op_assign(const algebra::Series<W, M>& s,
00137                    const M& monoid,
00138                    rat::exp<Tm, Tw>& dst,
00139                    const oTm& src);
00140 
00141     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00142     void op_assign(const algebra::Series<W, M>& s,
00143                    const W& semiring,
00144                    rat::exp<Tm, Tw>& dst,
00145                    const oTw& src);
00146 
00147     /*-----.
00148     | star |
00149     `-----*/
00150 
00151     template<typename W, typename M, typename Tm, typename Tw>
00152     bool op_starable(const algebra::Series<W, M>& s,
00153                       const rat::exp<Tm, Tw>& dst);
00154 
00155     template<typename W, typename M, typename Tm, typename Tw>
00156     void op_in_star(const algebra::Series<W, M>& s,
00157                     rat::exp<Tm, Tw>& dst);
00158 
00159     template<typename W, typename M, typename Tm, typename Tw>
00160     rat::exp<Tm, Tw>
00161     op_star(const algebra::Series<W, M>& s,
00162             const rat::exp<Tm, Tw>& src);
00163 
00164   } // algebra
00165 
00166     /*--------------------------------------.
00167     | foreign addition with monoid elements |
00168     `--------------------------------------*/
00169 
00170   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00171   struct op_add_traits<M, algebra::Series<W, M>, oTm, rat::exp<Tm, Tw> >
00172   {
00173     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00174   };
00175 
00176   namespace algebra {
00177 
00178     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00179     void op_in_add(const algebra::Series<W, M>& s,
00180                    const M& monoid,
00181                    rat::exp<Tm, Tw>& dst,
00182                    const oTm& src);
00183 
00184     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00185     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00186                             const M& monoid,
00187                             const rat::exp<Tm, Tw>& a,
00188                             const oTm& b);
00189 
00190     template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00191     rat::exp<Tm, Tw> op_add(const M& monoid,
00192                             const algebra::Series<W, M>& s,
00193                             const oTm& a,
00194                             const rat::exp<Tm, Tw>& b);
00195 
00196   }
00197 
00198   /*---------------------------------------.
00199   | foreign addition with semiring elements |
00200   `---------------------------------------*/
00201 
00202   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00203   struct op_add_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00204   {
00205     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00206   };
00207 
00208   namespace algebra {
00209 
00210     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00211     void op_in_add(const algebra::Series<W, M>& s,
00212                    const W& semiring,
00213                    rat::exp<Tm, Tw>& dst,
00214                    const oTw& src);
00215 
00216     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00217     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00218                             const W& semiring,
00219                             const rat::exp<Tm, Tw>& a,
00220                             const oTw& b);
00221 
00222     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00223     rat::exp<Tm, Tw> op_add(const W& semiring,
00224                             const algebra::Series<W, M>& s,
00225                             const oTw& a,
00226                             const rat::exp<Tm, Tw>& b);
00227 
00228   }
00229 
00230   /*-------------------------------------------.
00231   | foreign multiplication by semiring elements |
00232   `-------------------------------------------*/
00233 
00234   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00235   struct op_mul_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00236   {
00237     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00238   };
00239 
00240   namespace algebra {
00241 
00242     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00243     void op_in_mul(const algebra::Series<W, M>& s,
00244                    const W& semiring,
00245                    rat::exp<Tm, Tw>& ret,
00246                    const oTw& w);
00247 
00248     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00249     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00250                             const W& semiring,
00251                             const rat::exp<Tm, Tw>& a,
00252                             const oTw& w);
00253 
00254     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00255     rat::exp<Tm, Tw> op_mul(const W& semiring,
00256                             const algebra::Series<W, M>& s,
00257                             const oTw& w,
00258                             const rat::exp<Tm, Tw>& b);
00259 
00260     /*---------------.
00261     | Series methods |
00262     `---------------*/
00263     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00264     Tw op_series_get(const algebra::Series<W, M>& s,
00265                      const rat::exp<Tm, Tw>& p,
00266                      const oTm& m);
00267 
00268     template<typename W, typename M, typename Tm,
00269              typename Tw, typename oTm, typename oTw>
00270     void op_series_set(const algebra::Series<W, M>& s,
00271                        const rat::exp<Tm, Tw>& p,
00272                        const oTm& m,
00273                        const oTw& w);
00274 
00275     template <class W, class M, class Tm, class Tw>
00276     Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00277     op_choose(const algebra::Series<W,M>& s,
00278               SELECTOR2(rat::exp<Tm,Tw>));
00279 
00280     template <typename W, typename M, typename Tm, typename Tw, typename St>
00281     St&
00282     op_rout(const algebra::Series<W, M>&,
00283             St& st,
00284             const rat::exp<Tm, Tw>&);
00285 
00286     /*----------.
00287     | Transpose |
00288     `----------*/
00289 
00290     template <typename W, typename M, typename Tm, typename Tw>
00291     void op_in_transpose(const algebra::Series<W, M>& s,
00292                          rat::exp<Tm, Tw>& dst);
00293 
00294 
00295   } // algebra
00296 
00297 } // vcsn
00298 
00299 
00300 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00301 # include <vaucanson/algebra/implementation/series/krat.hxx>
00302 #endif // VCSN_USE_INTERFACE_ONLY
00303 
00304 
00305 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HH