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>
00039 void do_realtime_words(Auto& a)
00040 {
00041 AUTOMATON_TYPES(Auto);
00042 hstate_t s1;
00043 semiring_elt_t s_ident = algebra::identity_as<semiring_elt_value_t>
00044 ::of(a.structure().series().semiring());
00045
00046 typedef std::vector<htransition_t> transition_vector_t;
00047 transitions_t transitions = a.transitions();
00048 transition_vector_t tmp_trans;
00049 for_all_(transitions_t, e, transitions)
00050 tmp_trans.push_back(*e);
00051
00052 for_all(typename transition_vector_t, e, tmp_trans)
00053 {
00054 hstate_t start = a.src_of(*e);
00055 hstate_t stop = a.dst_of(*e);
00056 series_set_elt_t label = a.series_of(*e);
00057
00058 assert(label.supp().begin() != label.supp().end());
00059
00060 monoid_elt_t m1(a.structure().series().monoid(), *label.supp().begin());
00061 monoid_elt_value_t w1 = m1.value();
00062 unsigned int size = m1.length();
00063
00064 if (size > 1)
00065 {
00066 monoid_elt_t m(a.structure().series().monoid());
00067
00068 semiring_elt_t s = label.get(m1);
00069 series_set_elt_t in_series(a.structure().series());
00070 typename monoid_elt_t::iterator l = m1.begin();
00071
00072 m = *l;
00073
00074 in_series.assoc(m, s);
00075
00076 s1 = a.add_state();
00077 a.add_series_transition(start, s1, in_series);
00078
00079 l++;
00080 for (typename monoid_elt_t::iterator end = m1.begin() + (size - 1);
00081 l != end; ++l)
00082 {
00083 m = *l;
00084 hstate_t s0 = s1;
00085 s1 = a.add_state();
00086 series_set_elt_t series(a.structure().series());
00087 series.assoc(m, s_ident);
00088 a.add_series_transition(s0, s1, series);
00089 }
00090
00091 m = *l;
00092
00093 series_set_elt_t out_series(a.structure().series());
00094 out_series.assoc(m, s_ident);
00095
00096 a.add_series_transition(s1, stop, out_series);
00097 a.del_transition(*e);
00098 }
00099 }
00100 }
00101
00102
00103 template <class S, class T>
00104 void realtime_words_here(Element<S, T>& res)
00105 {
00106 typedef Element<S, T> auto_t;
00107 AUTOMATON_TYPES(auto_t);
00108 typedef std::vector<hstate_t> state_vector_t;
00109 typedef std::vector<htransition_t> transition_vector_t;
00110 state_vector_t tmp;
00111
00112
00113 cut_up_here(res);
00114
00115
00116 tmp.reserve(res.initial().size());
00117 for_all_const_initial_states(i, res)
00118 tmp.push_back(*i);
00119 for_all(typename state_vector_t, i, tmp)
00120 {
00121 series_set_elt_t l = res.get_initial(*i);
00122 assert(l.supp().begin() != l.supp().end());
00123 monoid_elt_t m(res.structure().series().monoid(), *l.supp().begin());
00124 if (m.length() > 0)
00125 {
00126 hstate_t s = res.add_state();
00127 res.add_series_transition(*i, s, l);
00128 res.set_initial(s);
00129 res.unset_initial(*i);
00130 }
00131 }
00132 tmp.clear();
00133
00134
00135 tmp.reserve(res.final().size());
00136 for_all_const_final_states(f, res)
00137 tmp.push_back(*f);
00138 for_all(typename state_vector_t, f, tmp)
00139 {
00140 series_set_elt_t l = res.get_final(*f);
00141 assert(l.supp().begin() != l.supp().end());
00142 monoid_elt_t m(res.structure().series().monoid(), *l.supp().begin());
00143 if (m.length() > 0)
00144 {
00145 hstate_t s = res.add_state();
00146 res.add_series_transition(s, *f, l);
00147 res.set_final(s);
00148 res.unset_final(*f);
00149 }
00150 }
00151
00152
00153
00154 do_realtime_words(res);
00155 }
00156
00157
00158
00159
00160
00161
00162 template <class A, typename AI>
00163 bool
00164 do_is_realtime(const AutomataBase<A>&, const Element<A, AI>& a)
00165 {
00166 TIMER_SCOPED("is_realtime (automaton)");
00167 typedef Element<A, AI> automaton_t;
00168 AUTOMATON_TYPES(automaton_t);
00169 for_all_const_transitions(e, a)
00170 if (!is_support_in_alphabet(a.series_of(*e)))
00171 return false;
00172 return true;
00173 }
00174
00175
00176
00177
00178
00179
00180 template<typename A, typename AI>
00181 void
00182 do_realtime_here(const AutomataBase<A>&,
00183 Element<A, AI>& a,
00184 misc::direction_type dir = misc::backward)
00185 {
00186 realtime_words_here(a);
00187
00188 eps_removal_here(a, dir);
00189
00190
00191 if (dir == misc::forward)
00192 coaccessible_here(a);
00193 else
00194 accessible_here(a);
00195 }
00196
00197
00198 template<typename A, typename AI>
00199 void
00200 realtime_here(Element<A, AI>& a, misc::direction_type dir)
00201 {
00202 do_realtime_here(a.structure(), a, dir);
00203 }
00204
00205
00206
00207
00208
00209
00210 template<typename A, typename AI>
00211 Element<A, AI>
00212 do_realtime(const AutomataBase<A>& b,
00213 const Element<A, AI>& a,
00214 misc::direction_type dir = misc::backward)
00215 {
00216 Element<A, AI> ret(a);
00217 do_realtime_here(b, ret, dir);
00218 return ret;
00219 }
00220
00221 template<typename A, typename AI>
00222 Element<A, AI>
00223 realtime(const Element<A, AI>& a, misc::direction_type dir)
00224 {
00225 return do_realtime(a.structure(), a, dir);
00226 }
00227
00228
00229 }
00230
00231 #endif // ! VCSN_ALGORITHMS_REALTIME_HXX