|
Vaucanson 1.4
|
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
1.7.4