17 #ifndef VCSN_ALGORITHMS_PRODUCT_HXX
18 # define VCSN_ALGORITHMS_PRODUCT_HXX
29 # endif // ! VCSN_NDEBUG
31 # include <vaucanson/automata/concept/automata_base.hh>
32 # include <vaucanson/misc/usual_macros.hh>
33 # include <vaucanson/automata/implementation/geometry.hh>
42 template<
typename A,
typename T,
typename U>
46 typedef AutomataBase<A> structure_t;
47 typedef Element<A, T> lhs_t;
48 typedef Element<A, U> rhs_t;
49 typedef lhs_t output_t;
50 typedef std::map<
typename output_t::hstate_t,
51 std::pair<typename lhs_t::hstate_t, typename rhs_t::hstate_t> >
54 Product (
const structure_t& structure,
55 const bool use_geometry)
56 : use_geometry_(use_geometry),
57 series_(structure.series()),
58 monoid_(series_.monoid()),
59 semiring_zero_(series_.semiring().zero(
SELECT(semiring_elt_value_t)))
65 operator() (output_t& output,
70 BENCH_TASK_SCOPED(
"product");
76 this->initialize_queue(output, lhs, rhs, m);
78 while (not to_process_.empty())
80 const pair_hstate_t current_pair = to_process_.front();
83 const hstate_t lhs_s = current_pair.first;
84 const hstate_t rhs_s = current_pair.second;
85 const hstate_t current_state = visited_[current_pair];
87 series_set_elt_t prod_series(series_);
88 if (is_product_not_null(lhs.get_initial(lhs_s), rhs.get_initial(rhs_s), prod_series))
89 output.set_initial(current_state, prod_series);
92 series_set_elt_t prod_series(series_);
93 if (is_product_not_null(lhs.get_final(lhs_s), rhs.get_final(rhs_s), prod_series))
94 output.set_final(current_state, prod_series);
96 for (
typename lhs_t::delta_iterator l(lhs.value(), lhs_s);
99 for (
typename rhs_t::delta_iterator r(rhs.value(), rhs_s);
103 series_set_elt_t prod_series(series_);
105 if (is_product_not_null(lhs.series_of(*l), rhs.series_of(*r), prod_series))
107 const pair_hstate_t new_pair(lhs.dst_of(*l), rhs.dst_of(*r));
108 typename visited_t::const_iterator found = visited_.find(new_pair);
111 if (found == visited_.end())
113 dst = output.add_state();
115 this->add_state_to_process(output, lhs, rhs, m, dst, new_pair);
119 output.add_series_transition(current_state, dst, prod_series);
131 template <
typename Output,
typename Lhs,
typename Rhs>
133 setcoordfrom (Output& a,
136 const typename Output::hstate_t state,
137 const typename Lhs::hstate_t x_state,
138 const typename Rhs::hstate_t y_state)
140 typename std::map<
typename Lhs::hstate_t,
141 typename Lhs::geometry_t::coords_t>::const_iterator iter;
142 typename std::map<
typename Rhs::hstate_t,
143 typename Rhs::geometry_t::coords_t>::const_iterator iter2;
146 iter = lhs.geometry().states().find(x_state);
147 if (iter != lhs.geometry().states().end())
148 x = iter->second.first;
150 iter2 = rhs.geometry().states().find(y_state);
151 if (iter2 != rhs.geometry().states().end())
152 y = iter2->second.second;
154 a.geometry().states()[state] = std::make_pair(x, y);
163 std::map<hstate_t,bool> visited;
164 std::stack<hstate_t> stack;
166 for_all_const_states(i, a)
173 for_all_const_initial_states(i, a)
177 while (!stack.empty())
179 hstate_t i = stack.top();
186 a.geometry()[i] = std::make_pair(x, x);
189 for (delta_iterator j(a.value(), i);
192 stack.push(a.dst_of(*j));
201 template <
typename Output,
typename Lhs,
typename Rhs>
203 setcoordfrom (Output& a,
206 const typename Output::hstate_t state,
207 const typename Lhs::hstate_t x_state,
208 const typename Rhs::hstate_t y_state) {};
212 AUTOMATON_TYPES(output_t);
214 typedef std::pair<typename lhs_t::hstate_t, typename rhs_t::hstate_t>
216 typedef std::list<htransition_t> delta_ret_t;
217 typedef std::map<pair_hstate_t, hstate_t> visited_t;
218 typedef typename series_set_elt_t::support_t support_t;
222 add_state_to_process (output_t& output,
226 const hstate_t& new_state,
227 const pair_hstate_t& new_pair)
229 m[new_state] = new_pair;
230 visited_[new_pair] = new_state;
231 to_process_.push(new_pair);
233 # define if_(Cond, ThenClause, ElseClause) \
234 misc::static_if_simple<Cond, ThenClause, ElseClause>::t
235 # define eq_(Type1, Type2) \
236 misc::static_eq<Type1, Type2>::value
237 # define DECLARE_GEOMETRY(Type) \
238 typedef geometry<typename Type::hstate_t, typename Type::htransition_t, typename Type::geometry_coords_t> geometry_ ## Type ;
240 DECLARE_GEOMETRY(output_t)
241 DECLARE_GEOMETRY(lhs_t)
242 DECLARE_GEOMETRY(rhs_t)
244 if_(eq_(typename output_t::geometry_t, geometry_output_t) and \
245 eq_(typename rhs_t::geometry_t, geometry_rhs_t) and \
246 eq_(typename lhs_t::geometry_t, geometry_lhs_t), \
248 ::setcoordfrom(output, lhs, rhs,
249 new_state, new_pair.first, new_pair.second);
256 initialize_queue (output_t& output,
261 for_all_const_initial_states(lhs_s, lhs)
262 for_all_const_initial_states(rhs_s, rhs)
264 const pair_hstate_t new_pair(*lhs_s, *rhs_s);
265 const hstate_t new_state = output.add_state();
267 this->add_state_to_process(output, lhs, rhs, m, new_state, new_pair);
272 is_product_not_null (
const series_set_elt_t left_series,
273 const series_set_elt_t right_series,
274 series_set_elt_t& prod_series)
const
276 bool prod_is_not_null =
false;
279 for_all_(support_t, supp, right_series.supp())
281 const monoid_elt_t supp_elt (monoid_, *supp);
282 const semiring_elt_t l = left_series.get(supp_elt);
283 const semiring_elt_t r = right_series.get(supp_elt);
284 const semiring_elt_t p = l * r;
285 if (p != semiring_zero_)
287 prod_series.assoc(*supp, p.value());
288 prod_is_not_null =
true;
291 return (prod_is_not_null);
295 const bool use_geometry_;
300 std::queue<pair_hstate_t> to_process_;
303 const series_set_t& series_;
304 const monoid_t& monoid_;
306 const semiring_elt_t semiring_zero_;
313 template<
typename A,
typename T,
typename U>
315 product (
const Element<A, T>& lhs,
const Element<A, U>& rhs,
316 std::map<
typename T::hstate_t,
317 std::pair<typename T::hstate_t, typename U::hstate_t> >& m,
318 const bool use_geometry)
320 Element<A, T> ret(lhs.structure());
321 Product<A, T, U> do_product(ret.structure(), use_geometry);
322 return do_product (ret, lhs, rhs, m);
325 template<
typename A,
typename T,
typename U>
327 product (
const Element<A, T>& lhs,
const Element<A, U>& rhs,
328 const bool use_geometry)
330 std::map<
typename T::hstate_t,
331 std::pair<typename T::hstate_t, typename U::hstate_t> > m;
332 return product (lhs, rhs, m, use_geometry);
337 #endif // ! VCSN_ALGORITHMS_PRODUCT_HXX