initial_derivation.hxx

00001 // initial_derivation.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 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_INITIAL_DERIVATION_HXX
00018 # define VCSN_ALGORITHMS_INITIAL_DERIVATION_HXX
00019 
00020 # include <vaucanson/algebra/concept/series_base.hh>
00021 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00022 
00023 # include <list>
00024 
00025 namespace vcsn
00026 {
00027 
00035   template <class Series, class T, class Dispatch>
00036   struct KRatExpInitialDerivation : algebra::KRatExpMatcher<
00037     KRatExpInitialDerivation<Series, T, Dispatch>,
00038     T,
00039     std::list< Element<Series, T> >,
00040     Dispatch
00041     >
00042   {
00043     typedef KRatExpInitialDerivation<Series, T, Dispatch>       self_t;
00044     typedef Element<Series, T>                          exp_t;
00045     typedef std::list<exp_t>                            list_t;
00046     typedef std::list<exp_t>                            return_type;
00047     typedef typename list_t::iterator                   iterator_t;
00048     IMPORT_TYPEDEF_(exp_t,                              semiring_elt_t);
00049     IMPORT_TYPEDEF_(exp_t,                              monoid_elt_t);
00050     typedef typename semiring_elt_t::value_t            semiring_elt_value_t;
00051     INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
00052 
00053     KRatExpInitialDerivation(const exp_t& exp) :
00054       exp_(exp)
00055     {}
00056 
00057     // Useful functions:
00058   private:
00059     list_t apply_sum(list_t explist)
00060     {
00061       if (explist.size() != 1)
00062       {
00063         iterator_t      i = explist.begin();
00064         exp_t           res = *i;
00065         for (i++; i != explist.end(); ++i)
00066         {
00067           res += *i;
00068         }
00069         explist.clear();
00070         explist.push_back(res);
00071       }
00072       return explist;
00073     }
00074 
00075     list_t& put_in(list_t& s, exp_t e)
00076     {
00077       s.clear();
00078       s.push_back(e);
00079       return s;
00080     }
00081 
00082    public:
00083 
00084     // Matches:
00085     MATCH__(Product, lhs, rhs)
00086     {
00087       list_t llist = match(lhs);
00088       exp_t s (exp_.structure(), rhs);
00089       list_t res;
00090       for (typename list_t::const_iterator it = llist.begin();
00091            it != llist.end(); ++it)
00092         res.push_back(*it * s);
00093       return res;
00094     }
00095     END
00096 
00097     MATCH__(Sum, lhs, rhs)
00098     {
00099       list_t llist = match(lhs);
00100       list_t rlist = match(rhs);
00101       list_t res;
00102       merge(llist.begin(), llist.end(),
00103                 rlist.begin(), rlist.end(),
00104                 inserter(res, res.begin()));
00105       return res;
00106     }
00107     END
00108 
00109     MATCH_(Star, e)
00110     {
00111       list_t    res;
00112       exp_t s (exp_.structure(), e.star());
00113       res.push_back(s);
00114       return res;
00115     }
00116     END
00117 
00118     MATCH__(LeftWeight, w, e)
00119     {
00120       list_t    clist = apply_sum(match(e));
00121       put_in(clist, semiring_elt_t(w) * *clist.begin());
00122       return clist;
00123     }
00124     END
00125 
00126     MATCH__(RightWeight, e, w)
00127     {
00128       list_t    clist = apply_sum(match(e));
00129       put_in(clist, *clist.begin() * semiring_elt_t(w));
00130       return clist;
00131     }
00132     END
00133 
00134     MATCH_(Constant, m)
00135     {
00136       list_t    res;
00137       exp_t s (exp_.structure(), m);
00138       res.push_back(s);
00139       return res;
00140     }
00141     END
00142 
00143     MATCH(Zero)
00144     {
00145       list_t    res;
00146       res.push_back(exp_.structure().zero(SELECT(T)));
00147       return res;
00148     }
00149     END
00150 
00151     MATCH(One)
00152     {
00153       list_t    res;
00154       res.push_back(exp_.structure().identity(SELECT(T)));
00155       return res;
00156     }
00157     END
00158 
00159   private:
00160     exp_t exp_;
00161   };
00162 
00163 }
00164 
00165 #endif // ! VCSN_ALGORITHMS_INITIAL_DERIVATION_HXX

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