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