Vaucanson  1.4.1
partial_rat_exp.hxx
1 // partial_rat_exp.hxx: 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, 2008, 2009 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX
18 # define VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX
19 
20 # include <vaucanson/algorithms/internal/partial_rat_exp.hh>
21 
22 namespace vcsn
23 {
24  /*-----------------.
25  | PartialExp class |
26  `-----------------*/
27 
28  template <typename Series, typename T>
29  PartialExp<Series, T>::PartialExp(const exp_t &e):
30  rat_exp_(&e),
31  semiring_elt_list_(),
32  node_list_()
33  {
34  semiring_elt_list_.push_back(rat_exp_->structure().semiring().identity(
35  SELECT(typename semiring_elt_t::value_t)));
36  }
37 
38  template <typename Series, typename T>
39  PartialExp<Series, T>::PartialExp(const PartialExp &other):
40  rat_exp_(other.rat_exp_),
41  semiring_elt_list_(other.semiring_elt_list_),
42  node_list_(other.node_list_)
43  { }
44 
45  template <typename Series, typename T>
46  PartialExp<Series, T>::PartialExp(const exp_t &e, const semiring_elt_t& w):
47  rat_exp_(&e),
48  semiring_elt_list_(),
49  node_list_()
50  {
51  semiring_elt_list_.push_back(w);
52  }
53 
54 
55  template <typename Series, typename T>
56  template <typename M, typename W>
57  PartialExp<Series, T>&
58  PartialExp<Series, T>::insert(const rat::Node<M, W>* v)
59  {
60  // Break initial left products.
61  if (node_list_.empty() && v->what() == rat::Node<M, W>::prod)
62  {
63  const rat::Product<M, W>* p =
64  dynamic_cast<const rat::Product<M, W>*>(v);
65  insert(p->left_);
66 
67  v = p->right_;
68  }
69 
70  node_list_.push_back(v);
71  semiring_elt_list_.push_back(
72  rat_exp_->structure().semiring().
73  identity(SELECT(typename semiring_elt_t::value_t)));
74  return *this;
75  }
76 
77  template <typename Series, typename T>
78  typename PartialExp<Series, T>::semiring_elt_list_t&
79  PartialExp<Series, T>::weights()
80  {
81  return semiring_elt_list_;
82  }
83 
84  template <typename Series, typename T>
85  const typename PartialExp<Series, T>::semiring_elt_list_t&
86  PartialExp<Series, T>::weights() const
87  {
88  return semiring_elt_list_;
89  }
90 
91  template <typename Series, typename T>
92  const typename PartialExp<Series, T>::node_list_t&
93  PartialExp<Series, T>::nodes() const
94  {
95  return node_list_;
96  }
97 
98  template <typename Series, typename T>
99  typename PartialExp<Series, T>::node_list_t&
100  PartialExp<Series, T>::nodes()
101  {
102  return node_list_;
103  }
104 
105  template <typename Series, typename T>
106  PartialExp<Series, T>&
107  PartialExp<Series, T>::operator<<=(const semiring_elt_t& w)
108  {
109  semiring_elt_list_.back() *= w;
110  return *this;
111  }
112 
113  template <typename Series, typename T>
114  PartialExp<Series, T>&
115  PartialExp<Series, T>::operator>>=(const semiring_elt_t& w)
116  {
117  semiring_elt_list_.front() = w * semiring_elt_list_.front();
118  return *this;
119  }
120 
121  template <typename Series, typename T>
122  const Series&
123  PartialExp<Series, T>::exp_structure() const
124  {
125  return rat_exp_->structure();
126  }
127 
128  template <typename Series, typename T>
129  const T&
130  PartialExp<Series, T>::exp_value() const
131  {
132  return rat_exp_->value();
133  }
134 
135  template <typename Series, typename T>
136  const typename PartialExp<Series, T>::exp_t&
137  PartialExp<Series, T>::exp() const
138  {
139  return *rat_exp_;
140  }
141 
142  /*--------------------.
143  | PartialExp iterator |
144  `--------------------*/
145 
146  template <typename Series, typename T>
147  template <bool IsConst>
148  PartialExp<Series, T>::internal_iterator<IsConst>::internal_iterator(
149  const semiring_elts_iterator_t& sit, const nodes_iterator_t& nit ):
150  semiring_elts_iterator_(sit),
151  nodes_iterator_(nit),
152  on_node_ (false)
153  {}
154 
155  template <typename Series, typename T>
156  template <bool IsConst>
157  PartialExp<Series, T>::internal_iterator<IsConst>&
158  PartialExp<Series, T>::internal_iterator<IsConst>::operator++()
159  {
160  if (on_node_)
161  ++nodes_iterator_;
162  else
163  ++semiring_elts_iterator_;
164  on_node_ = not on_node_;
165  return *this;
166  }
167 
168  template <typename Series, typename T>
169  template <bool IsConst>
170  PartialExp<Series, T>::internal_iterator<IsConst>
171  PartialExp<Series, T>::internal_iterator<IsConst>::operator++(int)
172  {
173  internal_iterator old = *this;
174 
175  if (on_node_)
176  ++nodes_iterator_;
177  else
178  ++semiring_elts_iterator_;
179  on_node_ = not on_node_;
180  return old;
181  }
182 
183  template <typename Series, typename T>
184  template <bool IsConst>
185  typename PartialExp<Series, T>::template internal_iterator<IsConst>::
186  semiring_elt_ref_t
187  PartialExp<Series, T>::internal_iterator<IsConst>::semiring_elt() const
188  {
189  assertion(!on_node_);
190  return *semiring_elts_iterator_;
191  }
192 
193  template <typename Series, typename T>
194  template <bool IsConst>
195  typename PartialExp<Series, T>::template internal_iterator<IsConst>::
196  node_ref_t
197  PartialExp<Series, T>::internal_iterator<IsConst>::node() const
198  {
199  assertion(on_node_);
200  return *nodes_iterator_;
201  }
202 
203  template <typename Series, typename T>
204  template <bool IsConst>
205  bool
206  PartialExp<Series, T>::internal_iterator<IsConst>::on_node() const
207  {
208  return on_node_;
209  }
210 
211  template <typename Series, typename T>
212  template <bool IsConst>
213  bool
214  PartialExp<Series, T>::internal_iterator<IsConst>::operator!=(const internal_iterator& other)
215  {
216  return nodes_iterator_ != other.nodes_iterator_ or
217  semiring_elts_iterator_ != other.semiring_elts_iterator_;
218  }
219 
220  template <typename Series, typename T>
221  template <bool IsConst>
222  bool
223  PartialExp<Series, T>::internal_iterator<IsConst>::operator==(const internal_iterator& other)
224  {
225  return nodes_iterator_ == other.nodes_iterator_ and
226  semiring_elts_iterator_ == other.semiring_elts_iterator_;
227  }
228 
229  template <typename Series, typename T>
230  typename PartialExp<Series, T>::iterator
231  PartialExp<Series, T>::begin()
232  {
233  return iterator(semiring_elt_list_.begin(), node_list_.begin());
234  }
235 
236  template <typename Series, typename T>
237  typename PartialExp<Series, T>::const_iterator
238  PartialExp<Series, T>::begin() const
239  {
240  return const_iterator(semiring_elt_list_.begin(), node_list_.begin());
241  }
242 
243  template <typename Series, typename T>
244  typename PartialExp<Series, T>::iterator
245  PartialExp<Series, T>::end()
246  {
247  return iterator(semiring_elt_list_.end(), node_list_.end());
248  }
249 
250  template <typename Series, typename T>
251  typename PartialExp<Series, T>::const_iterator
252  PartialExp<Series, T>::end() const
253  {
254  return const_iterator(semiring_elt_list_.end(), node_list_.end());
255  }
256 
257  /*---------------------.
258  | PartialExp functions |
259  `---------------------*/
260 
261  template <typename S, typename T>
262  std::ostream& operator<< (std::ostream& o, const PartialExp<S, T>& e)
263  {
264  typename PartialExp<S, T>::const_iterator i = e.begin();
265 
266  o << '[' << i.semiring_elt();
267 
268  for (i++; i != e.end(); ++i)
269  {
270  if (i.on_node())
271  {
272  typename PartialExp<S, T>::series_set_elt_value_t v(i.node());
273  typename PartialExp<S, T>::exp_t val(e.exp().structure(), v);
274  o << '|' << val;
275  }
276  else
277  {
278  o << '|' << i.semiring_elt();
279  }
280  }
281  return o << ']';
282  }
283 
284  template <typename S, typename T, typename M, typename W>
285  PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp,
286  const rat::Node<M, W>* node)
287  {
288  typedef typename PartialExp<S, T>::semiring_elt_t semiring_elt_t;
289  semiring_elt_t lw = exp.structure().semiring().identity(
290  SELECT(typename semiring_elt_t::value_t));
291  semiring_elt_t rw = exp.structure().semiring().identity(
292  SELECT(typename semiring_elt_t::value_t));
293 
294  while (node->what() == rat::Node<M, W>::lweight or
295  node->what() == rat::Node<M, W>::rweight)
296  if (node->what() == rat::Node<M, W>::lweight)
297  {
298  const rat::LeftWeighted<M, W>* p =
299  dynamic_cast<const rat::LeftWeighted<M, W>*>(node);
300  lw = p->weight_ * lw;
301  node = p->child_;
302  }
303  else
304  {
305  const rat::RightWeighted<M, W>* p =
306  dynamic_cast<const rat::RightWeighted<M, W>*>(node);
307  rw *= p->weight_;
308  node = p->child_;
309  }
310  PartialExp<S, T> res(exp);
311  res.insert(node);
312  res >>= lw;
313  res <<= rw;
314  return res;
315  }
316 
317  template <typename S, typename T>
318  PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp)
319  {
320  return prat_exp_convert(exp, exp.value().base());
321  }
322 
323  template <typename S, typename T>
324  std::list<PartialExp<S, T> > prat_exp_convert(const std::list<Element<S, T> >& listexp)
325  {
326  std::list<PartialExp<S, T> > res;
327  for (typename std::list<Element<S, T> >::const_iterator it =
328  listexp.begin(); it != listexp.end(); ++it)
329  res.push_back(prat_exp_convert(*it, it->value().base()));
330  return res;
331  }
332 
333  template <typename S, typename T>
334  bool operator< (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
335  {
336  typedef
337  typename PartialExp<S, T>::series_set_elt_value_t series_set_elt_value_t;
338  typename PartialExp<S, T>::const_iterator i1 = e1.begin();
339  typename PartialExp<S, T>::const_iterator i2 = e2.begin();
340 
341  if (i1.semiring_elt() != i2.semiring_elt())
342  return (i1.semiring_elt() < i2.semiring_elt());
343 
344  for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
345  {
346  if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
347  break;
348  ++i1;
349  ++i2;
350  if (i1.semiring_elt() != i2.semiring_elt())
351  break;
352  ++i1;
353  ++i2;
354  }
355  if (i1 == e1.end() || i2 == e2.end())
356  return (i1 == e1.end() && i2 != e2.end());
357  else if (i1.on_node())
358  return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
359  else
360  return i1.semiring_elt() < i2.semiring_elt();
361  }
362 
363  template <typename S, typename T>
364  bool operator== (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
365  {
366  typedef
367  typename PartialExp<S, T>::series_set_elt_value_t series_set_elt_value_t;
368  typename PartialExp<S, T>::const_iterator i1 = e1.begin();
369  typename PartialExp<S, T>::const_iterator i2 = e2.begin();
370 
371  if (i1.semiring_elt() != i2.semiring_elt())
372  return false;
373 
374  for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
375  {
376  if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
377  break;
378  ++i1;
379  ++i2;
380  if (i1.semiring_elt() != i2.semiring_elt())
381  break;
382  ++i1;
383  ++i2;
384  }
385  return (i1 == e1.end() && i2 == e2.end());
386  }
387 
388  template <typename S, typename T>
389  bool unweighted_inf(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
390  {
391  typedef
392  typename PartialExp<S, T>::series_set_elt_value_t series_set_elt_value_t;
393  typename PartialExp<S, T>::const_iterator i1 = e1.begin();
394  typename PartialExp<S, T>::const_iterator i2 = e2.begin();
395 
396  for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
397  {
398  if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
399  break;
400  ++i1;
401  ++i2;
402  if (i1.semiring_elt() != i2.semiring_elt())
403  break;
404  ++i1;
405  ++i2;
406  }
407  if (i1 == e1.end() || i2 == e2.end())
408  return (i1 == e1.end() && i2 != e2.end());
409  else if (i1.on_node())
410  return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
411  else
412  return i1.semiring_elt() < i2.semiring_elt();
413  }
414 
415  template <typename S, typename T>
416  bool unweighted_eq(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
417  {
418  typedef
419  typename PartialExp<S, T>::series_set_elt_value_t series_set_elt_value_t;
420  typename PartialExp<S, T>::const_iterator i1 = e1.begin();
421  typename PartialExp<S, T>::const_iterator i2 = e2.begin();
422 
423  for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
424  {
425  if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
426  break;
427  ++i1;
428  ++i2;
429  if (i1.semiring_elt() != i2.semiring_elt())
430  break;
431  ++i1;
432  ++i2;
433  }
434  return (i1 == e1.end() && i2 == e2.end());
435  }
436 
437 } // vcsn
438 
439 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1