forward_realtime.hxx

00001 // forward_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, 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_FORWARD_REALTIME_HXX
00018 # define VCSN_ALGORITHMS_FORWARD_REALTIME_HXX
00019 
00020 # include <vaucanson/algorithms/backward_realtime.hh>
00021 # include <vaucanson/algorithms/forward_realtime.hh>
00022 
00023 # include <vaucanson/automata/concept/automata_base.hh>
00024 # include <vaucanson/algorithms/eps_removal.hh>
00025 # include <vaucanson/algorithms/accessible.hh>
00026 
00027 # include <deque>
00028 # include <set>
00029 
00030 namespace vcsn {
00031 
00032   template <class A_, typename Auto_>
00033   void
00034   do_forward_realtime_here(const AutomataBase<A_>&,
00035                            Auto_& a)
00036   {
00037     typedef Auto_                               automaton_t;
00038     AUTOMATON_TYPES(automaton_t);
00039     typedef std::set<htransition_t>                     delta_ret_t;
00040     typedef std::deque<htransition_t>                   queue_t;
00041 
00042     queue_t               to_del, origin_d;
00043     delta_ret_t           aim_d;
00044     monoid_elt_t          monoid_identity =
00045       algebra::identity_as<monoid_elt_value_t>::
00046       of(a.structure().series().monoid());
00047     semiring_elt_t                semiring_zero =
00048       algebra::zero_as<semiring_elt_value_t>::
00049       of(a.structure().series().semiring());
00050     series_set_elt_t          series_identity =
00051       algebra::identity_as<series_set_elt_value_t>::of(a.structure().series());
00052 
00053     forward_eps_removal_here(a);
00054 
00055     for_all_states(origin, a)
00056     {
00057       std::insert_iterator<queue_t> origin_i(origin_d, origin_d.begin());
00058       a.delta(origin_i, *origin, delta_kind::transitions());
00059 
00060       while (!origin_d.empty())
00061       {
00062         htransition_t d_o = origin_d.front();
00063         origin_d.pop_front();
00064         if (a.series_of(d_o).get(monoid_identity) != semiring_zero)
00065         {
00066           aim_d.clear();
00067           a.deltac(aim_d, a.dst_of(d_o), delta_kind::transitions());
00068           for (typename delta_ret_t::const_iterator d = aim_d.begin();
00069                d != aim_d.end();
00070                ++d)
00071             if (a.series_of(*d).get(monoid_identity) == semiring_zero)
00072             {
00073               bool new_transition = true;
00074               for (typename queue_t::const_iterator d__o =
00075                      origin_d.begin();
00076                    d__o != origin_d.end();
00077                    ++d__o)
00078                 if ((a.dst_of(*d__o) == a.dst_of(*d) &&
00079                      (a.label_of(*d__o) == a.label_of(*d))))
00080                 {
00081                   new_transition = false;
00082                   break;
00083                 }
00084 
00085               if (new_transition)
00086               {
00087                 htransition_t new_htransition = a.add_series_transition
00088                   (*origin,
00089                    a.dst_of(*d),
00090                    a.series_of(d_o) * a.series_of(*d));
00091                 origin_d.push_back(new_htransition);
00092               }
00093             }
00094           if (a.is_final(a.dst_of(d_o)))
00095             a.set_final(*origin);
00096         }
00097       }
00098     }
00099 
00100     for (typename automaton_t::transition_iterator e = a.transitions().begin();
00101          e != a.transitions().end();
00102          ++e)
00103       if (a.series_of(*e).get(monoid_identity) != semiring_zero)
00104         to_del.push_back(*e);
00105 
00106     while (!to_del.empty())
00107     {
00108       htransition_t e = to_del.front();
00109       to_del.pop_front();
00110       a.del_transition(e);
00111     }
00112 
00113     coaccessible_here(a);
00114 
00115     realtime_words_here(a);
00116   }
00117 
00118   template<typename A, typename T>
00119   void
00120   forward_realtime_here(Element<A, T>& a)
00121   {
00122     do_forward_realtime_here(a.structure(), a);
00123   }
00124 
00125   template<typename A_, typename Auto_>
00126   Auto_
00127   do_forward_realtime(const AutomataBase<A_>&, const Auto_& a)
00128   {
00129     Auto_ ret(a);
00130     do_forward_realtime_here(ret.structure(), ret);
00131     return ret;
00132   }
00133 
00134 
00135   template<typename A, typename T>
00136   Element<A, T>
00137   forward_realtime(const Element<A, T>& a)
00138   {
00139     return do_forward_realtime(a.structure(), a);
00140   }
00141 
00142 } // vcsn
00143 
00144 #endif // ! VCSN_ALGORITHMS_FORWARD_REALTIME_HXX

Generated on Sat Jul 29 17:12:59 2006 for Vaucanson by  doxygen 1.4.6