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