00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_REALTIME_HXX
00018 # define VCSN_ALGORITHMS_REALTIME_HXX
00019
00020 # include <vaucanson/algorithms/realtime.hh>
00021
00022 # include <vaucanson/algorithms/eps_removal.hh>
00023 # include <vaucanson/algorithms/accessible.hh>
00024 # include <vaucanson/algorithms/cut_up.hh>
00025
00026 # include <vaucanson/automata/concept/automata_base.hh>
00027
00028 # include <deque>
00029 # include <set>
00030
00031 namespace vcsn {
00032
00033
00034
00035
00036
00037
00038 template <class Auto, class Label>
00039 int do_realtime_words(Auto& a,
00040 hstate_t start, hstate_t stop,
00041 const Label& label, bool initial, bool final)
00042 {
00043 AUTOMATON_TYPES(Auto);
00044 hstate_t s1;
00045 semiring_elt_t s_ident = algebra::identity_as<semiring_elt_value_t>
00046 ::of(a.structure().series().semiring());
00047
00048
00049 if (label.supp().begin() == label.supp().end())
00050 return 0;
00051
00052 monoid_elt_t m1(a.structure().series().monoid(), *label.supp().begin());
00053 monoid_elt_value_t w1 = m1.value();
00054
00055 unsigned int size = m1.length();
00056
00057 if (size > 1)
00058 {
00059 monoid_elt_t m(a.structure().series().monoid());
00060
00061 semiring_elt_t s = label.get(m1);
00062 series_set_elt_t in_series(a.structure().series());
00063 typename monoid_elt_t::iterator l = m1.begin();
00064
00065 m = *l;
00066
00067 in_series.assoc(m, s);
00068
00069 if (initial)
00070 {
00071 hstate_t s0 = a.add_state();
00072 a.set_initial(s0, in_series);
00073 a.unset_initial(stop);
00074 s1 = s0;
00075 }
00076 else
00077 {
00078 hstate_t s0 = start;
00079 s1 = a.add_state();
00080 a.add_series_transition(s0, s1, in_series);
00081 }
00082
00083 l++;
00084 for (typename monoid_elt_t::iterator end = m1.begin() + (size - 1);
00085 l != end; ++l)
00086 {
00087 m = *l;
00088 hstate_t s0 = s1;
00089 s1 = a.add_state();
00090 series_set_elt_t series(a.structure().series());
00091 series.assoc(m, s_ident);
00092 a.add_series_transition(s0, s1, series);
00093 }
00094
00095 m = *l;
00096
00097 series_set_elt_t out_series(a.structure().series());
00098 out_series.assoc(m, s_ident);
00099
00100 if (final)
00101 {
00102 a.unset_final(start);
00103 a.set_final(s1, out_series);
00104 }
00105 else
00106 a.add_series_transition(s1, stop, out_series);
00107
00108 return 1;
00109 }
00110
00111 return 0;
00112 }
00113
00114
00115 template <class S, class T>
00116 void realtime_words_here(Element<S, T>& res)
00117 {
00118 typedef Element<S, T> auto_t;
00119 AUTOMATON_TYPES(auto_t);
00120 typedef std::vector<hstate_t> vector_t;
00121
00122
00123 cut_up_here(res);
00124
00125 vector_t tmp(res.initial().size());
00126 for_all_initial_states(i, res)
00127 tmp.push_back(*i);
00128 for_all(vector_t, i, tmp)
00129 do_realtime_words(res, hstate_t(), *i, res.get_initial(*i), true, false);
00130
00131 tmp.clear();
00132 for_all_final_states(f, res)
00133 tmp.push_back(*f);
00134 for_all(vector_t, f, tmp)
00135 do_realtime_words(res, *f, hstate_t(), res.get_final(*f), false, true);
00136
00137 transitions_t transitions = res.transitions();
00138 for_all_(transitions_t, e, transitions)
00139 if (do_realtime_words(res, res.src_of(*e), res.dst_of(*e),
00140 res.series_of(*e), false, false))
00141 res.del_transition(*e);
00142 }
00143
00144
00145
00146
00147
00148
00149 template <class A_, typename Auto_>
00150 bool
00151 do_is_realtime(const AutomataBase<A_>&, const Auto_& a)
00152 {
00153 TIMER_SCOPED("is_realtime (automaton)");
00154 AUTOMATON_TYPES(Auto_);
00155 for_all_transitions(e, a)
00156 if (!is_letter_support(a.series_of(*e)))
00157 return false;
00158 return true;
00159 }
00160
00161
00162
00163
00164
00165
00166 template<typename Auto_, typename A_>
00167 void
00168 do_realtime_here(const AutomataBase<A_>&, Auto_& a,
00169 misc::direction_type type = misc::forward)
00170 {
00171 realtime_words_here(a);
00172
00173 eps_removal_here(a, type);
00174
00175 if (type == misc::forward)
00176 coaccessible_here(a);
00177 else
00178 accessible_here(a);
00179 }
00180
00181
00182 template<typename S, typename T>
00183 void
00184 realtime_here(Element<S, T>& a, misc::direction_type type)
00185 {
00186 do_realtime_here(a.structure(), a, type);
00187 }
00188
00189
00190
00191
00192
00193
00194 template<typename Auto_, typename A_>
00195 Auto_
00196 do_realtime(const AutomataBase<A_>&b,
00197 const Auto_& a,
00198 misc::direction_type type = misc::forward)
00199 {
00200 Auto_ ret(a);
00201 do_realtime_here(b, ret, type);
00202 return ret;
00203 }
00204
00205 template<typename A, typename T>
00206 Element<A, T>
00207 realtime(const Element<A, T>& a, misc::direction_type type)
00208 {
00209 return do_realtime(a.structure(), a, type);
00210 }
00211
00212
00213 }
00214
00215 #endif // ! VCSN_ALGORITHMS_REALTIME_HXX