partial_rat_exp.hh

Go to the documentation of this file.
00001 // partial_rat_exp.hh: 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_INTERNAL_PARTIAL_RAT_EXP_HH
00018 # define VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HH
00019 
00032 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00033 # include <vaucanson/algorithms/krat_exp_constant_term.hh>
00034 # include <vaucanson/algebra/implementation/series/krat.hh>
00035 # include <list>
00036 
00037 namespace vcsn
00038 {
00039   /*---------------------.
00040   | Traits for iterators |
00041   `---------------------*/
00042 
00043   template <bool IsConst, typename T>
00044   struct reference_type
00045   { typedef T& ret; };
00046 
00047   template <typename T>
00048   struct reference_type<true, T>
00049   { typedef const T& ret; };
00050 
00051   template <bool IsConst, typename T>
00052   struct iterator_type
00053   { typedef typename T::iterator ret; };
00054 
00055   template <typename T>
00056   struct iterator_type<true, T>
00057   { typedef typename T::const_iterator ret; };
00058 
00059   /*-----------------.
00060   | PartialExp class |
00061   `-----------------*/
00062 
00063   // An implementation of Derivates represented by list of pointers.
00064   template <typename Series, typename T>
00065   struct PartialExp
00066   {
00067     // Common types
00068     typedef Element<Series, T>                  exp_t;
00069     typedef Series                              series_set_t;
00070     typedef T                                   series_set_elt_value_t;
00071     typedef typename T::node_t                  node_t;
00072     typedef typename exp_t::semiring_elt_t      semiring_elt_t;
00073 
00074     /*
00075      * A std::list is used because pop_front is needed,
00076      * and we must be able to modify an element of the list.
00077      */
00078     typedef std::list<const node_t*>            node_list_t;
00079     typedef std::list<semiring_elt_t>           semiring_elt_list_t;
00080 
00081     // Constructors
00082     // Be carefull: the exp must be realtime !
00083     PartialExp(const exp_t &e);
00084     PartialExp(const exp_t &e, const semiring_elt_t& w);
00085     PartialExp(const PartialExp &other);
00086 
00087     // Insert a new node into the list, and add another weight "after".
00088     PartialExp&                         insert(const node_t *v);
00089 
00090     // Accessors
00091     semiring_elt_list_t&                weights();
00092     const semiring_elt_list_t&          weights() const;
00093     node_list_t&                        nodes();
00094     const node_list_t&                  nodes() const;
00095 
00096     // Operators to change weights
00097     PartialExp&                         operator<<=(const semiring_elt_t& w);
00098     PartialExp&                         operator>>=(const semiring_elt_t& w);
00099 
00100     // Accessor for the rat_exp and usefull methods
00101     const exp_t&                        exp() const;
00102     const Series&                       exp_structure() const;
00103     const T&                            exp_value() const;
00104 
00105   protected:
00106     // Protected attributes
00107     const exp_t*                        rat_exp_;
00108     semiring_elt_list_t                 semiring_elt_list_;
00109     node_list_t                         node_list_;
00110 
00111   public:
00112     // internal class for iterator and const_iterator
00113     template <bool IsConst>
00114     struct internal_iterator
00115     {
00116     public:
00117       typedef typename
00118       reference_type<IsConst,semiring_elt_t>::ret       semiring_elt_ref_t;
00119       typedef typename
00120       reference_type<IsConst,const node_t*>::ret        node_ref_t;
00121       typedef typename
00122       iterator_type<IsConst,semiring_elt_list_t>::ret   semiring_elts_iterator_t;
00123       typedef typename
00124       iterator_type<IsConst,node_list_t>::ret           nodes_iterator_t;
00125     public:
00126       internal_iterator(const semiring_elts_iterator_t&,
00127                         const nodes_iterator_t&);
00128       internal_iterator&        operator++();
00129       internal_iterator         operator++(int);
00130       bool                      operator!=(const internal_iterator& other);
00131       bool                      operator==(const internal_iterator& other);
00132       semiring_elt_ref_t        semiring_elt() const;
00133       node_ref_t                node() const;
00134       bool                      on_node() const;
00135     protected:
00136       semiring_elts_iterator_t  semiring_elts_iterator_;
00137       nodes_iterator_t          nodes_iterator_;
00138       bool                      on_node_;
00139     };
00140 
00141     // definitions of iterator and const_iterator
00142     typedef internal_iterator<false>    iterator;
00143     typedef internal_iterator<true>     const_iterator;
00144 
00145     // iterators functions
00146     iterator                            begin();
00147     iterator                            end();
00148     const_iterator                      begin() const;
00149     const_iterator                      end() const;
00150   };
00151 
00152   /*---------------------.
00153   | PartialExp functions |
00154   `---------------------*/
00155 
00156   template <typename S, typename T>
00157   std::ostream& operator<< (std::ostream& o, const PartialExp<S, T>& e);
00158 
00159   // Be carefull: the exp must be realtime !
00160   template <typename S, typename T>
00161   std::list<PartialExp<S, T> > prat_exp_convert(const std::list<Element<S, T> >& exp);
00162 
00163   template <typename S, typename T>
00164   PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp);
00165 
00166   template <typename S, typename T>
00167   bool operator< (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2);
00168 
00169   template <typename S, typename T>
00170   bool operator== (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2);
00171 
00172   template <typename S, typename T>
00173   bool unweighted_eq(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2);
00174 
00175   template <typename S, typename T>
00176   bool unweighted_inf(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2);
00177 
00178 } // vcsn
00179 
00180 
00181 #ifndef VCSN_USE_INTERFACE_ONLY
00182     # include <vaucanson/algorithms/internal/partial_rat_exp.hxx>
00183 #endif // VCSN_USE_INTERFACE_ONLY
00184 
00185 
00186 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HH

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