krat_exp_linearize.hxx

00001 // krat_exp_linearize.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_KRAT_EXP_LINEARIZE_HXX
00018 # define VCSN_ALGORITHMS_KRAT_EXP_LINEARIZE_HXX
00019 
00020 // LINEAR_INDEX_START must be != 0
00021 # define LINEAR_INDEX_START     1
00022 
00023 # include <vaucanson/algorithms/krat_exp_linearize.hh>
00024 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00025 
00026 namespace vcsn {
00027 
00028   // The Matcher building the linearized expression
00029   template <class Series, class T, class Dispatch>
00030   struct KRatExpLinearize : algebra::KRatExpMatcher<
00031     KRatExpLinearize<Series, T, Dispatch>,
00032     T,
00033     typename linearize_element<Series, T>::element_t,
00034     Dispatch
00035     >
00036   {
00037     // Types of the resulting expression
00038     typedef typename linearize_element<Series, T>::index_t      index_t;
00039     typedef typename linearize_element<Series, T>::element_t    return_type;
00040     typedef typename return_type::value_t               exp_impl_t;
00041     typedef typename return_type::monoid_elt_value_t    l_monoid_elt_value_t;
00042     typedef typename return_type::set_t                 l_series_set_elt_t;
00043     typedef typename l_series_set_elt_t::monoid_t       l_monoid_t;
00044     typedef typename l_series_set_elt_t::semiring_t     l_semiring_t;
00045     typedef typename l_monoid_t::alphabet_t             l_alphabet_t;
00046     typedef typename l_monoid_t::letter_t               l_letter_t;
00047     typedef typename return_type::monoid_elt_t          l_monoid_elt_t;
00048     typedef typename return_type::semiring_elt_t        l_semiring_elt_t;
00049     // Types of the source expression
00050     typedef KRatExpLinearize<Series, T, Dispatch>       self_t;
00051     typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
00052     typedef typename Element<Series, T>::monoid_elt_t   monoid_elt_t;
00053     typedef typename monoid_elt_t::value_t              monoid_elt_value_t;
00054     INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
00055 
00056     KRatExpLinearize(const Element<Series, T>& exp) :
00057       index_(LINEAR_INDEX_START),
00058       exp_(exp),
00059       l_alpha_(),
00060       l_series_(l_semiring_t (), l_monoid_t (l_alpha_))
00061     {
00062     }
00063 
00064     return_type linearize()
00065     {
00066       // Build a Element with the correct alphabet.
00067       return_type       result = match(exp_.value());
00068       l_monoid_t        l_monoid(l_alpha_);
00069       l_semiring_t      l_semiring;
00070       return return_type (l_series_set_elt_t (l_semiring, l_monoid),
00071                           result.value());
00072     }
00073 
00074     MATCH__(Product, lhs, rhs)
00075     {
00076       return match(lhs) * match(rhs);
00077     }
00078     END
00079 
00080     MATCH__(Sum, lhs, rhs)
00081     {
00082       return match(lhs) + match(rhs);
00083     }
00084     END
00085 
00086     MATCH_(Star, e)
00087     {
00088       return match(e).star();
00089     }
00090     END
00091 
00092     MATCH__(LeftWeight, w, e)
00093     {
00094       return l_semiring_elt_t(w) * match(e);
00095     }
00096     END
00097 
00098     MATCH__(RightWeight, e, w)
00099     {
00100       return match(e) * l_semiring_elt_t(w);
00101     }
00102     END
00103 
00104     MATCH_(Constant, m)
00105     {
00106       // Build new constant and update alphabet
00107       l_monoid_elt_value_t      res;
00108       typedef typename monoid_elt_value_t::const_iterator       const_iterator;
00109       for (const_iterator i = m.begin(); i != m.end(); ++i)
00110       {
00111         l_alpha_.insert(l_letter_t(*i, index_));
00112         res.push_back(l_letter_t(*i, index_));
00113         index_++;
00114       }
00115       // Transform it in the good type
00116       return return_type(l_series_, res);
00117     }
00118     END
00119 
00120     MATCH(Zero)
00121     {
00122       return l_series_.zero(SELECT(exp_impl_t));
00123     }
00124     END
00125 
00126     MATCH(One)
00127     {
00128       return l_series_.identity(SELECT(exp_impl_t));
00129     }
00130     END
00131 
00132   private:
00133     index_t             index_;
00134     Element<Series, T>  exp_;
00135     l_alphabet_t        l_alpha_;
00136     l_series_set_elt_t          l_series_;
00137   };
00138 
00139   template <class Series, class T>
00140   typename linearize_element<Series, T>::element_t
00141   linearize(const Element<Series, T>& exp)
00142   {
00143     KRatExpLinearize<Series, T, algebra::DispatchFunction<T> >
00144       matcher(exp);
00145     return matcher.linearize();
00146   }
00147 
00148 } // vcsn
00149 
00150 #endif // ! VCSN_ALGORITHMS_KRAT_EXP_LINEARIZE_HXX

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