Vaucanson  1.4.1
krat_exp_expand.hxx
1 // krat_exp_expand.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, 2011 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_KRAT_EXP_EXPAND_HXX
18 # define VCSN_ALGORITHMS_KRAT_EXP_EXPAND_HXX
19 
20 # include <list>
21 # include <map>
22 
23 # include <vaucanson/algorithms/krat_exp_expand.hh>
24 
25 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
26 
27 namespace vcsn
28 {
29 
30  namespace algebra {
31 
32  // This is a trait to get more easily used types.
33  template <typename S, typename T>
34  struct pseudo_exp_list
35  {
36  typedef Element<S, T> exp_t;
37  typedef std::list<exp_t> exp_list_t;
38  typedef typename exp_t::semiring_elt_t semiring_elt_t;
39  typedef std::map<exp_list_t, semiring_elt_t> ret_t;
40  };
41 
42  // The Expander class. It breaks up the expression to build a map
43  // and then rebuild it.
44  template <class Series, class T, class Dispatch>
45  struct KRatExpExpander : algebra::KRatExpMatcher<
46  KRatExpExpander<Series, T, Dispatch>,
47  T,
48  typename pseudo_exp_list<Series, T>::ret_t,
49  Dispatch
50  >
51  {
52  public:
53  typedef pseudo_exp_list<Series, T> trait;
54  typedef typename trait::exp_t exp_t;
55  typedef typename trait::ret_t return_type;
56  typedef typename trait::exp_list_t exp_list_t;
57  typedef KRatExpExpander<Series, T, Dispatch> self_t;
58  typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
59  typedef typename semiring_elt_t::value_t semiring_elt_value_t;
60  typedef typename Element<Series, T>::monoid_elt_t monoid_elt_t;
61  typedef typename monoid_elt_t::set_t monoid_t;
62  typedef typename monoid_t::alphabet_t alphabet_t;
63  typedef typename alphabet_t::letter_t letter_t;
64  INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
65 
66  KRatExpExpander(const exp_t& exp) :
67  exp_(exp)
68  {}
69 
70  // Some useful internal functions.
71  private:
72  // Convert the return_type into a rational expression.
73  exp_t convert(const return_type& l)
74  {
75  typedef typename return_type::const_iterator iterator;
76  typedef typename exp_list_t::const_iterator sub_iterator;
77 
78  exp_t result = exp_.structure().zero(SELECT(T));
79 
80  for (iterator i = l.begin(); i != l.end(); ++i)
81  {
82  exp_list_t l = i->first;
83  exp_t e = l.front();
84  for (sub_iterator j = ++l.begin(); j != l.end(); ++j)
85  e *= *j;
86  result += i->second * e;
87  }
88 
89  return result;
90  }
91 
92  // Convert a standard expression into the corresponding breaked one.
93  return_type convert(const exp_t& e)
94  {
95  exp_list_t exp_list;
96  exp_list.push_front(e);
97 
98  return_type result;
99  result[exp_list] =
100  exp_.structure().semiring().identity(SELECT(semiring_elt_value_t));
101 
102  return result;
103  }
104 
105  // The union of two lists implemented by a map. If an element is in the
106  // two lists then the weights are added.
107  return_type list_union(const return_type& left,
108  const return_type& right)
109  {
110  typedef typename return_type::const_iterator const_iterator;
111  typedef typename return_type::iterator iterator;
112 
113  return_type result(left);
114  for (const_iterator i = right.begin(); i != right.end(); ++i)
115  {
116  iterator j = result.find(i->first);
117 
118  if (j != result.end())
119  j->second += i->second;
120  else
121  result.insert(*i);
122  }
123 
124  return result;
125  }
126 
127  // Compute the concatenation of two lists
128  exp_list_t list_concat(const exp_list_t& left, const exp_list_t& right)
129  {
130 
131  typename T::node_t* lnode = left.back().value().base();
132  typename T::node_t* rnode = right.front().value().base();
133 
134  // Handle concatenations when one operand is a constant (ONE or ZERO)
135  if (dynamic_cast<typename T::n_one_t*>(lnode))
136  return right;
137  if (dynamic_cast<typename T::n_one_t*>(rnode))
138  return left;
139  if (dynamic_cast<typename T::n_zero_t*>(lnode))
140  return left;
141  if (dynamic_cast<typename T::n_zero_t*>(rnode))
142  return right;
143 
144  typedef typename exp_list_t::const_iterator const_iterator;
145  std::list<exp_t> result(left);
146 
147  // If the last exp from left and the first exp from right
148  // are words, concatenate them.
149  typename T::n_const_t* left_node =
150  dynamic_cast<typename T::n_const_t*>(lnode);
151  typename T::n_const_t* right_node =
152  dynamic_cast<typename T::n_const_t*>(rnode);
153  if (left_node and right_node)
154  {
155  result.back() = exp_t(exp_.structure(),
156  left_node->value_ + right_node->value_);
157  for (const_iterator i = ++right.begin(); i != right.end(); ++i)
158  result.push_back(*i);
159  }
160  else
161  for (const_iterator i = right.begin(); i != right.end(); ++i)
162  result.push_back(*i);
163  return result;
164  }
165 
166  // Public functions.
167  public:
168  // This function convert the result the original form.
169  exp_t get()
170  {
171  return_type l = this->match(exp_.value());
172  return convert(l);
173  }
174 
175  // Match functions.
176  MATCH__(Product, lhs, rhs)
177  {
178  typedef typename return_type::iterator iterator;
179 
180  return_type llist = this->match(lhs);
181  return_type rlist = this->match(rhs);
182  return_type result;
183 
184  for (iterator i = llist.begin(); i != llist.end(); ++i)
185  for (iterator j = rlist.begin(); j != rlist.end(); ++j)
186  {
187  exp_list_t p = list_concat(i->first, j->first);
188 
189  iterator pi = result.find(p);
190  if (pi != result.end())
191  pi->second += i->second * j->second;
192  else
193  result[p] = i->second * j->second;
194  }
195  return result;
196  }
197  END
198 
199  MATCH__(Sum, lhs, rhs)
200  {
201  return list_union(this->match(lhs), this->match(rhs));
202  }
203  END
204 
205  MATCH_(Star, e)
206  {
207  return_type l = this->match(e);
208  return convert(convert(l).star());
209  }
210  END
211 
212  MATCH__(LeftWeight, w, e)
213  {
214  typedef typename return_type::iterator iterator;
215 
216  return_type l = this->match(e);
217  return_type result;
218 
219  for (iterator i = l.begin(); i != l.end(); ++i)
220  result[i->first] = semiring_elt_t(w) * i->second;
221  return result;
222  }
223  END
224 
225  MATCH__(RightWeight, e, w)
226  {
227  typedef typename return_type::iterator iterator;
228 
229  return_type l = this->match(e);
230  return_type result;
231 
232  for (iterator i = l.begin(); i != l.end(); ++i)
233  result[i->first] = i->second * semiring_elt_t(w);
234  return result;
235  }
236  END
237 
238  MATCH_(Constant, m)
239  {
240  return convert(exp_t(exp_.structure(), m));
241  }
242  END
243 
244  MATCH(Zero)
245  {
246  return convert(exp_.structure().zero(SELECT(T)));
247  }
248  END
249 
250  MATCH(One)
251  {
252  return convert(exp_.structure().identity(SELECT(T)));
253  }
254  END
255 
256  private:
257  Element<Series, T> exp_;
258  };
259 
260  } // ! algebra
261 
262  template <class S, class E>
263  E do_expand(const algebra::SeriesBase<S>&, const E& exp)
264  {
265  typedef typename E::value_t T;
266 
267  algebra::KRatExpExpander< S, T, algebra::DispatchFunction<T> > matcher(exp);
268  return matcher.get();
269  }
270 
271  template <class Series, class T>
272  Element<Series, T>
273  expand(const Element<Series, T>& exp)
274  {
275  return do_expand(exp.structure(), exp);
276  }
277 
278 } // ! vcsn
279 
280 #endif // ! VCSN_ALGORITHMS_KRAT_EXP_EXPAND_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1