thompson.hxx

00001 // thompson.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, 2007 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_THOMPSON_HXX
00018 # define VCSN_ALGORITHMS_THOMPSON_HXX
00019 
00020 # include <vaucanson/algorithms/thompson.hh>
00021 
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/algorithms/normalized.hh>
00024 
00025 namespace vcsn {
00026 
00027   /*----------------.
00028   | ThompsonVisitor |
00029   `----------------*/
00030   // FIXME : Non optimal version.
00031   //         There are too much construction of automaton.
00032 
00033   // FIXME : from now, it is only working over LetterAutomaton
00034 
00035   template <class Auto_, class Monoid_, class Semiring_>
00036   class ThompsonVisitor :
00037       public rat::ConstNodeVisitor<Monoid_, Semiring_>
00038   {
00039     public :
00040       typedef Auto_                                     automaton_t;
00041       typedef typename automaton_t::set_t                       automata_set_t;
00042       typedef typename automaton_t::series_set_t                series_set_t;
00043       typedef typename automaton_t::series_set_elt_t    series_set_elt_t;
00044       typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00045       typedef Monoid_                                   monoid_elt_value_t;
00046       typedef Semiring_                                 semiring_elt_value_t;
00047       typedef rat::Node<monoid_elt_value_t, semiring_elt_value_t> node_t;
00048 
00049     public :
00050 
00051       ThompsonVisitor(const series_set_t& s) : series_(s)
00052       {}
00053 
00054       virtual
00055       ~ThompsonVisitor()
00056       {}
00057 
00058       virtual void
00059       product(const node_t* lhs, const node_t* rhs)
00060       {
00061         automaton_t     *tmp_;
00062         rhs->accept(*this);
00063         tmp_ = auto_;
00064         lhs->accept(*this);
00065         concatenate_of_normalized_here(*auto_, *tmp_);
00066         delete(tmp_);
00067       }
00068 
00069       virtual void
00070       sum(const node_t* lhs, const node_t* rhs)
00071       {
00072         automaton_t     *tmp_;
00073         lhs->accept(*this);
00074         tmp_ = auto_;
00075         rhs->accept(*this);
00076         union_of_normalized_here(*auto_, *tmp_);
00077       }
00078 
00079       virtual void
00080       star(const node_t* node)
00081       {
00082         node->accept(*this);
00083         star_of_normalized_here(*auto_);
00084       }
00085 
00086       virtual void
00087       left_weight(const semiring_elt_value_t& w, const node_t* node)
00088       {
00089         node->accept(*this);
00090 
00091         for (typename automaton_t::initial_iterator i = auto_->initial().begin();
00092              i != auto_->initial().end();
00093              ++i)
00094           auto_->set_initial(*i, semiring_elt_t(w) * auto_->get_initial(*i));
00095       }
00096 
00097       virtual void
00098       right_weight(const semiring_elt_value_t& w, const node_t* node)
00099       {
00100         node->accept(*this);
00101 
00102         for (typename automaton_t::initial_iterator i = auto_->initial().begin();
00103              i != auto_->initial().end();
00104              ++i)
00105           auto_->set_initial(*i, auto_->get_initial(*i) * semiring_elt_t(w));
00106       }
00107 
00108       virtual void
00109       constant(const monoid_elt_value_t& m)
00110       {
00111         auto_ = new automaton_t(automata_set_t(series_));
00112         hstate_t new_i = auto_->add_state();
00113         hstate_t last = new_i;
00114         hstate_t new_f;
00115         for (typename monoid_elt_value_t::const_iterator i = m.begin();
00116              i != m.end(); ++i)
00117         {
00118           new_f = auto_->add_state();
00119           auto_->add_letter_transition(last, new_f, *i);
00120           last = new_f;
00121         }
00122         auto_->set_initial(new_i);
00123         auto_->set_final(new_f);
00124       }
00125 
00126       virtual void
00127       zero()
00128       {
00129         auto_ = new automaton_t(automata_set_t(series_));
00130         auto_->set_initial(auto_->add_state());
00131         auto_->set_final(auto_->add_state());
00132       }
00133 
00134       virtual void
00135       one()
00136       {
00137         auto_ = new automaton_t(automata_set_t(series_));
00138         hstate_t new_i = auto_->add_state();
00139         hstate_t new_f = auto_->add_state();
00140         auto_->set_initial(new_i);
00141         auto_->set_final(new_f);
00142         auto_->add_spontaneous(new_i, new_f);
00143       }
00144 
00145       const automaton_t         &get_auto() const
00146       {
00147         return *auto_;
00148       }
00149 
00150     private :
00151       automaton_t               *auto_;
00152       const series_set_t        &series_;
00153   };
00154 
00155   template <typename A, typename auto_t,
00156             typename Letter, typename Weight>
00157   void
00158   do_thompson_of(const AutomataBase<A>&,
00159                  auto_t& output,
00160                  const rat::exp<Letter, Weight>& kexp)
00161   {
00162     ThompsonVisitor<auto_t, Letter, Weight> visitor(output.structure().series());
00163 
00164     // FIXME :
00165     // Static assert : Letter = monoid_elt_value_t,
00166     //                 Weight = semiring_elt_value_t
00167     kexp.accept(visitor);
00168     output = visitor.get_auto();
00169   }
00170 
00171   template<typename A,      typename T,
00172            typename Letter, typename Weight>
00173   void
00174   thompson_of(Element<A, T>& out,
00175               const rat::exp<Letter, Weight>& kexp)
00176   {
00177     do_thompson_of(out.structure(), out, kexp);
00178   }
00179 
00180   template <class AutoType, class S, class T>
00181   Element<Automata<S>, AutoType>
00182   thompson_of(const Element<S, T>& exp)
00183   {
00184     Automata<S>                         automata_set(exp.structure());
00185     Element<Automata<S>, AutoType>      automata(automata_set);
00186 
00187     thompson_of(automata, exp.value());
00188     return automata;
00189   }
00190 } // vcsn
00191 
00192 #endif // ! VCSN_ALGORITHMS_THOMPSON_HXX

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