Vaucanson  1.4.1
standard_of.hxx
1 // standard_of.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, 2006, 2008, 2009, 2010, 2011
6 // The 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_ALGORITHMS_STANDARD_OF_HXX
19 # define VCSN_ALGORITHMS_STANDARD_OF_HXX
20 
21 # include <vaucanson/algorithms/standard_of.hh>
22 
23 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
24 # include <vaucanson/algorithms/standard.hh>
25 
26 # include <vaucanson/misc/usual_macros.hh>
27 
28 namespace vcsn {
29 
30  namespace algebra {
31 
32  /*-------------------.
33  | Standard_OfVisitor |
34  `-------------------*/
35  template <class Exp_,
36  class Auto_,
37  class Dispatch_>
38  class Standard_OfVisitor :
39  public algebra::KRatExpMatcher<
40  Standard_OfVisitor<Exp_, Auto_, Dispatch_>,
41  Exp_,
42  Auto_*,
43  Dispatch_
44  >
45  {
46  public :
47  typedef Auto_* automaton_ptr_t;
48  typedef Auto_ automaton_t;
49  typedef typename automaton_t::set_t automata_set_t;
50 
51  typedef typename automaton_t::series_set_t series_set_t;
52  typedef typename automaton_t::monoid_t monoid_t;
53  typedef typename automaton_t::semiring_t semiring_t;
54 
55  typedef typename automaton_t::series_set_elt_t series_set_elt_t;
56  typedef typename automaton_t::monoid_elt_t monoid_elt_t;
57  typedef typename automaton_t::semiring_elt_t semiring_elt_t;
58 
59  typedef typename automaton_t::hstate_t hstate_t;
60  typedef typename automaton_t::htransition_t htransition_t;
61 
62  typedef typename Exp_::monoid_elt_value_t monoid_elt_value_t;
63  typedef typename Exp_::semiring_elt_value_t semiring_elt_value_t;
64 
65  typedef Standard_OfVisitor<Exp_, Auto_, Dispatch_> this_class;
66  typedef algebra::KRatExpMatcher<this_class, Exp_, Auto_*, Dispatch_>
67  parent_class;
68  typedef typename parent_class::return_type return_type;
69 
70  public :
71 
72  Standard_OfVisitor(automaton_t& a) :
73  automata_set_(a.series()),
74  auto_(&a)
75  {
76  }
77 
78  INHERIT_CONSTRUCTORS(this_class, Exp_, Auto_*, Dispatch_);
79 
80  // Could not use standard.hh functions because of the storing system.
81  // No map needed here.
82  MATCH__(Product, lhs, rhs)
83  {
84  AUTOMATON_TYPES(automaton_t);
85  this->match(lhs);
86 
87  hstate_t lhs_i = initial_;
88 
89  // Store final states and final values and clear it.
90  typedef typename std::list<std::pair<hstate_t, series_set_elt_t> >
91  list_fin_st_t;
92 
93  list_fin_st_t lhs_tmp;
94 
95  for_all_final_states(f, *auto_)
96  lhs_tmp.push_back (std::pair<hstate_t, series_set_elt_t>
97  (*f, auto_->get_final(*f)));
98  auto_->clear_final();
99 
100  this->match(rhs);
101 
102  // Restore the previously saved data.
103  typedef std::list<hstate_t> list_st_t;
104 
105  list_st_t lhs_finals;
106 
107  for (typename list_fin_st_t::iterator i = lhs_tmp.begin();
108  i != lhs_tmp.end();
109  ++i)
110  {
111  auto_->set_final(i->first, i->second);
112  lhs_finals.push_back (i->first);
113  }
114 
115  concat_of_standard_inside(auto_->structure(),
116  *auto_, lhs_finals, initial_);
117 
118  initial_ = lhs_i;
119  return auto_;
120  }
121  END
122 
123  MATCH__(Sum, lhs, rhs)
124  {
125  AUTOMATON_TYPES(automaton_t);
126  typedef typename std::list<std::pair<hstate_t, series_set_elt_t> >
127  list_fin_st_t;
128 
129  this->match(lhs);
130 
131  // Store lhs initial state.
132  hstate_t left_i = initial_;
133 
134  // Store final states and final values and clear it.
135  list_fin_st_t lhs_tmp;
136 
137  for_all_const_final_states(f, *auto_)
138  lhs_tmp.push_back (std::pair<hstate_t, series_set_elt_t>
139  (*f, auto_->get_final(*f)));
140 
141  auto_->clear_final();
142 
143  this->match(rhs);
144 
145  // Restore the previously saved data.
146  for (typename list_fin_st_t::iterator i = lhs_tmp.begin();
147  i != lhs_tmp.end();
148  ++i)
149  auto_->set_final(i->first, i->second);
150 
151  sum_of_standard_inside(auto_->structure(),
152  *auto_, left_i, initial_);
153 
154  initial_ = left_i;
155  return auto_;
156  }
157  END
158 
159  MATCH_(Star, node)
160  {
161  AUTOMATON_TYPES(automaton_t);
162  this->match(node);
163 
164  precondition(auto_->get_final(initial_).starable());
165 
166  typedef typename std::list<hstate_t> list_fin_st_t;
167 
168  // Store final states and final values and clear it.
169  list_fin_st_t tmp;
170 
171  for_all_final_states(f, *auto_)
172  if (*f != initial_)
173  tmp.push_back(*f);
174 
175  star_of_standard_inside(auto_->structure(),
176  *auto_, initial_, tmp);
177  return auto_;
178  }
179  END
180 
181  MATCH__(LeftWeight, w, node)
182  {
183  const semiring_t& semiring = automata_set_.series().semiring();
184  const semiring_elt_t weight (semiring, w);
185  const series_set_elt_t ws(auto_->series(), weight);
186  this->match(node);
187 
188  left_ext_mult_of_standard_inside(auto_->structure(),
189  *auto_, initial_, ws);
190  return auto_;
191  }
192  END
193 
194  MATCH__(RightWeight, node, w)
195  {
196  const semiring_t& semiring = automata_set_.series().semiring();
197  const semiring_elt_t weight (semiring, w);
198  this->match(node);
199 
200  for (typename automaton_t::final_iterator
201  f, next = auto_->final().begin();
202  next != auto_->final().end();)
203  {
204  // We need to store the next iterator before using the
205  // current one to avoid an invalid iterator after having
206  // called set_final. Indeed, set_final() can delete the
207  // iterator if its second parameter is the zero of the
208  // series.
209  f = next;
210  next++;
211  auto_->set_final(*f, auto_->get_final(*f) * weight);
212  }
213 
214  return auto_;
215  }
216  END
217 
218  MATCH_(Constant, m)
219  {
220  initial_ = auto_->add_state();
221  hstate_t last = initial_;
222  hstate_t new_f = initial_;
223 
224  for (typename monoid_elt_value_t::const_iterator i = m.begin();
225  i != m.end(); ++i)
226  {
227  new_f = auto_->add_state();
228  auto_->add_letter_transition(last, new_f, *i);
229  last = new_f;
230  }
231  auto_->set_initial(initial_);
232  auto_->set_final(new_f);
233 
234  return auto_;
235  }
236  END
237 
238  MATCH(Zero)
239  {
240  initial_ = auto_->add_state();
241  auto_->set_initial(initial_);
242  return auto_;
243  }
244  END
245 
246  MATCH(One)
247  {
248  initial_ = auto_->add_state();
249  auto_->set_initial(initial_);
250  auto_->set_final(initial_);
251  return auto_;
252  }
253  END
254 
255  private:
256  automata_set_t automata_set_;
257  // The automata used for construction
258  hstate_t initial_;
259  automaton_ptr_t auto_;
260 
261  typedef
262  class
263  {
264  public:
265  inline hstate_t operator[] (hstate_t a)
266  {
267  return a;
268  }
269  } ident_t;
270 
271  ident_t identity_;
272  };
273 
274  }
275 
276  template <typename A,
277  typename Output,
278  typename Exp>
279  void
280  do_standard_of(const AutomataBase<A>&,
281  Output& output,
282  const Exp& kexp)
283  {
284  algebra::Standard_OfVisitor<Exp, Output, algebra::DispatchFunction<Exp> >
285  m(output);
286 
287  m.match(kexp);
288  }
289 
290  template<typename A,
291  typename T,
292  typename Exp>
293  void
294  standard_of(Element<A, T>& out,
295  const Exp& kexp)
296  {
297  do_standard_of(out.structure(), out, kexp);
298  }
299 
300 } // vcsn
301 
302 #endif // ! VCSN_ALGORITHMS_STANDARD_OF_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1