00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_CUT_UP_HXX
00018 # define VCSN_ALGORITHMS_CUT_UP_HXX
00019
00029 namespace vcsn {
00030
00031
00032
00033
00034
00035
00036 template <typename A, typename AI>
00037 bool is_cut_up(const Element<A, AI>& a)
00038 {
00039 BENCH_TASK_SCOPED("is_cut_up");
00040 typedef Element<A, AI> automaton_t;
00041 AUTOMATON_TYPES(automaton_t);
00042
00043 for_all_const_transitions(e, a)
00044 if (! a.series_of(*e).is_finite_app() ||
00045 a.series_of(*e).supp().size() > 1)
00046 return false;
00047
00048 return true;
00049 }
00050
00051
00052
00053
00054
00055
00056 template <typename S, typename T, typename TT, typename Auto, typename Ret>
00057 void do_cut_up(const AutomataBase<S>&,
00058 const rat::exp<T, TT>&,
00059 const Auto& a,
00060 Ret& res)
00061 {
00062 AUTOMATON_TYPES_(Ret, ret_);
00063 typedef typename generalized_traits<Ret>::automaton_t gen_automaton_t;
00064 AUTOMATON_TYPES(gen_automaton_t);
00065
00066 auto_copy(res, a);
00067
00068 std::map<hstate_t, ret_hstate_t> statemap;
00069
00070 ret_transitions_t transitions = res.transitions();
00071
00072 for_all_(ret_transitions_t, e, transitions)
00073 {
00074 if (! res.series_of(*e).is_finite_app() ||
00075 res.series_of(*e).supp().size() > 1)
00076 {
00077 gen_automaton_t tmp(res.structure());
00078 standard_of(tmp, res.series_of(*e).value());
00079
00080 for_all_states(s, tmp)
00081 statemap[*s] = res.add_state();
00082
00083 for_all_initial_states(i, tmp)
00084 res.add_series_transition(res.src_of(*e),
00085 statemap[*i],
00086 tmp.get_initial(*i));
00087
00088 for_all_transitions(ed, tmp)
00089 res.add_transition(statemap[tmp.src_of(*ed)],
00090 statemap[tmp.dst_of(*ed)],
00091 tmp.label_of(*ed));
00092
00093 for_all_final_states(f, tmp)
00094 res.add_series_transition(statemap[*f], res.dst_of(*e),
00095 tmp.get_final(*f));
00096
00097 res.del_transition(*e);
00098 }
00099 }
00100 }
00101
00102
00103
00104
00105
00106
00107 template <typename S, typename T, typename TT, typename Auto, typename Ret>
00108 void do_cut_up(const S&,
00109 const algebra::polynom<T, TT>&,
00110 const Auto& a,
00111 Ret& res)
00112 {
00113 AUTOMATON_TYPES(Ret);
00114 typedef typename Ret::series_set_elt_t::support_t support_t;
00115 int size;
00116
00117 auto_copy(res, a);
00118
00119 transitions_t transitions = res.transitions();
00120
00121 for_all_(transitions_t, e, transitions)
00122 {
00123 series_set_elt_t label(res.structure().series());
00124 label = res.series_of(*e);
00125
00126 if ((size = label.supp().size()) > 1)
00127 {
00128 typename support_t::const_iterator m = label.supp().begin();
00129 for (int i = 0; i < size; ++i, ++m)
00130 {
00131 series_set_elt_t series(res.structure().series());
00132 series.assoc(*m, label.get(*m));
00133 res.add_series_transition(res.src_of(*e),
00134 res.dst_of(*e),
00135 series);
00136 }
00137
00138 res.del_transition(*e);
00139 }
00140 }
00141 }
00142
00143
00144
00145
00146
00147
00148 template <typename A, typename AI>
00149 void
00150 cut_up(const Element<A, AI>& a, Element<A, AI>& res)
00151 {
00152 BENCH_TASK_SCOPED("cut_up");
00153 typedef typename Element<A, AI>::series_set_elt_t::value_t series_impl_t;
00154 do_cut_up(a.structure(), SELECT(series_impl_t), a, res);
00155 }
00156
00157
00158 template <typename A, typename AI>
00159 Element<A, AI>
00160 cut_up(const Element<A, AI>& a)
00161 {
00162 Element<A, AI> res(a.structure());
00163 cut_up(a, res);
00164 return res;
00165 }
00166
00167
00168 template <typename A, typename AI>
00169 void
00170 cut_up_here(Element<A, AI>& a)
00171 {
00172 a = cut_up(a);
00173 }
00174
00175
00176 }
00177
00178
00179 #endif // ! VCSN_ALGORITHMS_CUT_UP_HXX