krat_exp_support.hxx

00001 // krat_exp_support.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_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_SUPPORT_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_SUPPORT_HXX
00019 
00020 # include <utility>
00021 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00022 # include <vaucanson/algebra/implementation/series/krat_exp_is_finite_app.hxx>
00023 
00024 namespace vcsn {
00025 
00026   template <class Series, class T, class Dispatch>
00027   class SupportMatcher : public algebra::KRatExpMatcher<
00028     SupportMatcher<Series, T, Dispatch>,
00029     T,
00030     int,
00031     Dispatch
00032     >
00033   {
00034     public:
00035       typedef IsFiniteAppMatcher<Series, T, Dispatch>   self_t;
00036       typedef int                                       return_type;
00037       typedef Series                                    series_set_t;
00038       typedef Element<Series, T>                        series_set_elt_t;
00039       typedef typename series_set_elt_t::monoid_elt_t   monoid_elt_t;
00040       typedef typename monoid_elt_t::value_t            monoid_elt_value_t;
00041       typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00042       typedef typename semiring_elt_t::value_t          semiring_elt_value_t;
00043       typedef std::list<monoid_elt_value_t>             support_t;
00044       typedef std::list<std::pair<semiring_elt_value_t, monoid_elt_value_t> >
00045       ext_support_t;
00046       INHERIT_CONSTRUCTORS(self_t, T, return_type, Dispatch);
00047 
00048       SupportMatcher(const series_set_t& s):
00049         series_(s)
00050       {}
00051 
00052       MATCH__(Product, lhs, rhs)
00053       {
00054         ext_support_t old_supp_ = supp_;
00055         supp_.clear();
00056         match(lhs);
00057         ext_support_t lhs_s = supp_;
00058         supp_.clear();
00059         match(rhs);
00060         ext_support_t ret;
00061         for_all_const_(ext_support_t, c, lhs_s)
00062           for_all_const_(ext_support_t, d, supp_)
00063         {
00064           monoid_elt_t mc(series_.monoid(), c->second);
00065           monoid_elt_t md(series_.monoid(), d->second);
00066           semiring_elt_t wc(series_.semiring(), c->first);
00067           semiring_elt_t wd(series_.semiring(), d->first);
00068           ret.push_back(std::make_pair((wc * wd).value(),
00069                                        (mc * md).value()));
00070         }
00071         supp_ = ret;
00072         supp_.insert(supp_.begin(), old_supp_.begin(), old_supp_.end());
00073         return 0;
00074       }
00075       END
00076 
00077       MATCH__(Sum, lhs, rhs)
00078       {
00079         match(lhs);
00080         match(rhs);
00081         return 0;
00082       }
00083       END
00084 
00085       MATCH_(Star, node)
00086       {
00087         result_not_computable("undefined case (star) in krat_exp_support");
00088         return 0;
00089       }
00090       END
00091 
00092       MATCH__(LeftWeight, w, node)
00093       {
00094         ext_support_t old_supp_ = supp_;
00095         supp_.clear();
00096         match(node);
00097         for_all_(ext_support_t, c, supp_)
00098           c->first = op_mul(series_.semiring(), w, c->first);
00099         supp_.insert(supp_.begin(), old_supp_.begin(), old_supp_.end());
00100         return 0;
00101       }
00102       END
00103 
00104       MATCH__(RightWeight, node, w)
00105       {
00106         ext_support_t old_supp_ = supp_;
00107         supp_.clear();
00108         match(node);
00109         for_all_(ext_support_t, c, supp_)
00110           c->first = op_mul(series_.semiring(), c->first, w);
00111         supp_.insert(supp_.begin(), old_supp_.begin(), old_supp_.end());
00112         return 0;
00113       }
00114       END
00115 
00116       MATCH_(Constant, m)
00117       {
00118         supp_.push_back(std::make_pair
00119                         (identity_value(series_.semiring(),
00120                                         SELECT(semiring_elt_value_t)),
00121                          m));
00122         return 0;
00123       }
00124       END
00125 
00126       MATCH(Zero)
00127       {
00128         return 0;
00129       }
00130       END
00131 
00132       MATCH(One)
00133       {
00134         supp_.push_back(std::make_pair
00135                         (identity_value(series_.semiring(),
00136                                         SELECT(semiring_elt_value_t)),
00137                          identity_value(series_.monoid(),
00138                                         SELECT(monoid_elt_value_t))));
00139         return 0;
00140       }
00141       END
00142 
00143       support_t get()
00144       {
00145         support_t ret;
00146         ext_support_t s = ext_get();
00147         for_all_const_(ext_support_t, c, s)
00148           ret.push_back(c->second);
00149         return ret;
00150       }
00151 
00152       ext_support_t& ext_get()
00153       {
00154         // Now join same words.
00155         typedef std::map<monoid_elt_value_t, semiring_elt_value_t> tmap_t;
00156         tmap_t v;
00157         typename tmap_t::iterator f;
00158         for_all_const_(ext_support_t, c, supp_)
00159         {
00160           if ((f = v.find(c->second)) == v.end())
00161             v[c->second] = c->first;
00162           else
00163             v[c->second] = op_add(series_.semiring(), v[c->second], c->first);
00164         }
00165         supp_.clear();
00166         for_all_const_(tmap_t, m, v)
00167           supp_.push_back(std::make_pair(m->second, m->first));
00168         return supp_;
00169       }
00170 
00171     private:
00172       ext_support_t             supp_;
00173       const series_set_t&       series_;
00174   };
00175 
00176 } // vcsn
00177 
00178 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_SUPPORT_HXX

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