Vaucanson  1.4.1
extension.hxx
1 // extension.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 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_EXTENSION_HXX
18 # define VCSN_ALGORITHMS_EXTENSION_HXX
19 
20 # include <vaucanson/algorithms/extension.hh>
21 # include <vaucanson/misc/usual_macros.hh>
22 
23 namespace vcsn {
24 
25  template <typename S, typename K, typename T, typename Auto_t>
26  typename identity_transducer_helper<S, K, T>::ret
27  do_extension(const AutomataBase<S>& s,
28  const Auto_t& a)
29  {
30  AUTOMATON_TYPES(Auto_t);
31  // ret_t is the type of the transducer returned.
32  typedef typename identity_transducer_helper<S, K, T>::ret ret_t;
33 
34  AUTOMATON_TYPES_(ret_t, t_);
35  typedef typename ret_t::set_t set_t;
36  typedef typename set_t::series_set_t o_series_set_t;
37  typedef typename ret_t::series_set_elt_t output_series_set_elt_t;
38  typedef typename series_set_elt_t::support_t support_t;
39 
40  set_t
41  ts(o_series_set_t (a.structure().series(),
42  a.structure().series().monoid()));
43  ret_t t_ret(ts);
44 
45  monoid_elt_t neutre = a.series().monoid().VCSN_EMPTY_;
46  monoid_elt_t t_neutre = t_ret.series().monoid().
47  identity(SELECT(typename t_monoid_elt_t::value_t));
48 
49  std::vector<hstate_t> conv(a.states().size());
50 
51  for_all_const_states (s, a)
52  conv[t_ret.add_state()] = *s;
53 
54  for_all_const_transitions (e, a)
55  {
56  series_set_elt_t t = a.series_of(*e);
57  series_set_elt_t s(t);
58  output_series_set_elt_t os(t_ret.structure().series());
59  support_t supp = s.supp();
60  for_all_const_(support_t, m, supp)
61  {
62  series_set_elt_t tmp(a.structure().series());
63  // try to associate the neutral monoid element with a weight
64  // to create a series which will be a weight in the series os
65  tmp.assoc(neutre, s.get(*m));
66  os.assoc(*m, tmp);
67  }
68  htransition_t f = t_ret.add_series_transition(conv[a.src_of(*e)],
69  conv[a.dst_of(*e)],
70  os);
71  }
72 
73  initial_iterator i;
74  for (initial_iterator next = a.initial().begin();
75  next != a.initial().end();)
76  {
77  //We need to store the next iterator before using the current one
78  //to avoid an invalid iterator after having called set_final.
79  //Indeed, set_final can delete the iterator if its second parameter
80  //is the zero of the serie.
81  i = next;
82  next++;
83 
84  series_set_elt_t a_series = a.get_initial(*i);
85  t_series_set_elt_t s;
86  s.set(t_neutre, a_series);
87  t_ret.set_initial(conv[*i], s);
88  }
89 
90  final_iterator f;
91  for (final_iterator next = a.final().begin();
92  next != a.final().end();)
93  {
94  //We need to store the next iterator before using the current one
95  //to avoid an invalid iterator after having called set_final.
96  //Indeed, set_final can delete the iterator if its second parameter
97  //is the zero of the serie.
98  f = next;
99  next++;
100  series_set_elt_t a_series = a.get_final(*f);
101  t_series_set_elt_t s;
102  s.value_set(t_neutre, a_series);
103  t_ret.set_final(conv[*f], s);
104  }
105 
106  return t_ret;
107  }
108 
109  template<typename S, typename K, typename T>
110  typename identity_transducer_helper<S, K, T>::ret
111  extension(const Element<S, T>& a)
112  {
113  BENCH_TASK_SCOPED("extension/1");
114  return do_extension(a.structure(), a);
115  }
116 
117 
118  /*----------------.
119  | Two arguments. |
120  `----------------*/
121 
122 
123  template<typename SA, typename ST, typename Auto_t, typename Trans_t>
124  Trans_t do_extension(const AutomataBase<SA>&,
125  const TransducerBase<ST>&,
126  const Auto_t& a,
127  const Trans_t& t)
128  {
129  AUTOMATON_TYPES_(Trans_t, t_);
130  AUTOMATON_TYPES_(Auto_t, a_);
131  typedef typename Auto_t::hstate_t hstate_t;
132  typedef typename Trans_t::series_set_elt_t t_output_series_set_elt_t;
133  typedef typename Auto_t::series_set_elt_t::support_t a_support_t;
134  typedef typename Trans_t::semiring_elt_t t_weight_t;
135 
136  Trans_t tt(t.structure());
137  std::map<hstate_t, hstate_t> conv;
138 
139  a_monoid_elt_t a_neutre =
140  a.series().monoid().identity(SELECT(typename a_monoid_elt_t::value_t));
141  t_monoid_elt_t t_neutre =
142  t.series().monoid().identity(SELECT(typename t_monoid_elt_t::value_t));
143 
144  for(a_state_iterator p = a.states().begin(); p != a.states().end(); ++p)
145  conv[*p] = tt.add_state();
146 
147  // convert transitions
148  for(a_transition_iterator e = a.transitions().begin();
149  e != a.transitions().end(); ++e)
150  {
151  a_series_set_elt_t s_ = a.series_of(*e);
152  a_series_set_elt_t s(s_);
153 
154  t_output_series_set_elt_t os(t.structure().series());
155 
156  a_support_t supp = s.supp();
157  for(typename a_support_t::const_iterator m = supp.begin();
158  m != supp.end(); ++m)
159  {
160  t_weight_t tmp(t.structure().series().semiring());
161  tmp.assoc(a_neutre, s.get(*m));
162  os.assoc(a_monoid_elt_t (a.structure().series().monoid(), *m), tmp);
163  }
164 
165  tt.add_series_transition(conv[a.src_of(*e)], conv[a.dst_of(*e)], os);
166  }
167 
168  a_initial_iterator i;
169  for (a_initial_iterator next = a.initial().begin();
170  next != a.initial().end();)
171  {
172  //We need to store the next iterator before using the current one
173  //to avoid an invalid iterator after having called set_final.
174  //Indeed, set_final can delete the iterator if its second parameter
175  //is the zero of the serie.
176  i = next;
177  next++;
178  a_series_set_elt_t a_series = a.get_initial(*i);
179  t_series_set_elt_t s (t.structure().series());
180  s.assoc(t_neutre, a_series);
181  tt.set_initial(conv[*i], s);
182  }
183 
184  a_final_iterator f;
185  for (a_final_iterator next = a.final().begin();
186  next != a.final().end();)
187  {
188  //We need to store the next iterator before using the current one
189  //to avoid an invalid iterator after having called set_final.
190  //Indeed, set_final can delete the iterator if its second parameter
191  //is the zero of the serie.
192  f = next;
193  next++;
194  a_series_set_elt_t a_series = a.get_final(*f);
195  t_series_set_elt_t s (t.structure().series());
196  s.assoc(t_neutre, a_series);
197  tt.set_final(conv[*f], s);
198  }
199 
200  return tt;
201  }
202 
203  template<typename SA, typename TA, typename ST, typename TT>
204  Element<ST, TT>
205  extension(const Element<SA, TA>& a, const Element<ST, TT>& t)
206  {
207  BENCH_TASK_SCOPED("extension/2");
208  return do_extension(a.structure(), t.structure(), a, t);
209  }
210 
211 }
212 
213 #endif // ! VCSN_ALGORITHMS_EXTENSION_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1