Vaucanson: partial_rat_exp.hxx Source File

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, 2008 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         {
00259           typename PartialExp<S, T>::series_set_elt_value_t v(i.node());
00260           typename PartialExp<S, T>::exp_t val(e.exp().structure(), v);
00261           o << '|' << val;
00262         }
00263       else
00264         {
00265           o << '|' << i.semiring_elt();
00266         }
00267     }
00268     return o << ']';
00269   }
00270 
00271   template <typename S, typename T, typename M, typename W>
00272   void prat_exp_list(PartialExp<S, T>&          pexp,
00273                      const rat::Node<M, W>*     node)
00274   {
00275     if (node->what() == rat::Node<M, W>::prod)
00276     {
00277       const rat::Product<M, W>* p =
00278         dynamic_cast<const rat::Product<M, W>*>(node);
00279       prat_exp_list(pexp, p->left_);
00280       prat_exp_list(pexp, p->right_);
00281     }
00282     else
00283       pexp.insert(node);
00284   }
00285 
00286   template <typename S, typename T, typename M, typename W>
00287   PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp,
00288                                     const rat::Node<M, W>* node)
00289   {
00290     typedef typename PartialExp<S, T>::semiring_elt_t   semiring_elt_t;
00291     semiring_elt_t      lw = exp.structure().semiring().identity(
00292       SELECT(typename semiring_elt_t::value_t));
00293     semiring_elt_t      rw = exp.structure().semiring().identity(
00294       SELECT(typename semiring_elt_t::value_t));
00295 
00296     while (node->what() == rat::Node<M, W>::lweight or
00297            node->what() == rat::Node<M, W>::rweight)
00298       if (node->what() == rat::Node<M, W>::lweight)
00299       {
00300         const rat::LeftWeighted<M, W>* p =
00301           dynamic_cast<const rat::LeftWeighted<M, W>*>(node);
00302         lw = p->weight_ * lw;
00303         node = p->child_;
00304       }
00305       else
00306       {
00307         const rat::RightWeighted<M, W>* p =
00308           dynamic_cast<const rat::RightWeighted<M, W>*>(node);
00309         rw *= p->weight_;
00310         node = p->child_;
00311       }
00312     PartialExp<S, T>    res(exp);
00313     prat_exp_list(res, node);
00314     res >>= lw;
00315     res <<= rw;
00316     return res;
00317   }
00318 
00319   template <typename S, typename T>
00320   PartialExp<S, T> prat_exp_convert(const Element<S, T>& exp)
00321   {
00322     return prat_exp_convert(exp, exp.value().base());
00323   }
00324 
00325   template <typename S, typename T>
00326   std::list<PartialExp<S, T> > prat_exp_convert(const std::list<Element<S, T> >& listexp)
00327   {
00328     std::list<PartialExp<S, T> > res;
00329     for (typename std::list<Element<S, T> >::const_iterator it =
00330            listexp.begin(); it != listexp.end(); ++it)
00331       res.push_back(prat_exp_convert(*it, it->value().base()));
00332     return res;
00333   }
00334 
00335   template <typename S, typename T>
00336   bool operator< (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00337   {
00338     typedef
00339     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00340     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00341     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00342 
00343     if (i1.semiring_elt() != i2.semiring_elt())
00344       return (i1.semiring_elt() < i2.semiring_elt());
00345 
00346     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00347     {
00348       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00349         break;
00350       ++i1;
00351       ++i2;
00352       if (i1.semiring_elt() != i2.semiring_elt())
00353         break;
00354       ++i1;
00355       ++i2;
00356     }
00357     if (i1 == e1.end() || i2 == e2.end())
00358       return (i1 == e1.end() && i2 != e2.end());
00359     else if (i1.on_node())
00360       return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
00361     else
00362       return i1.semiring_elt() < i2.semiring_elt();
00363   }
00364 
00365   template <typename S, typename T>
00366   bool operator== (const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00367   {
00368     typedef
00369     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00370     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00371     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00372 
00373     if (i1.semiring_elt() != i2.semiring_elt())
00374       return false;
00375 
00376     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00377     {
00378       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00379         break;
00380       ++i1;
00381       ++i2;
00382       if (i1.semiring_elt() != i2.semiring_elt())
00383         break;
00384       ++i1;
00385       ++i2;
00386     }
00387     return (i1 == e1.end() && i2 == e2.end());
00388   }
00389 
00390   template <typename S, typename T>
00391   bool unweighted_inf(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00392   {
00393     typedef
00394     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00395     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00396     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00397 
00398     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00399     {
00400       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00401         break;
00402       ++i1;
00403       ++i2;
00404       if (i1.semiring_elt() != i2.semiring_elt())
00405         break;
00406       ++i1;
00407       ++i2;
00408     }
00409     if (i1 == e1.end() || i2 == e2.end())
00410       return (i1 == e1.end() && i2 != e2.end());
00411     else if (i1.on_node())
00412       return series_set_elt_value_t(i1.node()) < series_set_elt_value_t(i2.node());
00413     else
00414       return i1.semiring_elt() < i2.semiring_elt();
00415   }
00416 
00417   template <typename S, typename T>
00418   bool unweighted_eq(const PartialExp<S, T>& e1, const PartialExp<S, T>& e2)
00419   {
00420     typedef
00421     typename PartialExp<S, T>::series_set_elt_value_t   series_set_elt_value_t;
00422     typename PartialExp<S, T>::const_iterator i1 = e1.begin();
00423     typename PartialExp<S, T>::const_iterator i2 = e2.begin();
00424 
00425     for (i1++, i2++; i1 != e1.end() and i2 != e2.end(); )
00426     {
00427       if (series_set_elt_value_t(i1.node()) != series_set_elt_value_t(i2.node()))
00428         break;
00429       ++i1;
00430       ++i2;
00431       if (i1.semiring_elt() != i2.semiring_elt())
00432         break;
00433       ++i1;
00434       ++i2;
00435     }
00436     return (i1 == e1.end() && i2 == e2.end());
00437   }
00438 
00439 } // vcsn
00440 
00441 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_HXX