Vaucanson  1.4.1
projection.hxx
1 // projection.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 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_PROJECTION_HXX
18 # define VCSN_ALGORITHMS_PROJECTION_HXX
19 
20 # include <map>
21 
22 # include <vaucanson/algorithms/projection.hh>
23 
24 namespace vcsn
25 {
26  template <typename auto_t, typename trans_t>
27  void
28  set_states(const trans_t& fmp_trans, auto_t& res,
29  std::map<typename trans_t::hstate_t, typename auto_t::hstate_t>&
30  stmap)
31  {
32  AUTOMATON_TYPES_(trans_t, trans_);
33  AUTOMATON_TYPES(auto_t);
34 
35  typedef typename trans_series_set_elt_t::support_t trans_support_t;
36 
37  const series_set_t& series = res.structure().series();
38  const monoid_t& monoid = res.structure().series().monoid();
39 
40  for_all_const_states(fmp_s, fmp_trans)
41  {
42  hstate_t s = res.add_state();
43  stmap[*fmp_s] = s;
44 
45  if (fmp_trans.is_initial(*fmp_s))
46  {
47  trans_series_set_elt_t in = fmp_trans.get_initial(*fmp_s);
48  trans_support_t supp = in.supp();
49 
50  semiring_elt_t in_semi_elt = in.get(*(supp.begin()));
51  series_set_elt_t series_elt(series);
52 
53  series_elt.assoc(monoid_elt_t(monoid,
54  algebra::identity_as<
55  monoid_elt_value_t>::
56  of(monoid).value()),
57  in_semi_elt);
58  res.set_initial(s, series_elt);
59  }
60 
61  if (fmp_trans.is_final(*fmp_s))
62  {
63  trans_series_set_elt_t out = fmp_trans.get_final(*fmp_s);
64  trans_support_t supp = out.supp();
65 
66  semiring_elt_t out_semi_elt = out.get(*(supp.begin()));
67  series_set_elt_t series_elt(series);
68 
69  series_elt.assoc(monoid_elt_t(monoid,
70  algebra::identity_as<
71  monoid_elt_value_t>::
72  of(monoid).value()),
73  out_semi_elt);
74  res.set_final(s, series_elt);
75  }
76  }
77  }
78 
79  /*---------.
80  | Identity |
81  `---------*/
82 
83  template <typename S1, typename S2, typename M1, typename M2,
84  typename auto_t, typename trans_t>
85  void
86  do_identity(const AutomataBase<S1>&,
87  const algebra::FreeMonoidBase<M1>&,
88  const AutomataBase<S2>&,
89  const algebra::FreeMonoidProduct<M1,M2>&,
90  const auto_t& aut, trans_t& res)
91  {
92  BENCH_TASK_SCOPED("identity");
93  AUTOMATON_TYPES_(auto_t, aut_);
94  AUTOMATON_TYPES(trans_t);
95 
96  std::map<hstate_t, aut_hstate_t> stmap;
97  typedef typename aut_series_set_elt_t::support_t aut_support_t;
98 
99  const series_set_t& series = res.structure().series();
100  const monoid_t& monoid = res.structure().series().monoid();
101  const aut_monoid_t& aut_monoid = aut.structure().series().monoid();
102 
103  set_states(aut, res, stmap);
104 
105  for_all_const_transitions_(aut_, aut_e, aut)
106  {
107  const aut_series_set_elt_t aut_series_elt = aut.series_of(*aut_e);
108 
109  // If the transition is labeled by a+bc, we want to output
110  // two transitions labeled by (a,a) and (bc,bc).
111  aut_support_t aut_supp = aut_series_elt.supp();
112  for_all_const_(aut_support_t, label, aut_supp)
113  {
114  const aut_monoid_elt_t aut_monoid_elt(aut_monoid, *label);
115  const monoid_elt_value_t word(aut_monoid_elt.value(),
116  aut_monoid_elt.value());
117 
118  series_set_elt_t series_elt(series);
119  series_elt.assoc(monoid_elt_t(monoid, word),
120  aut_series_elt.get(aut_monoid_elt));
121 
122  res.add_series_transition(stmap[aut.src_of(*aut_e)],
123  stmap[aut.dst_of(*aut_e)], series_elt);
124  }
125  }
126  }
127 
128  template <typename S, typename S2, typename T, typename T2>
129  void
130  identity(const Element<S,T>& aut, Element<S2, T2>& res)
131  {
132  do_identity(aut.structure(), aut.structure().series().monoid(),
133  res.structure(), res.structure().series().monoid(), aut, res);
134  }
135 
136  /*--------------.
137  | Partial erase |
138  `--------------*/
139 
140  template <typename S1, typename S2, typename M1, typename M2,
141  typename auto_t, typename trans_t>
142  void
143  do_partial_erase(const AutomataBase<S1>&,
144  const algebra::FreeMonoidBase<M1>&,
145  const AutomataBase<S2>&,
146  const algebra::FreeMonoidProduct<M1,M2>&,
147  const auto_t& aut, trans_t& res)
148  {
149  BENCH_TASK_SCOPED("partial erase");
150  AUTOMATON_TYPES_(auto_t, aut_);
151  AUTOMATON_TYPES(trans_t);
152 
153  std::map<hstate_t, aut_hstate_t> stmap;
154  typedef typename aut_series_set_elt_t::support_t aut_support_t;
155 
156  const series_set_t& series = res.structure().series();
157  const monoid_t& monoid = res.structure().series().monoid();
158  const aut_monoid_t& aut_monoid = aut.structure().series().monoid();
159  aut_monoid_elt_value_t empty_word =
160  algebra::identity_as<aut_monoid_elt_value_t>::of(aut_monoid).value();
161 
162  set_states(aut, res, stmap);
163 
164  for_all_const_transitions_(aut_, aut_e, aut)
165  {
166  const aut_series_set_elt_t aut_series_elt = aut.series_of(*aut_e);
167 
168  // If the transition is labeled by a+bc, we want to output
169  // two transitions labeled by (a,a) and (bc,bc).
170  aut_support_t aut_supp = aut_series_elt.supp();
171  for_all_const_(aut_support_t, label, aut_supp)
172  {
173  const aut_monoid_elt_t aut_monoid_elt(aut_monoid, *label);
174  const monoid_elt_value_t word(aut_monoid_elt.value(),
175  empty_word);
176 
177  series_set_elt_t series_elt(series);
178  series_elt.assoc(monoid_elt_t(monoid, word),
179  aut_series_elt.get(aut_monoid_elt));
180 
181  res.add_series_transition(stmap[aut.src_of(*aut_e)],
182  stmap[aut.dst_of(*aut_e)], series_elt);
183  }
184  }
185  }
186 
187  template <typename S, typename S2, typename T, typename T2>
188  void
189  partial_erase(const Element<S,T>& aut, Element<S2, T2>& res)
190  {
191  do_partial_erase(aut.structure(), aut.structure().series().monoid(),
192  res.structure(), res.structure().series().monoid(), aut, res);
193  }
194 
195 } // ! vcsn
196 
197 #endif // ! VCSN_ALGORITHMS_PROJECTION_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1