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 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       }
00131 
00132       virtual void
00133       one()
00134       {
00135         auto_ = new automaton_t(automata_set_t(series_));
00136         hstate_t new_i = auto_->add_state();
00137         hstate_t new_f = auto_->add_state();
00138         auto_->set_initial(new_i);
00139         auto_->set_final(new_f);
00140         auto_->add_spontaneous(new_i, new_f);
00141       }
00142 
00143       const automaton_t         &get_auto() const
00144       {
00145         return *auto_;
00146       }
00147 
00148     private :
00149       automaton_t               *auto_;
00150       const series_set_t        &series_;
00151   };
00152 
00153   template <typename A, typename auto_t,
00154             typename Letter, typename Weight>
00155   void
00156   do_thompson_of(const AutomataBase<A>&,
00157                  auto_t& output,
00158                  const rat::exp<Letter, Weight>& kexp)
00159   {
00160     ThompsonVisitor<auto_t, Letter, Weight> visitor(output.structure().series());
00161 
00162     // FIXME :
00163     // Static assert : Letter = monoid_elt_value_t,
00164     //                 Weight = semiring_elt_value_t
00165     kexp.accept(visitor);
00166     output = visitor.get_auto();
00167   }
00168 
00169   template<typename A,      typename T,
00170            typename Letter, typename Weight>
00171   void
00172   thompson_of(Element<A, T>& out,
00173               const rat::exp<Letter, Weight>& kexp)
00174   {
00175     do_thompson_of(out.structure(), out, kexp);
00176   }
00177 
00178   template <class AutoType, class S, class T>
00179   Element<Automata<S>, AutoType>
00180   thompson_of(const Element<S, T>& exp)
00181   {
00182     Automata<S>                         automata_set(exp.structure());
00183     Element<Automata<S>, AutoType>      automata(automata_set);
00184 
00185     thompson_of(automata, exp.value());
00186     return automata;
00187   }
00188 } // vcsn
00189 
00190 #endif // ! VCSN_ALGORITHMS_THOMPSON_HXX

Generated on Fri Jul 28 12:18:53 2006 for Vaucanson by  doxygen 1.4.6