Vaucanson  1.4.1
normalized.hxx
1 // normalized.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, 2010 The
6 // 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_NORMALIZED_HXX
19 # define VCSN_ALGORITHMS_NORMALIZED_HXX
20 
21 # include <vaucanson/algorithms/normalized.hh>
22 # include <vaucanson/algorithms/internal/has_neighbour.hh>
23 
24 # include <vaucanson/automata/concept/automata_base.hh>
25 # include <vaucanson/misc/usual_macros.hh>
26 # include <vaucanson/algorithms/standard.hh>
27 
28 # include <stack>
29 
30 namespace vcsn {
31 
32  /*-----------.
33  | normalized |
34  `-----------*/
35  template <typename A, typename AI>
36  void
37  do_normalize_here(const AutomataBase<A>&,
38  Element<A, AI>& a)
39  {
40  BENCH_TASK_SCOPED("normalize");
41  typedef Element<A, AI> automaton_t;
42  AUTOMATON_TYPES(automaton_t);
43 
44  hstate_t h = a.add_state();
45 
46  for_all_const_initial_states(i, a)
47  a.add_series_transition(h, *i, a.get_initial(*i));
48 
49  a.clear_initial();
50  a.set_initial(h);
51 
52  h = a.add_state();
53 
54  for_all_const_final_states(i, a)
55  a.add_series_transition(*i, h, a.get_final(*i));
56 
57  a.clear_final();
58  a.set_final(h);
59  }
60 
61  template <typename A, typename AI>
62  Element<A, AI>
63  normalize(const Element<A, AI>& a)
64  {
65  Element<A, AI> result(a);
66  do_normalize_here(result.structure(), result);
67  return result;
68  }
69 
70  template<typename A, typename AI>
71  void
72  normalize_here(Element<A, AI>& a)
73  {
74  do_normalize_here(a.structure(), a);
75  }
76 
77 
78  /*--------------------.
79  | union_of_normalized |
80  `--------------------*/
81 
82  template <typename A, typename AI1, typename AI2>
83  void
84  do_union_of_normalized_here(const AutomataBase<A>&,
85  Element<A, AI1>& lhs,
86  const Element<A, AI2>& rhs)
87  {
88  BENCH_TASK_SCOPED("union_of_normalized");
89  typedef Element<A, AI1> lhs_t;
90  typedef Element<A, AI2> rhs_t;
91  AUTOMATON_TYPES(lhs_t);
92  monoid_elt_t monoid_identity =
93  lhs.series().monoid().identity(SELECT(monoid_elt_value_t));
94  hstate_t new_i = lhs.add_state();
95  hstate_t new_f = lhs.add_state();
96 
97  union_here(lhs, rhs);
98 
99  for_all_const_initial_states(i, lhs)
100  lhs.add_spontaneous(new_i, *i, lhs.get_initial(*i).get(monoid_identity));
101  lhs.clear_initial();
102 
103  for_all_const_final_states(f, lhs)
104  lhs.add_spontaneous(*f, new_f, lhs.get_final(*f).get(monoid_identity));
105  lhs.clear_final();
106 
107  lhs.set_final(new_f);
108  lhs.set_initial(new_i);
109  }
110 
111  template<typename A, typename AI1, typename AI2>
112  void
113  union_of_normalized_here(Element<A, AI1>& lhs,
114  const Element<A, AI2>& rhs)
115  {
116  do_union_of_normalized_here(lhs.structure(), lhs, rhs);
117  }
118 
119  template<typename A, typename AI1, typename AI2>
120  Element<A, AI1>
121  union_of_normalized(const Element<A, AI1>& lhs,
122  const Element<A, AI2>& rhs)
123  {
124  Element<A, AI1> ret(lhs);
125  do_union_of_normalized_here(ret.structure(), ret, rhs);
126  return ret;
127  }
128 
129  /*--------------.
130  | is_normalized |
131  `--------------*/
132  template <typename A, typename AI>
133  bool
134  do_is_normalized(const AutomataBase<A>&,
135  const Element<A, AI>& a)
136  {
137  BENCH_TASK_SCOPED("is_normalized");
138  typedef Element<A, AI> automaton_t;
139  typedef typename automaton_t::series_set_elt_value_t series_set_elt_value_t;
140  typedef typename automaton_t::series_set_elt_t series_set_elt_t;
141 
142  series_set_elt_t series_identity =
143  a.series().identity(SELECT(series_set_elt_value_t));
144 
145  if (a.initial().size() != 1
146  || a.final().size() != 1
147  || a.get_initial(*a.initial().begin()) != series_identity
148  || a.get_final(*a.final().begin()) != series_identity)
149  return false;
150 
151  // Check that there is no input transition on the initial state
152  // and no output transition on the final state.
153  return !has_successors(a, *a.final().begin())
154  && !has_predecessors(a, *a.initial().begin());
155  }
156 
157  template<typename A, typename AI>
158  bool
159  is_normalized(const Element<A, AI>& a)
160  {
161  return do_is_normalized(a.structure(), a);
162  }
163 
164  /*--------------------------.
165  | concatenate_of_normalized |
166  `--------------------------*/
167  template <typename A, typename AI1, typename AI2>
168  void
169  do_concatenate_of_normalized_here(const AutomataBase<A>&,
170  Element<A, AI1>& lhs,
171  const Element<A, AI2>& rhs)
172  {
173  BENCH_TASK_SCOPED("concatenate_of_normalized");
174  typedef Element<A, AI1> lhs_t;
175  typedef Element<A, AI2> rhs_t;
176  AUTOMATON_TYPES(rhs_t);
177  typedef std::map<hstate_t, hstate_t> map_lhs_rhs_t;
178  typedef std::list<htransition_t> delta_ret_t;
179 
180  hstate_t glue_state = *lhs.final().begin();
181 
182  /*-----------------.
183  | Concat of states |
184  `-----------------*/
185  map_lhs_rhs_t map_h;
186 
187  // If rhs initial multiplicity is 1 and so is lhs final multiplicity,
188  // we can merge the lhs final state and the rhs initial state.
189  bool merge_lhs_final_and_rhs_initial =
190  (lhs.get_final(*lhs.final().begin()).value() ==
191  lhs.series().identity(SELECT(series_set_elt_value_t)) &&
192  rhs.get_initial(*rhs.initial().begin()).value() ==
193  rhs.series().identity(SELECT(series_set_elt_value_t)));
194 
195  for_all_const_states(s, rhs)
196  {
197  hstate_t new_state;
198 
199  if (merge_lhs_final_and_rhs_initial)
200  {
201  if (rhs.is_initial(*s))
202  new_state = glue_state;
203  else
204  new_state = lhs.add_state();
205  }
206  else
207  new_state = lhs.add_state();
208  map_h[*s] = new_state;
209  lhs.set_final(new_state, rhs.get_final(*s));
210  }
211 
212  /*------------------------.
213  | Concat of transitions. |
214  `------------------------*/
215  for_all_const_transitions(t, rhs)
216  lhs.add_transition(map_h[rhs.src_of(*t)],
217  map_h[rhs.dst_of(*t)],
218  rhs.label_of(*t));
219 
220  // If initial multiplicity of rhs isn't 1, add a spontaneous transition
221  // between lhs final state and rhs initial state, with lhs final
222  // multiplicity * rhs initial multiplicity.
223  if (!merge_lhs_final_and_rhs_initial)
224  {
225  monoid_elt_t monoid_identity =
226  rhs.series().monoid().identity(SELECT(monoid_elt_value_t));
227  hstate_t i = *rhs.initial().begin();
228  hstate_t f = *lhs.final().begin();
229 
230  lhs.add_spontaneous(f, map_h[i],
231  lhs.get_final(f).get(monoid_identity) *
232  rhs.get_initial(i).get(monoid_identity));
233  lhs.unset_final(f);
234  lhs.unset_initial(map_h[i]);
235  }
236  }
237 
238  template<typename A, typename AI1, typename AI2>
239  void
240  concatenate_of_normalized_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
241  {
242  do_concatenate_of_normalized_here(lhs.structure(), lhs, rhs);
243  }
244 
245  template<typename A, typename AI1, typename AI2>
246  Element<A, AI1>
247  concatenate_of_normalized(const Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
248  {
249  Element<A, AI1> ret(lhs);
250  do_concatenate_of_normalized_here(ret.structure(), ret, rhs);
251  return ret;
252  }
253 
254  /*-------------------.
255  | star_of_normalized |
256  `-------------------*/
257  template <typename A, typename AI>
258  void
259  do_star_of_normalized_here(const AutomataBase<A>&, Element<A, AI>& a)
260  {
261  BENCH_TASK_SCOPED("star_of_normalized");
262  typedef Element<A, AI> automaton_t;
263  AUTOMATON_TYPES(automaton_t);
264  monoid_elt_t monoid_identity =
265  a.series().monoid().identity(SELECT(monoid_elt_value_t));
266  hstate_t old_i = *a.initial().begin();
267  hstate_t old_f = *a.final().begin();
268  hstate_t new_i = a.add_state();
269  hstate_t new_f = a.add_state();
270 
271  a.add_spontaneous(old_f, old_i, a.get_initial(old_i).get(monoid_identity));
272  a.add_spontaneous(new_i, old_i, a.get_initial(old_i).get(monoid_identity));
273  a.add_spontaneous(old_f, new_f, a.get_final(old_f).get(monoid_identity));
274  a.add_spontaneous(new_i, new_f);
275  a.set_final(new_f);
276  a.unset_final(old_f);
277  a.set_initial(new_i);
278  a.unset_initial(old_i);
279  }
280 
281  template<typename A, typename AI>
282  void
283  star_of_normalized_here(Element<A, AI>& a)
284  {
285  do_star_of_normalized_here(a.structure(), a);
286  }
287 
288  template<typename A, typename AI>
289  Element<A, AI>
290  star_of_normalized(const Element<A, AI>& a)
291  {
292  Element<A, AI> ret(a);
293  do_star_of_normalized_here(ret.structure(), ret);
294  return ret;
295  }
296 
297 } // vcsn
298 
299 #endif // ! VCSN_ALGORITHMS_NORMALIZED_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1