realtime.hxx

00001 // realtime.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
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   | do_realtime_words.  |
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     // perform cut-up.
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   | is_realtime.  |
00148   `--------------*/
00149   template <class A_, typename Auto_>
00150   bool
00151   do_is_realtime(const AutomataBase<A_>&,
00152                  const Auto_&              a)
00153   {
00154     for (typename Auto_::transition_iterator e = a.transitions().begin();
00155          e != a.transitions().end();
00156          ++e)
00157       if (a.series_of(*e) ==
00158           a.structure().series().
00159           identity(SELECT(typename Auto_::series_set_elt_value_t)))
00160         return false;
00161     return true;
00162   }
00163 
00164 
00165   /*--------------.
00166   | realtime_here. |
00167   `--------------*/
00168 
00169   template<typename Auto_, typename A_>
00170   void
00171   do_realtime_here(const AutomataBase<A_>&, Auto_& a,
00172                    misc::direction_type type = misc::forward)
00173   {
00174     realtime_words_here(a);
00175 
00176     eps_removal_here(a, type);
00177 
00178     if (type == misc::forward)
00179       coaccessible_here(a);
00180     else
00181       accessible_here(a);
00182   }
00183 
00184 
00185   template<typename S, typename T>
00186   void
00187   realtime_here(Element<S, T>& a, misc::direction_type type)
00188   {
00189     do_realtime_here(a.structure(), a, type);
00190   }
00191 
00192 
00193   /*-----------.
00194   | realtime.  |
00195   `-----------*/
00196 
00197   template<typename Auto_, typename A_>
00198   Auto_
00199   do_realtime(const AutomataBase<A_>&b,
00200               const Auto_& a,
00201               misc::direction_type type = misc::forward)
00202   {
00203     Auto_ ret(a);
00204     do_realtime_here(b, ret, type);
00205     return ret;
00206   }
00207 
00208   template<typename A, typename T>
00209   Element<A, T>
00210   realtime(const Element<A, T>& a, misc::direction_type type)
00211   {
00212     return do_realtime(a.structure(), a, type);
00213   }
00214 
00215 
00216 } // vcsn
00217 
00218 #endif // ! VCSN_ALGORITHMS_REALTIME_HXX

Generated on Wed Jun 13 17:00:28 2007 for Vaucanson by  doxygen 1.5.1