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 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> >, rat::exp<Tm, Tw> >
00056   {
00057     static const bool dynamic_value = true;
00058 
00059     void        accept(const rat::ConstNodeVisitor<Tm, Tw>& v) const;
00060     size_t      depth() const;
00061   };
00062 
00063 
00064   template<typename W, typename M, typename Tm, typename Tw>
00065   bool op_contains(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m);
00066 
00067   template<typename W, typename M, typename Tm, typename Tw>
00068   bool op_is_finite_app(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m);
00069 
00070   template <typename W, typename M, typename Tm, typename Tw>
00071   Tm op_choose_from_supp(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m);
00072 
00073   template<typename W, typename M, typename Tm, typename Tw>
00074   const rat::exp<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
00075                                          SELECTOR2(rat::exp<Tm, Tw>));
00076 
00077   template<typename W, typename M, typename Tm, typename Tw>
00078   const rat::exp<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
00079                                      SELECTOR2(rat::exp<Tm, Tw>));
00080 
00081 
00082   template<typename W, typename M, typename Tm, typename Tw>
00083   void op_in_add(const algebra::Series<W, M>& s,
00084                  rat::exp<Tm, Tw>& dst,
00085                  const rat::exp<Tm, Tw>& arg);
00086 
00087   template<typename W, typename M, typename Tm, typename Tw>
00088   rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00089                           const rat::exp<Tm, Tw>& a,
00090                           const rat::exp<Tm, Tw>& b);
00091 
00092   template<typename W, typename M, typename Tm, typename Tw>
00093   void op_in_mul(const algebra::Series<W, M>& s,
00094                  rat::exp<Tm, Tw>& dst,
00095                  const rat::exp<Tm, Tw>& arg);
00096 
00097   template<typename W, typename M, typename Tm, typename Tw>
00098   rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00099                           const rat::exp<Tm, Tw>& a,
00100                           const rat::exp<Tm, Tw>& b);
00101 
00102 
00103   /*---------------------.
00104   | foreign constructors |
00105   `---------------------*/
00106 
00107   template<typename Tm, typename Tw, typename M, typename W>
00108   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00109                               SELECTOR2(rat::exp<Tm, Tw>),
00110                               const Tm& m_value);
00111 
00112   template<typename Tm, typename Tw, typename M, typename W>
00113   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00114                               SELECTOR2(rat::exp<Tm, Tw>),
00115                               char m_value);
00116 
00117   template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00118   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00119                               SELECTOR2(rat::exp<Tm, Tw>),
00120                               SELECTOR(M),
00121                               const oTm& m_value);
00122 
00123   template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00124   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00125                               SELECTOR2(rat::exp<Tm, Tw>),
00126                               SELECTOR(W),
00127                               const oTw& w_value);
00128 
00129   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00130   void op_assign(const algebra::Series<W, M>& s,
00131                  const M& monoid,
00132                  rat::exp<Tm, Tw>& dst,
00133                  const oTm& src);
00134 
00135   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00136   void op_assign(const algebra::Series<W, M>& s,
00137                  const W& semiring,
00138                  rat::exp<Tm, Tw>& dst,
00139                  const oTw& src);
00140 
00141   /*-----.
00142   | star |
00143   `-----*/
00144 
00145   template<typename W, typename M, typename Tm, typename Tw>
00146   bool op_starable(const algebra::Series<W, M>& s,
00147                     const rat::exp<Tm, Tw>& dst);
00148 
00149   template<typename W, typename M, typename Tm, typename Tw>
00150   void op_in_star(const algebra::Series<W, M>& s,
00151                   rat::exp<Tm, Tw>& dst);
00152 
00153   template<typename W, typename M, typename Tm, typename Tw>
00154   rat::exp<Tm, Tw>
00155   op_star(const algebra::Series<W, M>& s,
00156           const rat::exp<Tm, Tw>& src);
00157 
00158   /*--------------------------------------.
00159   | foreign addition with monoid elements |
00160   `--------------------------------------*/
00161 
00162   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00163   struct op_add_traits<M, algebra::Series<W, M>, oTm, rat::exp<Tm, Tw> >
00164   {
00165     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00166   };
00167 
00168   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00169   void op_in_add(const algebra::Series<W, M>& s,
00170                  const M& monoid,
00171                  rat::exp<Tm, Tw>& dst,
00172                  const oTm& src);
00173 
00174   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00175   rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00176                           const M& monoid,
00177                           const rat::exp<Tm, Tw>& a,
00178                           const oTm& b);
00179 
00180   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00181   rat::exp<Tm, Tw> op_add(const M& monoid,
00182                           const algebra::Series<W, M>& s,
00183                           const oTm& a,
00184                           const rat::exp<Tm, Tw>& b);
00185 
00186   /*---------------------------------------.
00187   | foreign addition with semiring elements |
00188   `---------------------------------------*/
00189 
00190 
00191   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00192   struct op_add_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00193   {
00194     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00195   };
00196 
00197   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00198   void op_in_add(const algebra::Series<W, M>& s,
00199                  const W& semiring,
00200                  rat::exp<Tm, Tw>& dst,
00201                  const oTw& src);
00202 
00203   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00204   rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00205                           const W& semiring,
00206                           const rat::exp<Tm, Tw>& a,
00207                           const oTw& b);
00208 
00209   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00210   rat::exp<Tm, Tw> op_add(const W& semiring,
00211                           const algebra::Series<W, M>& s,
00212                           const oTw& a,
00213                           const rat::exp<Tm, Tw>& b);
00214 
00215   /*-------------------------------------------.
00216   | foreign multiplication by semiring elements |
00217   `-------------------------------------------*/
00218 
00219   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00220   struct op_mul_traits<W, algebra::Series<W, M>, oTw, rat::exp<Tm, Tw> >
00221   {
00222     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > ret_t;
00223   };
00224 
00225 
00226   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00227   void op_in_mul(const algebra::Series<W, M>& s,
00228                  const W& semiring,
00229                  rat::exp<Tm, Tw>& ret,
00230                  const oTw& w);
00231 
00232   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00233   rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00234                           const W& semiring,
00235                           const rat::exp<Tm, Tw>& a,
00236                           const oTw& w);
00237 
00238   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00239   rat::exp<Tm, Tw> op_mul(const W& semiring,
00240                           const algebra::Series<W, M>& s,
00241                           const oTw& w,
00242                           const rat::exp<Tm, Tw>& b);
00243 
00244   /*---------------.
00245   | Series methods |
00246   `---------------*/
00247   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00248   Tw op_series_get(const algebra::Series<W, M>& s,
00249                    const rat::exp<Tm, Tw>& p,
00250                    const oTm& m);
00251 
00252   template<typename W, typename M, typename Tm,
00253            typename Tw, typename oTm, typename oTw>
00254   void op_series_set(const algebra::Series<W, M>& s,
00255                      const rat::exp<Tm, Tw>& p,
00256                      const oTm& m,
00257                      const oTw& w);
00258 
00259   template <class W, class M, class Tm, class Tw>
00260   Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00261   op_choose(const algebra::Series<W,M>& s,
00262             SELECTOR2(rat::exp<Tm,Tw>));
00263 
00264   /*----------.
00265   | Transpose |
00266   `----------*/
00267 
00268   template <typename W, typename M, typename Tm, typename Tw>
00269   void op_in_transpose(const algebra::Series<W, M>& s,
00270                        rat::exp<Tm, Tw>& dst);
00271 
00272 
00273 } // vcsn
00274 
00275 
00276 #ifndef VCSN_USE_INTERFACE_ONLY
00277     # include <vaucanson/algebra/implementation/series/krat.hxx>
00278 #endif // VCSN_USE_INTERFACE_ONLY
00279 
00280 
00281 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HH