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