aci_canonical.hxx

00001 // aci_canonical.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_ACI_CANONICAL_HXX
00018 # define VCSN_ALGORITHMS_ACI_CANONICAL_HXX
00019 
00020 # include <vaucanson/algorithms/aci_canonical.hh>
00021 
00022 # include <vaucanson/algebra/concept/series_base.hh>
00023 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00024 
00025 # include <set>
00026 
00027 namespace vcsn
00028 {
00029 
00038   template <class Series, class T, class Dispatch>
00039   struct KRatExpAciCanonical : algebra::KRatExpMatcher<
00040     KRatExpAciCanonical<Series, T, Dispatch>,
00041     T,
00042     std::set< Element<Series, T> >,
00043     Dispatch
00044     >
00045   {
00046     typedef Element<Series, T>                          exp_t;
00047     typedef std::set<exp_t>                             set_t;
00048     typedef std::set<exp_t>                             return_type;
00049     typedef typename set_t::iterator                    iterator_t;
00050     typedef KRatExpAciCanonical<Series, T, Dispatch>    self_t;
00051     typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
00052     typedef typename semiring_elt_t::value_t            semiring_elt_value_t;
00053     typedef typename Element<Series, T>::monoid_elt_t   monoid_elt_t;
00054     typedef typename monoid_elt_t::set_t                monoid_t;
00055     typedef typename monoid_t::alphabet_t               alphabet_t;
00056     typedef typename alphabet_t::letter_t               letter_t;
00057     INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
00058 
00059     KRatExpAciCanonical(const Element<Series, T>& exp) :
00060       exp_(exp)
00061     {}
00062 
00063     // Useful functions:
00064   private:
00065     set_t apply_sum(set_t expset)
00066     {
00067       if (expset.size() != 1)
00068       {
00069         iterator_t      i = expset.begin();
00070         exp_t           res = *i;
00071         for (i++; i != expset.end(); ++i)
00072         {
00073           res += *i;
00074         }
00075         expset.clear();
00076         expset.insert(res);
00077       }
00078       return expset;
00079     }
00080 
00081     set_t& put_in(set_t& s, exp_t e)
00082     {
00083       s.clear();
00084       s.insert(e);
00085       return s;
00086     }
00087 
00088   public:
00089     exp_t set2exp(set_t expset)
00090     {
00091       expset = apply_sum(expset);
00092       return *expset.begin();
00093     }
00094 
00095     // Matches:
00096     MATCH__(Product, lhs, rhs)
00097     {
00098       set_t lset = apply_sum(match(lhs));
00099       set_t rset = apply_sum(match(rhs));
00100       put_in(lset, *lset.begin() * *rset.begin());
00101       return lset;
00102     }
00103     END
00104 
00105     MATCH__(Sum, lhs, rhs)
00106     {
00107       set_t lset = match(lhs);
00108       set_t rset = match(rhs);
00109       set_t res;
00110       merge(lset.begin(), lset.end(),
00111                 rset.begin(), rset.end(),
00112                 inserter(res, res.begin()));
00113       return res;
00114     }
00115     END
00116 
00117     MATCH_(Star, e)
00118     {
00119       set_t cset = apply_sum(match(e));
00120       exp_t exp = *cset.begin();
00121       put_in(cset, exp.star());
00122       return cset;
00123     }
00124     END
00125 
00126     MATCH__(LeftWeight, w, e)
00127     {
00128       set_t     cset = apply_sum(match(e));
00129       put_in(cset, semiring_elt_t(w) * *cset.begin());
00130       return cset;
00131     }
00132     END
00133 
00134     MATCH__(RightWeight, e, w)
00135     {
00136       set_t     cset = apply_sum(match(e));
00137       put_in(cset, *cset.begin() * semiring_elt_t(w));
00138       return cset;
00139     }
00140     END
00141 
00142     MATCH_(Constant, m)
00143     {
00144       set_t     res;
00145       Element<Series, T> s (exp_.structure(), m);
00146       res.insert(s);
00147       return res;
00148     }
00149     END
00150 
00151     MATCH(Zero)
00152     {
00153       set_t     res;
00154       res.insert(exp_.structure().zero(SELECT(T)));
00155       return res;
00156     }
00157     END
00158 
00159     MATCH(One)
00160     {
00161       set_t     res;
00162       res.insert(exp_.structure().identity(SELECT(T)));
00163       return res;
00164     }
00165     END
00166 
00167   private:
00168     Element<Series, T>  exp_;
00169   };
00170 
00171   template <class Series_, class Exp_>
00172   Exp_
00173   do_canonical(const algebra::SeriesBase<Series_>&, const Exp_& exp)
00174   {
00175     typedef Series_                     S;
00176     typedef typename Exp_::value_t      T;
00177 
00178     KRatExpAciCanonical< S, T, algebra::DispatchFunction<T> >   matcher(exp);
00179     return matcher.set2exp(matcher.match(exp.value()));
00180   }
00181 
00182   template <class Series, class T>
00183   Element<Series, T>
00184   canonical(const Element<Series, T>& exp)
00185   {
00186     return do_canonical(exp.structure(), exp);
00187   }
00188 
00189 }
00190 
00191 #endif // ! VCSN_ALGORITHMS_ACI_CANONICAL_HXX

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