partial_rat_exp.hxx

00001 // partial_rat_exp.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 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_HXX
00018 # define VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX
00019 
00020 # include <vaucanson/algorithms/internal/partial_rat_exp.hh>
00021 
00022 namespace vcsn
00023 {
00024   /*-----------------.
00025   | PartialExp class |
00026   `-----------------*/
00027 
00028   template <typename Series, typename T>
00029   PartialExp<Series, T>::PartialExp(const exp_t &e):
00030     rat_exp_(&e),
00031     semiring_elt_list_(),
00032     node_list_()
00033   {
00034     semiring_elt_list_.push_back(rat_exp_->structure().semiring().identity(
00035       SELECT(typename semiring_elt_t::value_t)));
00036   }
00037 
00038   template <typename Series, typename T>
00039   PartialExp<Series, T>::PartialExp(const PartialExp &other):
00040     rat_exp_(other.rat_exp_),
00041     semiring_elt_list_(other.semiring_elt_list_),
00042     node_list_(other.node_list_)
00043   { }
00044 
00045   template <typename Series, typename T>
00046   PartialExp<Series, T>::PartialExp(const exp_t &e, const semiring_elt_t& w):
00047     rat_exp_(&e),
00048     semiring_elt_list_(),
00049     node_list_()
00050   {
00051     semiring_elt_list_.push_back(w);
00052   }
00053 
00054   template <typename Series, typename T>
00055   PartialExp<Series, T>&
00056   PartialExp<Series, T>::insert(const node_t *v)
00057   {
00058     node_list_.push_back(v);
00059     semiring_elt_list_.push_back(rat_exp_->structure().semiring().identity(
00060       SELECT(typename semiring_elt_t::value_t)));
00061     return *this;
00062   }
00063 
00064   template <typename Series, typename T>
00065   typename PartialExp<Series, T>::semiring_elt_list_t&
00066   PartialExp<Series, T>::weights()
00067   {
00068     return semiring_elt_list_;
00069   }
00070 
00071   template <typename Series, typename T>
00072   const typename PartialExp<Series, T>::semiring_elt_list_t&
00073   PartialExp<Series, T>::weights() const
00074   {
00075     return semiring_elt_list_;
00076   }
00077 
00078   template <typename Series, typename T>
00079   const typename PartialExp<Series, T>::node_list_t&
00080   PartialExp<Series, T>::nodes() const
00081   {
00082     return node_list_;
00083   }
00084 
00085   template <typename Series, typename T>
00086   typename PartialExp<Series, T>::node_list_t&
00087   PartialExp<Series, T>::nodes()
00088   {
00089     return node_list_;
00090   }
00091 
00092   template <typename Series, typename T>
00093   PartialExp<Series, T>&
00094   PartialExp<Series, T>::operator<<=(const semiring_elt_t& w)
00095   {
00096     semiring_elt_list_.back() *= w;
00097     return *this;
00098   }
00099 
00100   template <typename Series, typename T>
00101   PartialExp<Series, T>&
00102   PartialExp<Series, T>::operator>>=(const semiring_elt_t& w)
00103   {
00104     semiring_elt_list_.front() = w * semiring_elt_list_.front();
00105     return *this;
00106   }
00107 
00108   template <typename Series, typename T>
00109   const Series&
00110   PartialExp<Series, T>::exp_structure() const
00111   {
00112     return rat_exp_->structure();
00113   }
00114 
00115   template <typename Series, typename T>
00116   const T&
00117   PartialExp<Series, T>::exp_value() const
00118   {
00119     return rat_exp_->value();
00120   }
00121 
00122   template <typename Series, typename T>
00123   const typename PartialExp<Series, T>::exp_t&
00124   PartialExp<Series, T>::exp() const
00125   {
00126     return *rat_exp_;
00127   }
00128 
00129   /*--------------------.
00130   | PartialExp iterator |
00131   `--------------------*/
00132 
00133   template <typename Series, typename T>
00134   template <bool IsConst>
00135   PartialExp<Series, T>::internal_iterator<IsConst>::internal_iterator(
00136     const semiring_elts_iterator_t& sit, const nodes_iterator_t& nit ):
00137       semiring_elts_iterator_(sit),
00138       nodes_iterator_(nit),
00139       on_node_ (false)
00140   {}
00141 
00142   template <typename Series, typename T>
00143   template <bool IsConst>
00144   PartialExp<Series, T>::internal_iterator<IsConst>&
00145   PartialExp<Series, T>::internal_iterator<IsConst>::operator++()
00146   {
00147     if (on_node_)
00148       ++nodes_iterator_;
00149     else
00150       ++semiring_elts_iterator_;
00151     on_node_ = not on_node_;
00152     return *this;
00153   }
00154 
00155   template <typename Series, typename T>
00156   template <bool IsConst>
00157   PartialExp<Series, T>::internal_iterator<IsConst>
00158   PartialExp<Series, T>::internal_iterator<IsConst>::operator++(int)
00159   {
00160     internal_iterator old = *this;
00161 
00162     if (on_node_)
00163       ++nodes_iterator_;
00164     else
00165       ++semiring_elts_iterator_;
00166     on_node_ = not on_node_;
00167     return old;
00168   }
00169 
00170   template <typename Series, typename T>
00171   template <bool IsConst>
00172   typename PartialExp<Series, T>::template internal_iterator<IsConst>::
00173   semiring_elt_ref_t
00174   PartialExp<Series, T>::internal_iterator<IsConst>::semiring_elt() const
00175   {
00176     assertion(!on_node_);
00177     return *semiring_elts_iterator_;
00178   }
00179 
00180   template <typename Series, typename T>
00181   template <bool IsConst>
00182   typename PartialExp<Series, T>::template internal_iterator<IsConst>::
00183   node_ref_t
00184   PartialExp<Series, T>::internal_iterator<IsConst>::node() const
00185   {
00186     assertion(on_node_);
00187     return *nodes_iterator_;
00188   }
00189 
00190   template <typename Series, typename T>
00191   template <bool IsConst>
00192   bool
00193   PartialExp<Series, T>::internal_iterator<IsConst>::on_node() const
00194   {
00195     return on_node_;
00196   }
00197 
00198   template <typename Series, typename T>
00199   template <bool IsConst>
00200   bool
00201   PartialExp<Series, T>::internal_iterator<IsConst>::operator!=(const internal_iterator& other)
00202   {
00203     return nodes_iterator_ != other.nodes_iterator_ or
00204       semiring_elts_iterator_ != other.semiring_elts_iterator_;
00205   }
00206 
00207   template <typename Series, typename T>
00208   template <bool IsConst>
00209   bool
00210   PartialExp<Series, T>::internal_iterator<IsConst>::operator==(const internal_iterator& other)
00211   {
00212     return nodes_iterator_ == other.nodes_iterator_ and
00213       semiring_elts_iterator_ == other.semiring_elts_iterator_;
00214   }
00215 
00216   template <typename Series, typename T>
00217   typename PartialExp<Series, T>::iterator
00218   PartialExp<Series, T>::begin()
00219   {
00220     return iterator(semiring_elt_list_.begin(), node_list_.begin());
00221   }
00222 
00223   template <typename Series, typename T>
00224   typename PartialExp<Series, T>::const_iterator
00225   PartialExp<Series, T>::begin() const
00226   {
00227     return const_iterator(semiring_elt_list_.begin(), node_list_.begin());
00228   }
00229 
00230   template <typename Series, typename T>
00231   typename PartialExp<Series, T>::iterator
00232   PartialExp<Series, T>::end()
00233   {
00234     return iterator(semiring_elt_list_.end(), node_list_.end());
00235   }
00236 
00237   template <typename Series, typename T>
00238   typename PartialExp<Series, T>::const_iterator
00239   PartialExp<Series, T>::end() const
00240   {
00241     return const_iterator(semiring_elt_list_.end(), node_list_.end());
00242   }
00243 
00244   /*---------------------.
00245   | PartialExp functions |
00246   `---------------------*/
00247 
00248   template <typename S, typename T>
00249   std::ostream& operator<< (std::ostream& o, const PartialExp<S, T>& e)
00250   {
00251     typename PartialExp<S, T>::const_iterator i = e.begin();
00252 
00253     o << '[' << i.semiring_elt();
00254 
00255     for (i++; i != e.end(); ++i)
00256     {
00257       if (i.on_node())
00258         o << '|' << typename PartialExp<S, T>::series_set_elt_value_t(i.node());
00259       else
00260         o << '|' << i.semiring_elt();
00261     }
00262     return o << ']';
00263   }
00264 
00265   template <typename S, typename T, typename M, typename W>
00266   void prat_exp_list(PartialExp<S, T>&          pexp,
00267                      const rat::Node<M, W>*     node)
00268   {
00269     if (node->what() == rat::Node<M, W>::prod)
00270     {
00271       const rat::Product<M, W>* p =
00272         dynamic_cast<const rat::Product<M, W>*>(node);
00273       prat_exp_list(pexp, p->left_);
00274       prat_exp_list(pexp, p->right_);
00275     }
00276     else
00277       pexp.insert(node);
00278   }
00279 
00280   template <typename S, typename T, typename M, typename W>
00281   PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp,
00282                                     const rat::Node<M, W>* node)
00283   {
00284     typedef typename PartialExp<S, T>::semiring_elt_t   semiring_elt_t;
00285     semiring_elt_t      lw = exp.structure().semiring().identity(
00286       SELECT(typename semiring_elt_t::value_t));
00287     semiring_elt_t      rw = exp.structure().semiring().identity(
00288       SELECT(typename semiring_elt_t::value_t));
00289 
00290     while (node->what() == rat::Node<M, W>::lweight or
00291            node->what() == rat::Node<M, W>::rweight)
00292       if (node->what() == rat::Node<M, W>::lweight)
00293       {
00294         const rat::LeftWeighted<M, W>* p =
00295           dynamic_cast<const rat::LeftWeighted<M, W>*>(node);
00296         lw = p->weight_ * lw;
00297         node = p->child_;
00298       }
00299       else
00300       {
00301         const rat::RightWeighted<M, W>* p =
00302           dynamic_cast<const rat::RightWeighted<M, W>*>(node);
00303         rw *= p->weight_;
00304         node = p->child_;
00305       }
00306     PartialExp<S, T>    res(exp);
00307     prat_exp_list(res, node);
00308     res >>= lw;
00309     res <<= rw;
00310     return res;
00311   }
00312 
00313   template <typename S, typename T>
00314   PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp)
00315   {
00316     return prat_exp_convert(exp, exp.value().base());
00317   }
00318 
00319   template <typename S, typename T>
00320   std::list<PartialExp<S, T> > prat_exp_convert(const std::list<Element<S, T> >& listexp)
00321   {
00322     std::list<PartialExp<S, T> > res;
00323     for (typename std::list<Element<S, T> >::const_iterator it =
00324            listexp.begin(); it != listexp.end(); ++it)
00325       res.push_back(prat_exp_convert(*it, it->value().base()));
00326     return res;
00327   }
00328 
00329   template <typename S, typename T>
00330   bool operator< (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00331   {
00332     typedef
00333     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00334     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00335     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00336 
00337     if (i1.semiring_elt() != i2.semiring_elt())
00338       return (i1.semiring_elt() < i2.semiring_elt());
00339 
00340     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00341     {
00342       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00343         break;
00344       ++i1;
00345       ++i2;
00346       if (i1.semiring_elt() != i2.semiring_elt())
00347         break;
00348       ++i1;
00349       ++i2;
00350     }
00351     if (i1 == e1.end() || i2 == e2.end())
00352       return (i1 == e1.end() && i2 != e2.end());
00353     else if (i1.on_node())
00354       return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
00355     else
00356       return i1.semiring_elt() < i2.semiring_elt();
00357   }
00358 
00359   template <typename S, typename T>
00360   bool operator== (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00361   {
00362     typedef
00363     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00364     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00365     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00366 
00367     if (i1.semiring_elt() != i2.semiring_elt())
00368       return false;
00369 
00370     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00371     {
00372       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00373         break;
00374       ++i1;
00375       ++i2;
00376       if (i1.semiring_elt() != i2.semiring_elt())
00377         break;
00378       ++i1;
00379       ++i2;
00380     }
00381     return (i1 == e1.end() && i2 == e2.end());
00382   }
00383 
00384   template <typename S, typename T>
00385   bool unweighted_inf(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00386   {
00387     typedef
00388     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00389     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00390     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00391 
00392     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00393     {
00394       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00395         break;
00396       ++i1;
00397       ++i2;
00398       if (i1.semiring_elt() != i2.semiring_elt())
00399         break;
00400       ++i1;
00401       ++i2;
00402     }
00403     if (i1 == e1.end() || i2 == e2.end())
00404       return (i1 == e1.end() && i2 != e2.end());
00405     else if (i1.on_node())
00406       return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
00407     else
00408       return i1.semiring_elt() < i2.semiring_elt();
00409   }
00410 
00411   template <typename S, typename T>
00412   bool unweighted_eq(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00413   {
00414     typedef
00415     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00416     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00417     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00418 
00419     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00420     {
00421       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00422         break;
00423       ++i1;
00424       ++i2;
00425       if (i1.semiring_elt() != i2.semiring_elt())
00426         break;
00427       ++i1;
00428       ++i2;
00429     }
00430     return (i1 == e1.end() && i2 == e2.end());
00431   }
00432 
00433 } // vcsn
00434 
00435 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX

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