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 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 misc::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     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 W, typename M, typename Tm, typename Tw>
00146     bool op_is_finite_app(const algebra::Series<W, M>& s,
00147                           const algebra::polynom<Tm, Tw>& m);
00148 
00149     template<typename W, typename M, typename Tm, typename Tw>
00150     const algebra::polynom<Tm, Tw>&
00151     identity_value(SELECTOR2(algebra::Series<W, M>),
00152                    SELECTOR2(algebra::polynom<Tm, Tw>));
00153 
00154     template<typename W, typename M, typename Tm, typename Tw>
00155     const algebra::polynom<Tm, Tw>&
00156     zero_value(SELECTOR2(algebra::Series<W, M>),
00157                SELECTOR2(algebra::polynom<Tm, Tw>));
00158 
00159     template<typename W, typename M, typename Tm, typename Tw>
00160     void op_in_add(const algebra::Series<W, M>& s,
00161                    algebra::polynom<Tm, Tw>& dst,
00162                    const algebra::polynom<Tm, Tw>& arg);
00163 
00164     template<typename W, typename M, typename Tm, typename Tw>
00165     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00166                                     const algebra::polynom<Tm, Tw>& a,
00167                                     const algebra::polynom<Tm, Tw>& b);
00168 
00169     /*-------------------.
00170     | Cauchy's product.  |
00171     `-------------------*/
00172     template<typename W, typename M, typename Tm, typename Tw>
00173     algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00174                                     const algebra::polynom<Tm, Tw>& a,
00175                                     const algebra::polynom<Tm, Tw>& b);
00176 
00177     template<typename W, typename M, typename Tm, typename Tw>
00178     void op_in_mul(const algebra::Series<W, M>& s,
00179                    algebra::polynom<Tm, Tw>& dst,
00180                    const algebra::polynom<Tm, Tw>& arg);
00181 
00182     /*-----------------------.
00183     | foreign constructors.  |
00184     `-----------------------*/
00185 
00186     template <typename Tm, typename Tw, typename W, typename M>
00187     algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00188                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00189                                         const Tm& m_value);
00190 
00191     template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00192     algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00193                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00194                                         SELECTOR(algebra::MonoidBase<M>),
00195                                         const oTm& m_value);
00196 
00197     template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00198     algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00199                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00200                                         SELECTOR(algebra::SemiringBase<W>),
00201                                         const oTw& w_value);
00202 
00203     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00204     void op_assign(const algebra::Series<W, M>& s,
00205                    const algebra::MonoidBase<M>& monoid,
00206                    algebra::polynom<Tm, Tw>& dst,
00207                    const oTm& src);
00208 
00209     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00210     void op_assign(const algebra::Series<W, M>& s,
00211                    const algebra::SemiringBase<W>& semiring,
00212                    algebra::polynom<Tm, Tw>& dst,
00213                    const oTw& src);
00214 
00215     /*----------------------------------------.
00216     | foreign addition with monoid elements.  |
00217     `----------------------------------------*/
00218 
00219     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00220     void op_in_add(const algebra::Series<W, M>& s,
00221                    const algebra::MonoidBase<M>& monoid,
00222                    algebra::polynom<Tm, Tw>& dst,
00223                    const oTm& src);
00224 
00225     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00226     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00227                                     const algebra::MonoidBase<M>& monoid,
00228                                     const algebra::polynom<Tm, Tw>& a,
00229                                     const oTm& b);
00230 
00231 
00232   } // algebra
00233 
00234   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00235   struct op_add_traits<M, algebra::Series<W, M>,
00236                        oTm, algebra::polynom<Tm, Tw> >
00237   {
00238     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00239   };
00240 
00241   namespace algebra {
00242 
00243     template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00244     algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
00245                                     const algebra::Series<W, M>& s,
00246                                     const oTm& a,
00247                                     const algebra::polynom<Tm, Tw>& b);
00248 
00249     /*------------------------------------------.
00250     | Foreign addition with semiring elements.  |
00251     `------------------------------------------*/
00252 
00253     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00254     void op_in_add(const algebra::Series<W, M>& s,
00255                    const algebra::SemiringBase<W>& semiring,
00256                    algebra::polynom<Tm, Tw>& dst,
00257                    const oTw& src);
00258 
00259     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00260     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00261                                     const algebra::SemiringBase<W>& semiring,
00262                                     const algebra::polynom<Tm, Tw>& a,
00263                                     const oTw& b);
00264 
00265   } // algebra
00266 
00267   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00268   struct op_add_traits<W, algebra::Series<W, M>,
00269                        oTw, algebra::polynom<Tm, Tw> >
00270   {
00271     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00272   };
00273 
00274   namespace algebra {
00275 
00276     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00277     algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
00278                                     const algebra::Series<W, M>& s,
00279                                     const oTw& a,
00280                                     const algebra::polynom<Tm, Tw>& b);
00281 
00282     /*----------------------------------------------.
00283     | Foreign multiplication by semiring elements.  |
00284     `----------------------------------------------*/
00285 
00286     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00287     void op_in_mul(const algebra::Series<W, M>& s,
00288                    const algebra::SemiringBase<W>& semiring,
00289                    algebra::polynom<Tm, Tw>& dst,
00290                    const oTw& src);
00291 
00292     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00293     algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00294                                     const algebra::SemiringBase<W>& semiring,
00295                                     const algebra::polynom<Tm, Tw>& a,
00296                                     const oTw& b);
00297 
00298   } // algebra
00299 
00300   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00301   struct op_mul_traits<W, algebra::Series<W, M>,
00302                        oTw, algebra::polynom<Tm, Tw> >
00303   {
00304     typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
00305   };
00306 
00307   namespace algebra {
00308 
00309     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00310     algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
00311                                     const algebra::Series<W, M>& s,
00312                                     const oTw& a,
00313                                     const algebra::polynom<Tm, Tw>& b);
00314 
00315     /*----------.
00316     | Transpose. |
00317     `----------*/
00318     template <typename W, typename M, typename Tm, typename Tw>
00319     void  op_in_transpose(const algebra::Series<W, M>& s,
00320                           algebra::polynom<Tm, Tw>& t);
00321 
00322     /*-------------.
00323     | input-output. |
00324     `-------------*/
00325 
00326     template<typename W, typename M, typename St, typename Tm, typename Tw>
00327     St& op_rout(const algebra::Series<W, M>& s, St& st,
00328                 const algebra::polynom<Tm, Tw>& p);
00329 
00330   } // algebra
00331 
00332   /*---------------.
00333   | specialization |
00334   `---------------*/
00335 
00336   template<typename W, typename M, typename Tm, typename Tw>
00337   struct MetaElement<algebra::Series<W, M>, algebra::polynom<Tm, Tw> >
00338     : public MetaElement<algebra::SeriesBase<algebra::Series<W, M> >,
00339                          algebra::polynom<Tm, Tw> >
00340   {
00341     static const bool dynamic_value = true;
00342   };
00343 
00344 
00345   namespace algebra {
00346 
00347     /*---------------------------------.
00348     | design_pattern series operations |
00349     `---------------------------------*/
00350 
00351     template <class W, class M, class Tm, class Tw>
00352     Tm op_choose_from_supp(const algebra::Series<W, M>& s,
00353                            const algebra::polynom<Tm, Tw>& p);
00354 
00355     template<typename W, typename M, typename Tm, typename Tw>
00356     typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
00357     op_support(const algebra::Series<W, M>& s,
00358                const algebra::polynom<Tm, Tw>& m);
00359 
00360     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00361     Tw op_series_get(const algebra::Series<W, M>& s,
00362                      const algebra::polynom<Tm, Tw>& p,
00363                      const oTm& m);
00364 
00365     template<typename W, typename M,
00366              typename Tm, typename Tw,
00367              typename oTm, typename oTw>
00368     void op_series_set(const algebra::Series<W, M>& s,
00369                        algebra::polynom<Tm, Tw>& p,
00370                        const oTm& m,
00371                        const oTw& w);
00372 
00373     template <class W, class M, class Tm, class Tw>
00374     Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
00375     op_choose(const algebra::Series<W,M>& s,
00376               SELECTOR2(algebra::polynom<Tm,Tw>));
00377 
00378   } // algebra
00379 
00380 } // vcsn
00381 
00382 namespace std {
00383 
00384   template <class Tm, class Tw>
00385   std::ostream& operator<<(std::ostream& out,
00386                            const vcsn::algebra::polynom<Tm, Tw>& p);
00387 
00388 } // std
00389 
00390 
00391 
00392 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00393 # include <vaucanson/algebra/implementation/series/polynoms.hxx>
00394 #endif // VCSN_USE_INTERFACE_ONLY
00395 
00396 
00397 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH