derived_term_automaton.hxx

00001 // derived_term_automaton.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_DERIVED_TERM_AUTOMATON_HXX
00018 # define VCSN_ALGORITHMS_DERIVED_TERM_AUTOMATON_HXX
00019 
00020 # include <vaucanson/algorithms/derived_term_automaton.hh>
00021 
00022 # include <vaucanson/algorithms/internal/build_pattern.hh>
00023 # include <vaucanson/algorithms/internal/partial_rat_exp.hh>
00024 # include <vaucanson/algorithms/internal/partial_rat_exp_constant_term.hh>
00025 # include <vaucanson/algorithms/internal/partial_rat_exp_derivation.hh>
00026 
00027 # include <vaucanson/algorithms/krat_exp_realtime.hh>
00028 # include <vaucanson/misc/usual_macros.hh>
00029 # include <vaucanson/algorithms/initial_derivation.hh>
00030 
00031 # ifdef DEBUG
00032 
00033 namespace std
00034 {
00035   template <typename T>
00036   std::ostream& operator << (std::ostream& o, const std::list<T>& l)
00037   {
00038     typename std::list<T>::const_iterator       i = l.begin();
00039 
00040     o << '{';
00041     if (i != l.end())
00042     {
00043       o << *i;
00044       for (i++; i != l.end(); ++i)
00045         o << ", " << *i;
00046     }
00047     return o << '}';
00048   }
00049 }
00050 
00051 #  define DERIVATES_TRACE_DEBUG(undef, e, l, s)         \
00052      if (!undef)                                        \
00053      {                                                  \
00054        std::cout << "Deriv "                            \
00055                  << e                                   \
00056                  << " by "                              \
00057                  << l                                   \
00058                  << " ="                                \
00059                  << std::endl;                          \
00060        std::cout << s << std::endl;                     \
00061        std::cout << std::endl;                          \
00062      }
00063 
00064 # else
00065 
00066 #  define DERIVATES_TRACE_DEBUG(undef, e, l, s)
00067 
00068 # endif
00069 
00070 namespace vcsn {
00071 
00072   using namespace algorithm_patterns;
00073 
00074   // In order to avoid re-calculation, the algorithm building
00075   // derivatives automaton is implemented in a incremental way
00076   template <typename T_auto, typename S, typename T>
00077   struct DerivativesAlgo : public IncAutomataConstructor <
00078     DerivativesAlgo<T_auto, S, T>,
00079     T_auto,
00080     PartialExp<S, T> >
00081   {
00082     typedef PartialExp<S, T>                            exp_t;
00083     typedef std::list<exp_t>                            exp_list_t;
00084     typedef typename exp_list_t::iterator               exp_list_iterator;
00085     AUTOMATON_TYPES(T_auto);
00086     AUTOMATON_FREEMONOID_TYPES(T_auto);
00087 
00088     // Contructor -> initialize mother class and undefined attributes,
00089     // which indicate if the resulting automaton is valid
00090     DerivativesAlgo(const series_set_t& series, const Element<S, T>& exp):
00091       IncAutomataConstructor<DerivativesAlgo, T_auto, PartialExp<S, T> >
00092         (series, prat_exp_convert(exp)),
00093       undefined(false)
00094     {}
00095 
00096     // List Contructor -> initialize mother class and undefined attributes,
00097     // which indicate if the resulting automaton is valid.
00098     // This is used for the broken_derived_term_automaton algorithm.
00099     DerivativesAlgo(const series_set_t& series,
00100                     const std::list<Element<S, T> >& listexp):
00101       IncAutomataConstructor<DerivativesAlgo, T_auto, PartialExp<S, T> >
00102         (series, prat_exp_convert(listexp)),
00103        undefined(false)
00104      {}
00105 
00106     // Function applied on each state
00107     void on_state(const PartialExp<S, T>& e)
00108     {
00109       alphabet_t alpha = this->get()->series().monoid().alphabet();
00110 
00111       // Test the constant term of current expression
00112       // If it is not zero, it is a final state
00113       std::pair<semiring_elt_t, bool>   c_term = constant_term(e);
00114       if (!c_term.second)
00115         undefined = true;
00116       if (c_term.first !=
00117           e.exp_structure().semiring().zero(SELECT(semiring_elt_value_t)))
00118         set_final(series_set_elt_t (e.exp_structure(), c_term.first));
00119 
00120       // Create links between current state and states corresponding to
00121       // partial derivatives of current expression
00122       for (alphabet_iterator a = alpha.begin(); a != alpha.end(); ++a)
00123       {
00124         std::pair<std::list<PartialExp<S, T> >, bool>
00125           s = prat_exp_derivate(e, *a);
00126         if (!s.second)
00127           undefined = true;
00128         DERIVATES_TRACE_DEBUG(undefined, e, *a, s.first);
00129         for (exp_list_iterator i = s.first.begin(); i != s.first.end(); ++i)
00130         {
00131           PartialExp<S, T> p_exp = *i;
00132           series_set_elt_t s_elt (e.exp_structure(),
00133                               monoid_elt_t(e.exp_structure().monoid(), *a));
00134           s_elt = p_exp.begin().semiring_elt() * s_elt;
00135           p_exp.begin().semiring_elt() =
00136             e.exp_structure().semiring().identity(SELECT(semiring_elt_value_t));
00137           link_to(p_exp, s_elt);
00138         }
00139       }
00140     }
00141 
00142     bool undefined;
00143   };
00144 
00145   template<typename T_auto, typename S, typename T>
00146   T_auto*
00147   do_derived_term_automaton(const T_auto& out,
00148                            const Element<S, T>& kexp)
00149   {
00150     Element<S, T>                       exp = realtime(kexp);
00151     DerivativesAlgo<T_auto, S, T>       derivatives_algo(out.series(), exp);
00152     derivatives_algo.run();
00153     if (derivatives_algo.undefined)
00154     {
00155       delete derivatives_algo.get();
00156       return NULL;
00157     }
00158     else
00159       return derivatives_algo.get();
00160   }
00161 
00162   template<typename A, typename T, typename Exp>
00163   void
00164   derived_term_automaton(Element<A, T>& out, const Exp& kexp)
00165   {
00166     TIMER_SCOPED("derived_term_automaton");
00167     Element<A, T>* res = do_derived_term_automaton(out, kexp);
00168     if (res)
00169       out = *res;
00170   }
00171 
00172   template<typename A, typename T, typename Exp>
00173   Element<A, T>
00174   derived_term_automaton(const Exp& kexp)
00175   {
00176     A                   a_structure(kexp.structure());
00177     Element<A, T>       out (a_structure);
00178     derived_term_automaton (out, kexp);
00179     return out;
00180   }
00181 
00182   // broken_derived_term_automaton implementation
00183   template<typename T_auto, typename S, typename T>
00184   T_auto*
00185   do_broken_derived_term_automaton(const T_auto& out,
00186                            const Element<S, T>& kexp)
00187   {
00188     Element<S, T>                       exp = realtime(kexp);
00189     KRatExpInitialDerivation< S, T, algebra::DispatchFunction<T> >
00190       matcher(exp);
00191     std::list< Element<S, T> > listexp = matcher.match(exp.value());
00192     DerivativesAlgo<T_auto, S, T> derivatives_algo(out.series(),
00193                                                    listexp);
00194     derivatives_algo.run();
00195     if (derivatives_algo.undefined)
00196     {
00197       delete derivatives_algo.get();
00198       return NULL;
00199     }
00200     else
00201       return derivatives_algo.get();
00202   }
00203 
00204   template<typename A, typename T, typename Exp>
00205   void
00206   broken_derived_term_automaton(Element<A, T>& out, const Exp& kexp)
00207   {
00208     Element<A, T>*      result = do_broken_derived_term_automaton(out, kexp);
00209     if (result != NULL)
00210       out = *result;
00211   }
00212 
00213   template<typename A, typename T, typename Exp>
00214   Element<A, T>
00215   broken_derived_term_automaton(const Exp& kexp)
00216   {
00217     A                   a_structure(kexp.structure());
00218     Element<A, T>       out (a_structure);
00219     Element<A, T>*      result = do_broken_derived_term_automaton(out, kexp);
00220     if (result != NULL)
00221       out = *result;
00222     return out;
00223   }
00224 
00225 
00226 
00227 } // vcsn
00228 
00229 #endif // ! VCSN_ALGORITHMS_DERIVED_TERM_AUTOMATON_HXX

Generated on Wed Jun 13 17:00:21 2007 for Vaucanson by  doxygen 1.5.1