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

Generated on Sun Jul 29 19:35:29 2007 for Vaucanson by  doxygen 1.5.2