Vaucanson  1.4.1
partial_rat_exp_derivation.hxx
1 // partial_rat_exp_derivation.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 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_DERIVATION_HXX
18 # define VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_DERIVATION_HXX
19 
20 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
21 # include <vaucanson/algorithms/krat_exp_constant_term.hh>
22 # include <vaucanson/algebra/implementation/series/krat.hh>
23 # include <vaucanson/misc/contract.hh>
24 
25 namespace vcsn {
26 
27  template <typename T>
28  void list_fusion_here(std::list<T>& dst, std::list<T>& src)
29  {
30  typedef typename std::list<T>::iterator iterator;
31  typedef typename T::series_set_t series_set_t;
32  typedef typename T::series_set_elt_value_t series_set_elt_value_t;
33  typedef typename T::semiring_elt_t::value_t semiring_elt_value_t;
34 
35  src.sort(unweighted_inf<series_set_t, series_set_elt_value_t>);
36  dst.sort(unweighted_inf<series_set_t, series_set_elt_value_t>);
37  dst.merge(src, unweighted_inf<series_set_t, series_set_elt_value_t>);
38  iterator i = dst.begin();
39  while (i != dst.end())
40  {
41  iterator next = i;
42  if (++next != dst.end() and unweighted_eq(*next, *i))
43  {
44  i->begin().semiring_elt() += next->begin().semiring_elt();
45  dst.erase(next);
46  if (i->begin().semiring_elt() ==
47  i->begin().semiring_elt().structure().zero(
48  SELECT(semiring_elt_value_t)))
49  {
50  next = i++;
51  dst.erase(next);
52  continue ;
53  }
54  }
55  ++i;
56  }
57  }
58 
59  template <typename S, typename T>
60  void list_multiply_here_left(std::list<PartialExp<S, T> >& l,
61  const typename PartialExp<S, T>::semiring_elt_t& w)
62  {
63  typedef std::list<PartialExp<S, T> > list_t;
64  for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
65  *i >>= w;
66  }
67 
68  template <typename S, typename T>
69  void list_multiply_here_right(std::list<PartialExp<S, T> >& l,
70  const typename PartialExp<S, T>::semiring_elt_t& w)
71  {
72  typedef std::list<PartialExp<S, T> > list_t;
73  for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
74  *i <<= w;
75  }
76 
77  template <typename S, typename T>
78  void list_insert_here(std::list<PartialExp<S, T> >& l,
79  const typename PartialExp<S,T>::node_t* elm)
80  {
81  typedef std::list<PartialExp<S, T> > list_t;
82  for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
83  i->insert(elm);
84  }
85 
92  template <typename Series, typename T>
93  class PRatExpDerivationVisitor :
94  public rat::ConstNodeVisitor<typename T::monoid_elt_value_t,
95  typename T::semiring_elt_value_t>
96  {
97  public:
98  typedef Element<Series, T> exp_t;
99  typedef T series_set_elt_value_t;
100  typedef typename T::node_t node_t;
101  typedef typename std::list<PartialExp<Series, T> > return_type;
102  typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
103  typedef typename semiring_elt_t::value_t semiring_elt_value_t;
104  typedef typename Element<Series, T>::monoid_elt_t monoid_elt_t;
105  typedef typename monoid_elt_t::value_t monoid_elt_value_t;
106  typedef typename monoid_elt_t::set_t monoid_t;
107  typedef typename monoid_t::alphabet_t alphabet_t;
108  typedef typename alphabet_t::letter_t letter_t;
109 
110  public:
111  PRatExpDerivationVisitor(const exp_t& exp,
112  const letter_t& a) :
113  undefined(false),
114  exp_(exp),
115  a_(a),
116  father_(NULL)
117  {}
118 
119  virtual
120  ~PRatExpDerivationVisitor()
121  {}
122 
123  void match(const node_t* node)
124  {
125  father_ = node;
126  node->accept(*this);
127  }
128 
129  private:
130  Element<Series, T> series(const T& e)
131  {
132  return Element<Series, T>(exp_.structure(), e);
133  }
134 
135  public:
136  virtual void
137  product(const node_t* lhs, const node_t* rhs)
138  {
139  std::pair<semiring_elt_t, bool> ret =
140  constant_term(series(series_set_elt_value_t(lhs)));
141  if (ret.second == false)
142  {
143  undefined = true;
144  return ;
145  }
146 
147  return_type tmp;
148  if ( ret.first !=
149  exp_.structure().semiring().zero(SELECT(semiring_elt_value_t)))
150  {
151  match(rhs);
152  list_multiply_here_left(result, ret.first);
153  tmp = result;
154  }
155 
156  match(lhs);
157  list_insert_here(result, rhs);
158  list_fusion_here(result, tmp);
159  }
160 
161  virtual void
162  sum(const node_t* lhs, const node_t* rhs)
163  {
164  match(rhs);
165  return_type tmp = result;
166  match(lhs);
167  list_fusion_here(result, tmp);
168  }
169 
170  virtual void
171  star(const node_t* node)
172  {
173  assertion(father_ != NULL);
174  const typename T::node_t* father = father_;
175 
176  std::pair<semiring_elt_t, bool> ret =
177  constant_term(series(series_set_elt_value_t(node)));
178  if ((ret.second == false) || (ret.first.starable() == false))
179  {
180  undefined = true;
181  return;
182  }
183 
184  match(node);
185  list_insert_here(result, father);
186  list_multiply_here_left(result, ret.first.star());
187  }
188 
189  virtual void
190  left_weight(const semiring_elt_value_t& w, const node_t* node)
191  {
192  match(node);
193  list_multiply_here_left(result, semiring_elt_t(w));
194  }
195 
196  virtual void
197  right_weight(const semiring_elt_value_t& w, const node_t* node)
198  {
199  match(node);
200  list_multiply_here_right(result, semiring_elt_t(w));
201  }
202 
203  virtual void
204  constant(const monoid_elt_value_t& m)
205  {
206  result = return_type();
207  if (m.length() != 1)
208  {
209  WARNING("PartialExp base is not realtime.");
210  undefined = true;
211  return;
212  }
213  if (m[0] == a_)
214  result.push_back(PartialExp<Series, T>(exp_));
215  }
216 
217  virtual void
218  zero()
219  {
220  result = return_type();
221  }
222 
223  virtual void
224  one()
225  {
226  result = return_type();
227  }
228 
229  public:
230  bool undefined;
231  return_type result;
232 
233  private:
234  const exp_t& exp_;
235  const letter_t& a_;
236  const typename T::node_t* father_;
237  };
238 
239 
240 /*****************************************************************************/
241 /***************************** User's functions ******************************/
242 /*****************************************************************************/
243 
244  template <class Series, class T, class Letter>
245  std::pair<std::list<PartialExp<Series, T> >, bool>
246  prat_exp_derivate(const Element<Series, T>& exp,
247  Letter a)
248  {
249  PRatExpDerivationVisitor<Series, T> visitor(exp, a);
250  visitor.match(exp.value().base());
251  return std::make_pair(visitor.result, !visitor.undefined);
252  }
253 
254  template <class Series, class T, class Letter>
255  std::pair<std::list<PartialExp<Series, T> >, bool>
256  prat_exp_derivate(const PartialExp<Series, T>& exp,
257  Letter a)
258  {
259  typedef PartialExp<Series, T> exp_t;
260  typedef std::list<PartialExp<Series, T> > exp_list_t;
261  typedef std::pair<exp_list_t, bool> return_type;
262  typedef typename exp_t::const_iterator const_iterator;
263  typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
264  typedef typename semiring_elt_t::value_t semiring_elt_value_t;
265  typedef T series_set_elt_value_t;
266 
267  // Save the first weight, and go to the first expression
268  const_iterator i = exp.begin();
269  semiring_elt_t w = i.semiring_elt();
270  i++;
271 
272  // Check if the exp is not empty
273  if (i == exp.end())
274  return std::make_pair(exp_list_t(), true);
275 
276  // Visit the first element of the exp
277  PRatExpDerivationVisitor<Series, T> visitor(exp.exp(), a);
278  const typename exp_t::node_t* n = i.node();
279  visitor.match(n);
280 
281  // Insert other pointers and values into the result
282  for (i++; i != exp.end(); ++i)
283  if (i.on_node())
284  list_insert_here(visitor.result, i.node());
285  else
286  list_multiply_here_right(visitor.result, i.semiring_elt());
287 
288  // Calculate the constant term
289  std::pair<semiring_elt_t, bool> cterm =
290  constant_term(Element<Series, T>(exp.exp_structure(), series_set_elt_value_t(n)));
291  if (cterm.second == false)
292  return std::make_pair(exp_list_t(), false);
293 
294  // -------- If cterm != 0, look at the rest of the list ---------------
295  if (cterm.first !=
296  exp.exp_structure().semiring().zero(SELECT(semiring_elt_value_t)) )
297  {
298  // Build an exp from the orignal, without the head
299  exp_t new_exp(exp);
300  new_exp.nodes().pop_front();
301  new_exp.weights().pop_front();
302 
303  // Recall prat_exp_derivate on it
304  return_type ret = prat_exp_derivate(new_exp, a);
305 
306  // Multiply by constant term
307  list_multiply_here_left(ret.first, cterm.first);
308 
309  // Fusion results
310  visitor.undefined = visitor.undefined || !ret.second;
311  list_fusion_here(visitor.result, ret.first);
312  }
313  //------------------------------------------------------------------------
314 
315  // Multiply by the weight of exp
316  list_multiply_here_left(visitor.result, w);
317 
318  // Return the final result
319  return std::make_pair(visitor.result, !visitor.undefined);
320  }
321 
322 } // vcsn
323 
324 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_DERIVATION_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1