standard_of.hxx

00001 // standard_of.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_STANDARD_OF_HXX
00018 # define VCSN_ALGORITHMS_STANDARD_OF_HXX
00019 
00020 # include <vaucanson/algorithms/standard_of.hh>
00021 
00022 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00023 # include <vaucanson/algorithms/standard.hh>
00024 
00025 namespace vcsn {
00026 
00027   namespace algebra {
00028 
00029     /*-------------------.
00030     | Standard_OfVisitor |
00031     `-------------------*/
00032     template <class Exp_,
00033               class Auto_,
00034               class Dispatch_>
00035     class Standard_OfVisitor :
00036         public algebra::KRatExpMatcher<
00037       Standard_OfVisitor<Exp_, Auto_, Dispatch_>,
00038       Exp_,
00039       Auto_*,
00040       Dispatch_
00041       >
00042     {
00043       public :
00044         typedef Auto_*                                  automaton_ptr_t;
00045         typedef Auto_                                   automaton_t;
00046         typedef typename automaton_t::set_t             automata_set_t;
00047 
00048         typedef typename automaton_t::series_set_t      series_set_t;
00049         typedef typename automaton_t::monoid_t          monoid_t;
00050         typedef typename automaton_t::semiring_t        semiring_t;
00051 
00052         typedef typename automaton_t::series_set_elt_t  series_set_elt_t;
00053         typedef typename automaton_t::monoid_elt_t      monoid_elt_t;
00054         typedef typename automaton_t::semiring_elt_t    semiring_elt_t;
00055 
00056         typedef typename Exp_::monoid_elt_value_t       monoid_elt_value_t;
00057         typedef typename Exp_::semiring_elt_value_t     semiring_elt_value_t;
00058 
00059         typedef Standard_OfVisitor<Exp_, Auto_, Dispatch_>      this_class;
00060         typedef algebra::KRatExpMatcher<this_class, Exp_, Auto_*, Dispatch_>
00061         parent_class;
00062         typedef typename parent_class::return_type      return_type;
00063 
00064       public :
00065 
00066         Standard_OfVisitor(const series_set_t& series) :
00067           automata_set_(series)
00068         {}
00069 
00070         INHERIT_CONSTRUCTORS(this_class, Exp_, Auto_*, Dispatch_);
00071 
00072         MATCH__(Product, lhs, rhs)
00073         {
00074           automaton_ptr_t tmp_  = match(rhs);
00075           automaton_ptr_t auto_ = match(lhs);
00076           concat_of_standard_here(*auto_, *tmp_);
00077           delete (tmp_);
00078           return auto_;
00079         }
00080         END
00081 
00082         MATCH__(Sum, lhs, rhs)
00083         {
00084           automaton_ptr_t tmp_  = match(rhs);
00085           automaton_ptr_t auto_ = match(lhs);
00086           union_of_standard_here(*auto_, *tmp_);
00087           delete (tmp_);
00088           return auto_;
00089         }
00090         END
00091 
00092         MATCH_(Star, node)
00093         {
00094           automaton_ptr_t stared = match(node);
00095           star_of_standard_here(*stared);
00096           return stared;
00097         }
00098         END
00099 
00100         MATCH__(LeftWeight, w, node)
00101         {
00102           const semiring_t&     semiring = automata_set_.series().semiring();
00103           const semiring_elt_t  weight (semiring, w);
00104           automaton_ptr_t       auto_ = match(node);
00105 
00106           for (typename automaton_t::initial_iterator i = auto_->initial().begin();
00107                i != auto_->initial().end();
00108                ++i)
00109           {
00110             std::list<htransition_t>    e;
00111             auto_->deltac(e, *i, delta_kind::transitions());
00112             for (typename std::list<htransition_t>::const_iterator j = e.begin();
00113                  j != e.end();
00114                  ++j)
00115             {
00116               // FIXME: The following code is only correct when labels are
00117               // FIXME: series. We should add meta code to make the code
00118               // FIXME: fail at runtime when this function is called
00119               // FIXME: with label as letters. However, we cannot afford
00120               // FIXME: doing an error at compile time, because the rest
00121               // FIXME: of this matcher is valid on Boolean automata with
00122               // FIXME: label as letter.
00123               typedef typename automaton_t::label_t     label_t;
00124               typedef Element<series_set_t, label_t>    label_elt_t;
00125 
00126               label_elt_t label (automata_set_.series(), auto_->label_of(*j));
00127               label  = weight * label;
00128 
00129               hstate_t                          aim = auto_->dst_of(*j);
00130               auto_->del_transition(*j);
00131 
00132               if (label != zero_as<label_t>::of(automata_set_.series()))
00133                 auto_->add_transition(*i, aim, label.value());
00134             }
00135             auto_->set_final(*i, weight * auto_->get_final(*i));
00136           }
00137           return auto_;
00138         }
00139         END
00140 
00141         MATCH__(RightWeight, node, w)
00142         {
00143           const semiring_t&     semiring = automata_set_.series().semiring();
00144           const semiring_elt_t  weight (semiring, w);
00145           automaton_ptr_t       auto_ = match(node);
00146 
00147           for (typename automaton_t::final_iterator i = auto_->final().begin();
00148                i != auto_->final().end();
00149                ++i)
00150             auto_->set_final(*i, auto_->get_final(*i) * weight);
00151           return auto_;
00152         }
00153         END
00154 
00155         MATCH_(Constant, m)
00156         {
00157           automaton_ptr_t auto_ = new automaton_t(automata_set_);
00158           hstate_t new_i = auto_->add_state();
00159           hstate_t last = new_i;
00160           hstate_t new_f;
00161           for (typename monoid_elt_value_t::const_iterator i = m.begin();
00162                i != m.end(); ++i)
00163           {
00164             new_f = auto_->add_state();
00165             auto_->add_letter_transition(last, new_f, *i);
00166             last = new_f;
00167           }
00168           auto_->set_initial(new_i);
00169           auto_->set_final(new_f);
00170           return auto_;
00171         }
00172         END
00173 
00174         MATCH(Zero)
00175         {
00176           automaton_ptr_t auto_ = new automaton_t(automata_set_);
00177           return auto_;
00178         }
00179         END
00180 
00181         MATCH(One)
00182         {
00183           automaton_ptr_t auto_ = new automaton_t(automata_set_);
00184           hstate_t new_i = auto_->add_state();
00185           auto_->set_initial(new_i);
00186           auto_->set_final(new_i);
00187           return auto_;
00188         }
00189       END
00190 
00191       private:
00192         automata_set_t automata_set_;
00193     };
00194 
00195   }
00196 
00197   template <typename A,
00198             typename Output,
00199             typename Exp>
00200   void
00201   do_standard_of(const AutomataBase<A>&,
00202                  Output& output,
00203                  const Exp& kexp)
00204   {
00205     algebra::Standard_OfVisitor<Exp, Output, algebra::DispatchFunction<Exp> >
00206       m(output.structure().series());
00207     output = *m.match(kexp);
00208   }
00209 
00210   template<typename A,
00211            typename T,
00212            typename Exp>
00213   void
00214   standard_of(Element<A, T>& out,
00215               const Exp& kexp)
00216   {
00217     do_standard_of(out.structure(), out, kexp);
00218   }
00219 
00220   template <typename A, typename T, typename Exp>
00221   Element<A, T>
00222   standard_of(const Exp& e)
00223   {
00224     A automata_structure(e.structure());
00225     Element<A, T> out(automata_structure);
00226     standard_of(out, e);
00227     return out;
00228   }
00229 
00230 } // vcsn
00231 
00232 #endif // ! VCSN_ALGORITHMS_STANDARD_OF_HXX

Generated on Sat Jul 29 17:13:11 2006 for Vaucanson by  doxygen 1.4.6