Vaucanson  1.4.1
polynoms.hh
1 // polynoms.hh: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2010 The
6 // Vaucanson Group.
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12 //
13 // The complete GNU General Public Licence Notice can be found as the
14 // `COPYING' file in the root directory.
15 //
16 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
17 //
18 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH
19 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH
20 
21 # include <vaucanson/design_pattern/design_pattern.hh>
22 # include <vaucanson/algebra/implementation/series/series.hh>
23 # include <vaucanson/algebra/implementation/series/transpose.hh>
24 # include <vaucanson/misc/support.hh>
25 
26 # include <map>
27 # include <utility>
28 
29 namespace vcsn
30 {
31  namespace algebra
32  {
33  /*----------------.
34  | polynom<Tm, Tw> |
35  `----------------*/
36 
37  template<typename Tm, typename Tw>
38  class polynom
39  {
40  public:
41  typedef Tm monoid_elt_value_t;
42  typedef Tw semiring_elt_value_t;
43 
44  typedef typename std::map<Tm, Tw>::const_iterator const_iterator;
45  typedef typename std::map<Tm, Tw>::iterator iterator;
46 
47  template<typename M, typename W>
48  polynom(SELECTOR(M), SELECTOR(W));
49  polynom(const polynom& other);
50  polynom();
51 
52  size_t size() const;
53  bool empty() const;
54 
55  iterator begin();
56  const_iterator begin() const;
57 
58  iterator end();
59  const_iterator end() const;
60 
61  iterator find(const Tm& m);
62  const_iterator find(const Tm& m) const;
63 
64  template<typename W>
65  Tw& make_get(SELECTOR(W), const Tm& m);
66  template<typename W>
67  Tw get(SELECTOR(W), const Tm& m) const;
68 
69  void insert(const Tm& m, const Tw& w);
70 
71  template<typename W>
72  void add(const W& semiring, const Tm& m, const Tw& w);
73  void erase(iterator i);
74  void clear();
75  void swap(polynom<Tm, Tw>& other);
76 
77  const std::map<Tm, Tw>&
78  as_map() const;
79 
80  const Tw&
81  operator [] (const Tm& m) const;
82 
83  Tw&
84  operator [] (const Tm& m);
85 
86  protected:
87  std::map<Tm, Tw> map_;
88  };
89 
90  template<typename Tm, typename Tw>
91  struct series_traits<polynom<Tm, Tw> >
92  {
93  typedef Tm monoid_elt_value_t;
94  typedef Tw semiring_elt_value_t;
95  typedef misc::Support<std::map<Tm, Tw> > support_t;
96  };
97 
98  template <class Tm, class Tw, class W, class M>
99  struct mute_series_impl<polynom<Tm, Tw>, W, M>
100  {
101  typedef polynom<M, W> ret;
102  };
103 
104  template <class Series, class Tm, class Tw>
105  struct DefaultTransposeFun<Series, polynom<Tm,Tw> >
106  {
107  polynom<Tm,Tw>
108  operator()(const Series& s, const polynom<Tm,Tw>& l) const;
109  protected:
110  template <class S>
111  static
112  Tw transpose(const SeriesBase<S>& s, const Tw& w);
113 
114  template <class S>
115  static
116  Tw transpose(const SemiringBase<S>& s, const Tw& w);
117  };
118 
119  template <class Tm, class Tw>
120  bool operator==(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
121 
122  template <class Tm, class Tw>
123  bool operator!=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
124 
125  template <class Tm, class Tw>
126  bool operator<(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
127 
128  template <class Tm, class Tw>
129  bool operator>(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
130 
131  template <class Tm, class Tw>
132  bool operator<=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
133 
134  template <class Tm, class Tw>
135  bool operator>=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs);
136 
137  template<typename W, typename M, typename Tm, typename Tw>
138  bool op_contains(const algebra::Series<W, M>& s,
139  const algebra::polynom<Tm, Tw>& m);
140 
141  template<typename Self, typename Tm, typename Tw>
142  void op_in_star(const algebra::SeriesBase<Self>& s,
143  algebra::polynom<Tm, Tw>& m);
144 
145  template<typename Self, typename Tm, typename Tw>
146  bool op_starable(const algebra::SeriesBase<Self>& s,
147  const algebra::polynom<Tm, Tw>& b);
148 
149  template<typename W, typename M, typename Tm, typename Tw>
150  bool op_is_finite_app(const algebra::Series<W, M>& s,
151  const algebra::polynom<Tm, Tw>& m);
152 
153  template<typename W, typename M, typename Tm, typename Tw>
154  const algebra::polynom<Tm, Tw>&
155  identity_value(SELECTOR2(algebra::Series<W, M>),
156  SELECTOR2(algebra::polynom<Tm, Tw>));
157 
158  template<typename W, typename M, typename Tm, typename Tw>
159  const algebra::polynom<Tm, Tw>&
160  zero_value(SELECTOR2(algebra::Series<W, M>),
161  SELECTOR2(algebra::polynom<Tm, Tw>));
162 
163  template<typename W, typename M, typename Tm, typename Tw>
164  void op_in_add(const algebra::Series<W, M>& s,
165  algebra::polynom<Tm, Tw>& dst,
166  const algebra::polynom<Tm, Tw>& arg);
167 
168  template<typename W, typename M, typename Tm, typename Tw>
169  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
170  const algebra::polynom<Tm, Tw>& a,
171  const algebra::polynom<Tm, Tw>& b);
172 
173  /*-------------------.
174  | Cauchy's product. |
175  `-------------------*/
176 
177  template<typename W, typename M, typename Tm, typename Tw>
178  algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
179  const algebra::polynom<Tm, Tw>& a,
180  const algebra::polynom<Tm, Tw>& b);
181 
182  template<typename W, typename M, typename Tm, typename Tw>
183  void op_in_mul(const algebra::Series<W, M>& s,
184  algebra::polynom<Tm, Tw>& dst,
185  const algebra::polynom<Tm, Tw>& arg);
186 
187  /*-----------------------.
188  | foreign constructors. |
189  `-----------------------*/
190 
191  template <typename Tm, typename Tw, typename W, typename M>
192  algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
193  SELECTOR2(algebra::polynom<Tm, Tw>),
194  const Tm& m_value);
195 
196  template<typename Tm, typename Tw, typename W, typename M, typename oTm>
197  algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
198  SELECTOR2(algebra::polynom<Tm, Tw>),
199  SELECTOR(algebra::MonoidBase<M>),
200  const oTm& m_value);
201 
202  template<typename Tm, typename Tw, typename W, typename M, typename oTw>
203  algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
204  SELECTOR2(algebra::polynom<Tm, Tw>),
205  SELECTOR(algebra::SemiringBase<W>),
206  const oTw& w_value);
207 
208  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
209  void op_assign(const algebra::Series<W, M>& s,
210  const algebra::MonoidBase<M>& monoid,
211  algebra::polynom<Tm, Tw>& dst,
212  const oTm& src);
213 
214  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
215  void op_assign(const algebra::Series<W, M>& s,
216  const algebra::SemiringBase<W>& semiring,
217  algebra::polynom<Tm, Tw>& dst,
218  const oTw& src);
219 
220  /*----------------------------------------.
221  | foreign addition with monoid elements. |
222  `----------------------------------------*/
223 
224  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
225  void op_in_add(const algebra::Series<W, M>& s,
226  const algebra::MonoidBase<M>& monoid,
227  algebra::polynom<Tm, Tw>& dst,
228  const oTm& src);
229 
230  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
231  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
232  const algebra::MonoidBase<M>& monoid,
233  const algebra::polynom<Tm, Tw>& a,
234  const oTm& b);
235 
236 
237  } // ! algebra
238 
239  template<typename M, typename W, typename oTm, typename Tm, typename Tw>
240  struct op_add_traits<M, algebra::Series<W, M>,
241  oTm, algebra::polynom<Tm, Tw> >
242  {
243  typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
244  };
245 
246  namespace algebra
247  {
248  template<typename M, typename W, typename oTm, typename Tm, typename Tw>
249  algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
250  const algebra::Series<W, M>& s,
251  const oTm& a,
252  const algebra::polynom<Tm, Tw>& b);
253 
254  /*------------------------------------------.
255  | Foreign addition with semiring elements. |
256  `------------------------------------------*/
257 
258  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
259  void op_in_add(const algebra::Series<W, M>& s,
260  const algebra::SemiringBase<W>& semiring,
261  algebra::polynom<Tm, Tw>& dst,
262  const oTw& src);
263 
264  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
265  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
266  const algebra::SemiringBase<W>& semiring,
267  const algebra::polynom<Tm, Tw>& a,
268  const oTw& b);
269 
270  } // ! algebra
271 
272  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
273  struct op_add_traits<W, algebra::Series<W, M>,
274  oTw, algebra::polynom<Tm, Tw> >
275  {
276  typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
277  };
278 
279  namespace algebra
280  {
281  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
282  algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
283  const algebra::Series<W, M>& s,
284  const oTw& a,
285  const algebra::polynom<Tm, Tw>& b);
286 
287  /*----------------------------------------------.
288  | Foreign multiplication by semiring elements. |
289  `----------------------------------------------*/
290 
291  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
292  void op_in_mul(const algebra::Series<W, M>& s,
293  const algebra::SemiringBase<W>& semiring,
294  algebra::polynom<Tm, Tw>& dst,
295  const oTw& src);
296 
297  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
298  algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
299  const algebra::SemiringBase<W>& semiring,
300  const algebra::polynom<Tm, Tw>& a,
301  const oTw& b);
302 
303  } // ! algebra
304 
305  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
306  struct op_mul_traits<W, algebra::Series<W, M>,
307  oTw, algebra::polynom<Tm, Tw> >
308  {
309  typedef Element<algebra::Series<W, M>, algebra::polynom<Tm, Tw> > ret_t;
310  };
311 
312  namespace algebra
313  {
314  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
315  algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
316  const algebra::Series<W, M>& s,
317  const oTw& a,
318  const algebra::polynom<Tm, Tw>& b);
319 
320  /*-----------.
321  | Transpose. |
322  `-----------*/
323 
324  template <typename W, typename M, typename Tm, typename Tw>
325  void op_in_transpose(const algebra::Series<W, M>& s,
326  algebra::polynom<Tm, Tw>& t);
327 
328  /*--------------.
329  | input-output. |
330  `--------------*/
331 
332  template<typename W, typename M, typename St, typename Tm, typename Tw>
333  St& op_rout(const algebra::Series<W, M>& s, St& st,
334  const algebra::polynom<Tm, Tw>& p);
335 
336  } // ! algebra
337 
338  /*---------------.
339  | specialization |
340  `---------------*/
341 
342  template<typename W, typename M, typename Tm, typename Tw>
343  struct MetaElement<algebra::Series<W, M>, algebra::polynom<Tm, Tw> >
344  : public MetaElement<algebra::SeriesBase<algebra::Series<W, M> >,
345  algebra::polynom<Tm, Tw> >
346  {
347  static const bool dynamic_value = true;
348  };
349 
350  namespace algebra
351  {
352  /*---------------------------------.
353  | design_pattern series operations |
354  `---------------------------------*/
355 
356  template <class W, class M, class Tm, class Tw>
357  Tm op_choose_from_supp(const algebra::Series<W, M>& s,
358  const algebra::polynom<Tm, Tw>& p);
359 
360  template<typename W, typename M, typename Tm, typename Tw>
361  typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
362  op_support(const algebra::Series<W, M>& s,
363  const algebra::polynom<Tm, Tw>& m);
364 
365  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
366  Tw op_series_get(const algebra::Series<W, M>& s,
367  const algebra::polynom<Tm, Tw>& p,
368  const oTm& m);
369 
370  template<typename W, typename M,
371  typename Tm, typename Tw,
372  typename oTm, typename oTw>
373  void op_series_set(const algebra::Series<W, M>& s,
374  algebra::polynom<Tm, Tw>& p,
375  const oTm& m,
376  const oTw& w);
377 
378  template <class W, class M, class Tm, class Tw>
379  Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
380  op_choose(const algebra::Series<W,M>& s,
381  SELECTOR2(algebra::polynom<Tm,Tw>));
382 
383  } // ! algebra
384 
385 } // ! vcsn
386 
387 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
388 # include <vaucanson/algebra/implementation/series/polynoms.hxx>
389 #endif // VCSN_USE_INTERFACE_ONLY
390 
391 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HH
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1