00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef VCSN_ALGORITHMS_STANDARD_HXX
00019 # define VCSN_ALGORITHMS_STANDARD_HXX
00020
00021 # include <vaucanson/algorithms/standard.hh>
00022 # include <vaucanson/algorithms/internal/has_neighbour.hh>
00023
00024 # include <vaucanson/algorithms/sum.hh>
00025 # include <vaucanson/algorithms/accessible.hh>
00026 # include <vaucanson/automata/concept/automata_base.hh>
00027 # include <vaucanson/misc/usual_macros.hh>
00028
00029 # include <set>
00030
00031 namespace vcsn {
00032
00033
00034
00035
00036 template <class A, typename AI>
00037 void
00038 do_in_standardize(const AutomataBase<A>&, Element<A, AI>& a)
00039 {
00040 TIMER_SCOPED("standardize");
00041 typedef Element<A, AI> automaton_t;
00042 AUTOMATON_TYPES(automaton_t);
00043
00044 hstate_t i = a.add_state();
00045 std::list<htransition_t> transition_oi;
00046 series_set_elt_t final_series =
00047 algebra::zero_as<series_set_elt_value_t>::of(a.series());
00048
00049 for_all_const_initial_states(oi, a)
00050 {
00051 series_set_elt_t s = a.get_initial(*oi);
00052
00053
00054 transition_oi.clear();
00055 for (delta_iterator oil(a.value(), *oi);
00056 ! oil.done();
00057 oil.next())
00058 transition_oi.push_back(*oil);
00059 for_all_const_(std::list<htransition_t>, oil, transition_oi)
00060 {
00061 series_set_elt_t t = s * a.series_of(*oil);
00062 a.add_series_transition(i, a.dst_of(*oil), t);
00063 }
00064
00065 final_series += s * a.get_final(*oi);
00066 }
00067
00068
00069
00070
00071
00072 for (initial_iterator oi = a.initial().begin(), next = oi;
00073 oi != a.initial().end();
00074 oi = next)
00075 {
00076 ++next;
00077 if (!has_predecessors(a, *oi))
00078 a.del_state(*oi);
00079 }
00080 a.clear_initial();
00081 a.set_initial(i);
00082 a.set_final(i, final_series);
00083 }
00084
00085 template<typename A, typename AI>
00086 void
00087 standardize(Element<A, AI>& a)
00088 {
00089 do_in_standardize(a.structure(), a);
00090 }
00091
00092
00093
00094
00095
00096 template <typename A, typename AI1, typename AI2>
00097 void
00098 do_union_of_standard_here(const AutomataBase<A>&,
00099 Element<A, AI1>& lhs,
00100 const Element<A, AI2>& rhs)
00101 {
00102 precondition(is_standard(lhs));
00103 precondition(is_standard(rhs));
00104
00105 TIMER_SCOPED("union_of_standard");
00106 typedef Element<A, AI1> lhs_t;
00107 typedef Element<A, AI2> rhs_t;
00108 typedef std::list<typename lhs_t::htransition_t> edelta_ret_t;
00109
00110
00111 typename lhs_t::hstate_t new_i = *lhs.initial().begin();
00112 sum_here(lhs, rhs);
00113
00114
00115
00116 typename lhs_t::initial_support_t initial = lhs.initial();
00117
00118
00119 assertion (initial.size() == 2);
00120 typename lhs_t::initial_iterator i = initial.begin();
00121 typename lhs_t::hstate_t old_i = *i != new_i ? *i : *++i;
00122
00123 lhs.set_final(new_i,
00124 lhs.get_final(new_i) + lhs.get_final(old_i));
00125
00126
00127 edelta_ret_t dst;
00128 for (typename lhs_t::delta_iterator d(lhs.value(), old_i);
00129 ! d.done();
00130 d.next())
00131 dst.push_back(*d);
00132 for_all_const_(edelta_ret_t, d, dst)
00133 {
00134 lhs.add_transition(new_i,
00135 lhs.dst_of(*d),
00136 lhs.label_of(*d));
00137 lhs.del_transition(*d);
00138 }
00139 lhs.del_state(old_i);
00140 }
00141
00142 template<typename A, typename AI1, typename AI2>
00143 void
00144 union_of_standard_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
00145 {
00146 do_union_of_standard_here(lhs.structure(), lhs, rhs);
00147 }
00148
00149 template<typename A, typename AI1, typename AI2>
00150 Element<A, AI1>
00151 union_of_standard(const Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
00152 {
00153 Element<A, AI1> ret(lhs);
00154 union_of_standard_here(ret, rhs);
00155 return ret;
00156 }
00157
00158
00159
00160
00161 template <typename A, typename AI>
00162 bool
00163 do_is_standard(const AutomataBase<A>&, const Element<A, AI>& a)
00164 {
00165 TIMER_SCOPED("is_standard");
00166 typedef Element<A, AI> automaton_t;
00167 typedef typename automaton_t::series_set_elt_value_t series_set_elt_value_t;
00168
00169
00170 if (a.initial().size() != 1)
00171 return false;
00172
00173
00174 typename automaton_t::hstate_t s = *a.initial().begin();
00175 if (a.get_initial(s)
00176 != a.series().identity(SELECT(series_set_elt_value_t)))
00177 return false;
00178
00179
00180 return !has_predecessors(a, s);
00181 }
00182
00183 template<typename A, typename AI>
00184 bool
00185 is_standard(const Element<A, AI>& a)
00186 {
00187 return do_is_standard(a.structure(), a);
00188 }
00189
00190
00191
00192
00193 template <typename A, typename AI1, typename AI2>
00194 void
00195 do_concat_of_standard_here(const AutomataBase<A>&,
00196 Element<A, AI1>& lhs,
00197 const Element<A, AI2>& rhs)
00198 {
00199 precondition(is_standard(lhs));
00200 precondition(is_standard(rhs));
00201
00202 TIMER_SCOPED("concat_of_standard");
00203 typedef Element<A, AI1> lhs_t;
00204 typedef Element<A, AI2> rhs_t;
00205 AUTOMATON_TYPES(lhs_t);
00206 typedef std::map<hstate_t, hstate_t> map_t;
00207 typedef std::list<htransition_t> delta_ret_t;
00208
00209
00210
00211
00212 map_t map_h;
00213 delta_ret_t dst;
00214 hstate_t new_state;
00215
00216
00217 for (typename rhs_t::state_iterator s = rhs.states().begin();
00218 s != rhs.states().end();
00219 ++s)
00220 if (!rhs.is_initial(*s))
00221 {
00222 new_state = lhs.add_state();
00223 map_h[*s] = new_state;
00224 }
00225
00226
00227 for (typename rhs_t::state_iterator i = rhs.states().begin();
00228 i != rhs.states().end();
00229 ++i)
00230 if (!rhs.is_initial(*i))
00231 {
00232 for (typename rhs_t::delta_iterator d(rhs.value(), *i);
00233 ! d.done();
00234 d.next())
00235 lhs.add_transition(map_h[*i],
00236 map_h[rhs.dst_of(*d)],
00237 rhs.label_of(*d));
00238 }
00239
00240
00241 hstate_t rhs_i = *rhs.initial().begin();
00242 dst.clear();
00243 for (typename rhs_t::delta_iterator i(rhs.value(), rhs_i);
00244 ! i.done();
00245 i.next())
00246 dst.push_back(*i);
00247 for_all_const_final_states(f, lhs)
00248 {
00249 typename lhs_t::series_set_elt_t weight = lhs.get_final(*f);
00250 for_all_const_(delta_ret_t, d, dst)
00251 lhs.add_series_transition(*f,
00252 map_h[rhs.dst_of(*d)],
00253 weight * rhs.label_of(*d));
00254 }
00255
00256
00257
00258 typename lhs_t::series_set_elt_t rhs_iw = rhs.get_final(rhs_i);
00259 typename lhs_t::final_support_t support = lhs.final();
00260 for (typename lhs_t::final_iterator next = lhs.final().begin();
00261 next != lhs.final().end();)
00262 {
00263 typename lhs_t::final_iterator f = next;
00264 next++;
00265 lhs.set_final(*f, lhs.get_final(*f) * rhs_iw);
00266 }
00267
00268
00269 for_all_const_(map_t, nf, map_h)
00270 if (rhs.is_final(nf->first))
00271 lhs.set_final(nf->second, rhs.get_final(nf->first));
00272 }
00273
00274 template<typename A, typename AI1, typename AI2>
00275 void
00276 concat_of_standard_here(Element<A, AI1>& lhs, const Element<A, AI2>& rhs)
00277 {
00278 do_concat_of_standard_here(lhs.structure(), lhs, rhs);
00279 }
00280
00281 template<typename A, typename AI1, typename AI2>
00282 Element<A, AI1>
00283 concat_of_standard(const Element<A, AI1>& lhs,
00284 const Element<A, AI2>& rhs)
00285 {
00286 Element<A, AI1> ret(lhs);
00287 do_concat_of_standard_here(ret.structure(), ret, rhs);
00288 return ret;
00289 }
00290
00291
00292
00293
00294 template <typename A, typename AI>
00295 void
00296 do_star_of_standard_here(const AutomataBase<A>&, Element<A, AI>& a)
00297 {
00298 precondition(is_standard(a));
00299
00300 TIMER_SCOPED("star_of_standard");
00301 typedef Element<A, AI> automaton_t;
00302 AUTOMATON_TYPES(automaton_t);
00303 typedef std::list<htransition_t> edelta_ret_t;
00304
00305 edelta_ret_t dst;
00306 hstate_t new_i = *a.initial().begin();
00307 series_set_elt_t out_mult = a.get_final(new_i);
00308
00309 out_mult.star();
00310 for (delta_iterator i(a.value(), new_i);
00311 ! i.done();
00312 i.next())
00313 dst.push_back(*i);
00314 for_all_final_states(f, a)
00315 {
00316 if (*f != new_i)
00317 {
00318 series_set_elt_t f_mult = a.get_final(*f) * out_mult;
00319 a.set_final(*f, f_mult);
00320 for_all_const_(edelta_ret_t, d, dst)
00321 a.add_series_transition(*f, a.dst_of(*d), f_mult * a.label_of(*d));
00322 }
00323 }
00324 a.set_final(new_i, out_mult);
00325 }
00326
00327 template<typename A, typename AI>
00328 void
00329 star_of_standard_here(Element<A, AI>& a)
00330 {
00331 do_star_of_standard_here(a.structure(), a);
00332 }
00333
00334 template<typename A, typename AI>
00335 Element<A, AI>
00336 star_of_standard(const Element<A, AI>& a)
00337 {
00338 Element<A, AI> ret(a);
00339 do_star_of_standard_here(ret.structure(), ret);
00340 return ret;
00341 }
00342
00343 }
00344
00345 #endif // ! VCSN_ALGORITHMS_STANDARD_HXX