Vaucanson  1.4.1
thompson.hxx
1 // thompson.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, 2007, 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_THOMPSON_HXX
18 # define VCSN_ALGORITHMS_THOMPSON_HXX
19 
20 # include <utility>
21 
22 # include <vaucanson/algorithms/thompson.hh>
23 
24 # include <vaucanson/automata/concept/automata_base.hh>
25 # include <vaucanson/misc/usual_macros.hh>
26 
27 namespace vcsn {
28 
29  /*----------------.
30  | ThompsonVisitor |
31  `----------------*/
32  // FIXME : from now, it is only working over LetterAutomaton
33 
34  template <class Auto_, class Monoid_, class Semiring_>
35  class ThompsonVisitor :
36  public rat::ConstNodeVisitor<Monoid_, Semiring_>
37  {
38  public :
39  typedef Auto_ automaton_t;
40  typedef typename automaton_t::hstate_t hstate_t;
41  typedef typename automaton_t::set_t automata_set_t;
42  typedef typename automaton_t::series_set_t series_set_t;
43  typedef typename automaton_t::series_set_elt_t series_set_elt_t;
44  typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
45  typedef Monoid_ monoid_elt_value_t;
46  typedef Semiring_ semiring_elt_value_t;
47  typedef rat::Node<monoid_elt_value_t, semiring_elt_value_t> node_t;
48 
49  public :
50 
51  ThompsonVisitor(automaton_t &a)
52  : auto_ (a)
53  {}
54 
55  virtual
56  ~ThompsonVisitor()
57  {}
58 
59  virtual void
60  product(const node_t* lhs, const node_t* rhs)
61  {
62  // Visit left tree
63  lhs->accept(*this);
64  // Store results
65  std::pair<hstate_t, hstate_t> left_ini_fin = ini_fin_;
66  // Visit right tree
67  rhs->accept(*this);
68  // Create spontaneous link between
69  // final of left automaton and initial of right automaton.
70  auto_.add_spontaneous(left_ini_fin.second, ini_fin_.first);
71 
72  // Save new initial state.
73  ini_fin_.first = left_ini_fin.first;
74  }
75 
76  virtual void
77  sum(const node_t* lhs, const node_t* rhs)
78  {
79  lhs->accept(*this);
80 
81  std::pair<hstate_t, hstate_t> left_ini_fin = ini_fin_;
82  hstate_t new_i = auto_.add_state();
83  hstate_t new_f = auto_.add_state();
84 
85  auto_.add_spontaneous(new_i, left_ini_fin.first);
86  auto_.add_spontaneous(left_ini_fin.second, new_f);
87 
88  rhs->accept(*this);
89 
90  auto_.add_spontaneous(new_i, ini_fin_.first);
91  auto_.add_spontaneous(ini_fin_.second, new_f);
92 
93  ini_fin_.first = new_i;
94  ini_fin_.second = new_f;
95  }
96 
97  virtual void
98  star(const node_t* node)
99  {
100  node->accept(*this);
101  auto_.add_spontaneous(ini_fin_.second, ini_fin_.first);
102 
103  hstate_t new_i = auto_.add_state();
104  hstate_t new_f = auto_.add_state();
105 
106  auto_.add_spontaneous(new_i, new_f);
107  auto_.add_spontaneous(new_i, ini_fin_.first);
108  auto_.add_spontaneous(ini_fin_.second, new_f);
109 
110  ini_fin_.first = new_i;
111  ini_fin_.second = new_f;
112  }
113 
114  virtual void
115  left_weight(const semiring_elt_value_t& w, const node_t* node)
116  {
117  node->accept(*this);
118 
119  hstate_t new_i = auto_.add_state();
120  hstate_t new_f = auto_.add_state();
121 
122  series_set_elt_t t = auto_.series().zero_;
123  t.assoc(auto_.series().monoid().identity(SELECT(monoid_elt_value_t)), w);
124  auto_.add_series_transition(new_i, ini_fin_.first, t);
125 
126  auto_.add_spontaneous(ini_fin_.second, new_f);
127 
128  ini_fin_.first = new_i;
129  ini_fin_.second = new_f;
130  }
131 
132  virtual void
133  right_weight(const semiring_elt_value_t& w, const node_t* node)
134  {
135  node->accept(*this);
136 
137  hstate_t new_i = auto_.add_state();
138  hstate_t new_f = auto_.add_state();
139 
140  auto_.add_spontaneous(new_i, ini_fin_.first);
141 
142  series_set_elt_t t = auto_.series().zero_;
143  t.assoc(auto_.series().monoid().identity(SELECT(monoid_elt_value_t)), w);
144  auto_.add_series_transition(ini_fin_.second, new_f, t);
145 
146  ini_fin_.first = new_i;
147  ini_fin_.second = new_f;
148  }
149 
150  virtual void
151  constant(const monoid_elt_value_t& m)
152  {
153  ini_fin_.first = auto_.add_state();
154  hstate_t link_state;
155 
156  typename monoid_elt_value_t::const_iterator i = m.begin();
157 
158  ini_fin_.second = auto_.add_state();
159  auto_.add_letter_transition(ini_fin_.first, ini_fin_.second, *i);
160  ++i;
161 
162  while (i != m.end())
163  {
164  link_state = auto_.add_state();
165  auto_.add_spontaneous(ini_fin_.second, link_state);
166  ini_fin_.second = auto_.add_state();
167  auto_.add_letter_transition(link_state, ini_fin_.second, *i);
168  ++i;
169  }
170  }
171 
172  virtual void
173  zero()
174  {
175  ini_fin_.first = auto_.add_state();
176  ini_fin_.second = auto_.add_state();
177  }
178 
179  virtual void
180  one()
181  {
182  ini_fin_.first = auto_.add_state();
183  ini_fin_.second = auto_.add_state();
184  auto_.add_spontaneous(ini_fin_.first, ini_fin_.second);
185  }
186 
187  const automaton_t &get_auto() const
188  {
189  auto_.clear_initial();
190  auto_.clear_final();
191  auto_.set_initial(ini_fin_.first);
192  auto_.set_final(ini_fin_.second);
193  return auto_;
194  }
195 
196  // finalize is used to only set initial and final states of auto_
197  // only once (to spare the multiple set and unset required elsewise).
198  void
199  finalize() const
200  {
201  auto_.set_initial(ini_fin_.first);
202  auto_.set_final(ini_fin_.second);
203  }
204 
205  private :
206  automaton_t &auto_;
207  std::pair<hstate_t, hstate_t> ini_fin_;
208  };
209 
210  template <typename A, typename auto_t,
211  typename Letter, typename Weight>
212  void
213  do_thompson_of(const AutomataBase<A>&,
214  auto_t& output,
215  const rat::exp<Letter, Weight>& kexp)
216  {
217  // You should provide an empty automaton as output.
218  ThompsonVisitor<auto_t, Letter, Weight> visitor(output);
219  // FIXME :
220  // Static assert : Letter = monoid_elt_value_t,
221  // Weight = semiring_elt_value_t
222  kexp.accept(visitor);
223  visitor.finalize();
224  }
225 
226  template<typename A, typename T,
227  typename Letter, typename Weight>
228  void
229  thompson_of(Element<A, T>& out,
230  const rat::exp<Letter, Weight>& kexp)
231  {
232  do_thompson_of(out.structure(), out, kexp);
233  }
234 
235  template <typename AutoType, typename S, typename K, typename T>
236  Element<Automata<S, K>, AutoType>
237  thompson_of(const Element<S, T>& exp)
238  {
239  Automata<S, K> automata_set(exp.structure());
240  Element<Automata<S, K>, AutoType> automata(automata_set);
241 
242  thompson_of(automata, exp.value());
243  return automata;
244  }
245 } // vcsn
246 
247 #endif // ! VCSN_ALGORITHMS_THOMPSON_HXX
Generated on Sat Jul 14 2012 18:46:41 for Vaucanson by   doxygen 1.8.1.1