Vaucanson: polynoms.hh Source File

00001 // polynoms.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 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_POLYNOMS_HH
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH
00019 
00020 # include <vaucanson/design_pattern/design_pattern.hh>
00021 # include <vaucanson/algebra/implementation/series/series.hh>
00022 # include <vaucanson/algebra/implementation/series/transpose.hh>
00023 # include <vaucanson/misc/support.hh>
00024 
00025 # include <map>
00026 # include <utility>
00027 
00028 namespace vcsn {
00029 
00030   namespace algebra  {
00031 
00032     /*----------------.
00033       | polynom<Tm, Tw> |
00034       `----------------*/
00035 
00036     template<typename Tm, typename Tw>
00037     class polynom
00038     {
00039     public:
00040       typedef Tm        monoid_elt_value_t;
00041       typedef Tw        semiring_elt_value_t;
00042 
00043       typedef typename std::map<Tm, Tw>::const_iterator const_iterator;
00044       typedef typename std::map<Tm, Tw>::iterator       iterator;
00045 
00046       template<typename M, typename W>
00047       polynom(SELECTOR(M), SELECTOR(W));
00048       polynom(const polynom& other);
00049       polynom();
00050 
00051       size_t            size() const;
00052       bool              empty() const;
00053 
00054       iterator          begin();
00055       const_iterator    begin() const;
00056 
00057       iterator          end();
00058       const_iterator    end() const;
00059 
00060       iterator          find(const Tm& m);
00061       const_iterator    find(const Tm& m) const;
00062 
00063       template<typename W>
00064       Tw&               make_get(SELECTOR(W), const Tm& m);
00065       template<typename W>
00066       Tw                get(SELECTOR(W), const Tm& m) const;
00067 
00068       void              insert(const Tm& m, const Tw& w);
00069 
00070       template<typename W>
00071       void              add(const W& semiring, const Tm& m, const Tw& w);
00072       void              erase(iterator i);
00073       void              clear();
00074       void              swap(polynom<Tm, Tw>& other);
00075 
00076       const std::map<Tm, Tw>&
00077       as_map() const;
00078 
00079       const Tw&
00080       operator [] (const Tm& m) const;
00081 
00082       Tw&
00083       operator [] (const Tm& m);
00084 
00085     protected:
00086       std::map<Tm, Tw> map_;
00087     };
00088 
00089     template<typename Tm, typename Tw>
00090     struct series_traits<polynom<Tm, Tw> >
00091     {
00092       typedef Tm monoid_elt_value_t;
00093       typedef Tw semiring_elt_value_t;
00094       typedef utility::Support<std::map<Tm, Tw> > support_t;
00095     };
00096 
00097     template <class Tm, class Tw, class W, class M>
00098     struct mute_series_impl<polynom<Tm, Tw>, W, M>
00099     {
00100       typedef polynom<M, W>     ret;
00101     };
00102 
00103     template <class Series, class Tm, class Tw>
00104     struct DefaultTransposeFun<Series, polynom<Tm,Tw> >
00105     {
00106       polynom<Tm,Tw>
00107       operator()(const Series& s, const polynom<Tm,Tw>& l) const;
00108     protected:
00109       template <class S>
00110       static
00111       Tw transpose(const SeriesBase<S>& s, const Tw& w);
00112 
00113       template <class S>
00114       static
00115       Tw transpose(const SemiringBase<S>& s, const Tw& w);
00116     };
00117 
00118     template <class Tm, class Tw>
00119     bool operator==(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00120 
00121     template <class Tm, class Tw>
00122     bool operator!=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00123 
00124     template <class Tm, class Tw>
00125     bool operator<(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00126 
00127     template <class Tm, class Tw>
00128     bool operator>(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00129 
00130     template <class Tm, class Tw>
00131     bool operator<=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00132 
00133     template <class Tm, class Tw>
00134     bool operator>=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
00135 
00136 
00137   } // algebra
00138 
00139   template<typename W, typename M, typename Tm, typename Tw>
00140   bool op_contains(const algebra::Series<W, M>& s, const algebra::polynom<Tm, Tw>& m);
00141 
00142   template<typename Self, typename Tm, typename Tw>
00143   void op_in_star(const algebra::SeriesBase<Self>& s,
00144                   algebra::polynom<Tm, Tw>& m);
00145 
00146   template<typename W, typename M, typename Tm, typename Tw>
00147   bool op_is_finite_app(const algebra::Series<W, M>& s, const algebra::polynom<Tm, Tw>& m);
00148 
00149   template<typename W, typename M, typename Tm, typename Tw>
00150   const algebra::polynom<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
00151                                                  SELECTOR2(algebra::polynom<Tm, Tw>));
00152 
00153   template<typename W, typename M, typename Tm, typename Tw>
00154   const algebra::polynom<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
00155                                              SELECTOR2(algebra::polynom<Tm, Tw>));
00156 
00157   template<typename W, typename M, typename Tm, typename Tw>
00158   void op_in_add(const algebra::Series<W, M>& s,
00159                  algebra::polynom<Tm, Tw>& dst,
00160                  const algebra::polynom<Tm, Tw>& arg);
00161 
00162   template<typename W, typename M, typename Tm, typename Tw>
00163   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00164                                   const algebra::polynom<Tm, Tw>& a,
00165                                   const algebra::polynom<Tm, Tw>& b);
00166 
00167   /*-----------------.
00168     | cauchy's product |
00169     `-----------------*/
00170   template<typename W, typename M, typename Tm, typename Tw>
00171   algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00172                                   const algebra::polynom<Tm, Tw>& a,
00173                                   const algebra::polynom<Tm, Tw>& b);
00174 
00175   template<typename W, typename M, typename Tm, typename Tw>
00176   void op_in_mul(const algebra::Series<W, M>& s,
00177                  algebra::polynom<Tm, Tw>& dst,
00178                  const algebra::polynom<Tm, Tw>& arg);
00179 
00180   /*---------------------.
00181     | foreign constructors |
00182     `---------------------*/
00183 
00184   template <typename Tm, typename Tw, typename W, typename M>
00185   algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00186                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00187                                       const Tm& m_value);
00188 
00189   template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00190   algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00191                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00192                                       SELECTOR(algebra::MonoidBase<M>),
00193                                       const oTm& m_value);
00194 
00195   template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00196   algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00197                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00198                                       SELECTOR(algebra::SemiringBase<W>),
00199                                       const oTw& w_value);
00200 
00201   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00202   void op_assign(const algebra::Series<W, M>& s,
00203                  const algebra::MonoidBase<M>& monoid,
00204                  algebra::polynom<Tm, Tw>& dst,
00205                  const oTm& src);
00206 
00207   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00208   void op_assign(const algebra::Series<W, M>& s,
00209                  const algebra::SemiringBase<W>& semiring,
00210                  algebra::polynom<Tm, Tw>& dst,
00211                  const oTw& src);
00212 
00213   /*--------------------------------------.
00214     | foreign addition with monoid elements |
00215     `--------------------------------------*/
00216 
00217   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00218   void op_in_add(const algebra::Series<W, M>& s,
00219                  const algebra::MonoidBase<M>& monoid,
00220                  algebra::polynom<Tm, Tw>& dst,
00221                  const oTm& src);
00222 
00223   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00224   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00225                                   const algebra::MonoidBase<M>& monoid,
00226                                   const algebra::polynom<Tm, Tw>& a,
00227                                   const oTm& b);
00228 
00229 
00230   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00231   struct op_add_traits<M, algebra::Series<W, M>, oTm, algebra::polynom<Tm, Tw> >
00232   {
00233     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00234   };
00235 
00236   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00237   algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
00238                                   const algebra::Series<W, M>& s,
00239                                   const oTm& a,
00240                                   const algebra::polynom<Tm, Tw>& b);
00241 
00242   /*---------------------------------------.
00243     | foreign addition with semiring elements |
00244     `---------------------------------------*/
00245 
00246   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00247   void op_in_add(const algebra::Series<W, M>& s,
00248                  const algebra::SemiringBase<W>& semiring,
00249                  algebra::polynom<Tm, Tw>& dst,
00250                  const oTw& src);
00251 
00252   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00253   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00254                                   const algebra::SemiringBase<W>& semiring,
00255                                   const algebra::polynom<Tm, Tw>& a,
00256                                   const oTw& b);
00257 
00258   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00259   struct op_add_traits<W, algebra::Series<W, M>, oTw, algebra::polynom<Tm, Tw> >
00260   {
00261     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00262   };
00263 
00264   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00265   algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
00266                                   const algebra::Series<W, M>& s,
00267                                   const oTw& a,
00268                                   const algebra::polynom<Tm, Tw>& b);
00269 
00270   /*-------------------------------------------.
00271     | foreign multiplication by semiring elements |
00272     `-------------------------------------------*/
00273 
00274   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00275   void op_in_mul(const algebra::Series<W, M>& s,
00276                  const algebra::SemiringBase<W>& semiring,
00277                  algebra::polynom<Tm, Tw>& dst,
00278                  const oTw& src);
00279 
00280   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00281   algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00282                                   const algebra::SemiringBase<W>& semiring,
00283                                   const algebra::polynom<Tm, Tw>& a,
00284                                   const oTw& b);
00285 
00286   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00287   struct op_mul_traits<W, algebra::Series<W, M>, oTw, algebra::polynom<Tm, Tw> >
00288   {
00289     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00290   };
00291 
00292   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00293   algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
00294                                   const algebra::Series<W, M>& s,
00295                                   const oTw& a,
00296                                   const algebra::polynom<Tm, Tw>& b);
00297 
00298   /*----------.
00299     | transpose |
00300     `----------*/
00301   template <typename W, typename M, typename Tm, typename Tw>
00302   void  op_in_transpose(const algebra::Series<W, M>& s, algebra::polynom<Tm, Tw>& t);
00303 
00304   /*-------------.
00305     | input-output |
00306     `-------------*/
00307 
00308   template<typename W, typename M, typename St, typename Tm, typename Tw>
00309   St& op_rout(const algebra::Series<W, M>& s, St& st, const algebra::polynom<Tm, Tw>& p);
00310 
00311   /*---------------.
00312     | specialization |
00313     `---------------*/
00314 
00315   template<typename W, typename M, typename Tm, typename Tw>
00316   struct MetaElement<algebra::Series<W, M>, algebra::polynom<Tm, Tw> >
00317     : public MetaElement<algebra::SeriesBase<algebra::Series<W, M> >, algebra::polynom<Tm, Tw> >
00318   {
00319     static const bool dynamic_value = true;
00320   };
00321 
00322   /*------------------------------.
00323     | design_pattern series operations |
00324     `------------------------------*/
00325 
00326   template <class W, class M, class Tm, class Tw>
00327   Tm op_choose_from_supp(const algebra::Series<W, M>& s,
00328                          const algebra::polynom<Tm, Tw>& p);
00329 
00330   template<typename W, typename M, typename Tm, typename Tw>
00331   typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
00332   op_support(const algebra::Series<W, M>& s, const algebra::polynom<Tm, Tw>& m);
00333 
00334   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00335   Tw op_series_get(const algebra::Series<W, M>& s,
00336                    const algebra::polynom<Tm, Tw>& p,
00337                    const oTm& m);
00338 
00339   template<typename W, typename M,
00340            typename Tm, typename Tw,
00341            typename oTm, typename oTw>
00342   void op_series_set(const algebra::Series<W, M>& s,
00343                      algebra::polynom<Tm, Tw>& p,
00344                      const oTm& m,
00345                      const oTw& w);
00346 
00347   template <class W, class M, class Tm, class Tw>
00348   Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
00349   op_choose(const algebra::Series<W,M>& s,
00350             SELECTOR2(algebra::polynom<Tm,Tw>));
00351 
00352 } // vcsn
00353 
00354 namespace std {
00355 
00356   template <class Tm, class Tw>
00357   std::ostream& operator<<(std::ostream& out,
00358                            const vcsn::algebra::polynom<Tm, Tw>& p);
00359 
00360 } // std
00361 
00362 
00363 
00364 #ifndef VCSN_USE_INTERFACE_ONLY
00365     # include <vaucanson/algebra/implementation/series/polynoms.hxx>
00366 #endif // VCSN_USE_INTERFACE_ONLY
00367 
00368 
00369 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH