PolyBoRi
CTermStack.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00014 //*****************************************************************************
00015 
00016 #ifndef polybori_iterators_CTermStack_h_
00017 #define polybori_iterators_CTermStack_h_
00018 
00019 // get standard header
00020 #include <stack>
00021 #include <iterator>
00022 #include <utility> // for std::pair
00023 
00024 // include basic definitions
00025 #include <polybori/pbori_defs.h>
00026 
00027 // include polybori functionals
00028 #include <polybori/routines/pbori_func.h>
00029 
00030 // include polybori properties
00031 #include <polybori/common/traits.h>
00032 
00033 #include <polybori/routines/pbori_routines.h>
00034  
00035 // include boost's indirect iterator facilities
00036 #include <boost/iterator/indirect_iterator.hpp>
00037 
00038 #include <polybori/BoolePolyRing.h>
00039 #include <polybori/BooleEnv.h>
00040 #include <polybori/cache/CDegreeCache.h>
00041 #include "CBidirectTermIter.h"
00042   
00043 #include <polybori/BooleSet.h>
00044 
00045 BEGIN_NAMESPACE_PBORI
00046 
00048 template<class NavigatorType>
00049 struct cached_deg {
00050   typedef CDegreeCache<BooleSet> cache_type;
00051   typedef typename cache_type::manager_type manager_type;
00052   cached_deg(const manager_type & mgr): m_deg_cache(mgr) {}
00053 
00054   typename NavigatorType::deg_type
00055   operator()(NavigatorType navi) const {
00056     return dd_cached_degree(m_deg_cache, navi);
00057   }
00058   cache_type m_deg_cache;
00059 };
00060 
00062 
00063 template <class NavigatorType>
00064 class cached_block_deg {
00065 public:
00066   typedef typename NavigatorType::idx_type idx_type;
00067 
00068   typedef cached_block_deg<NavigatorType> self;
00069 
00071   typedef std::vector<idx_type> block_idx_type;
00072 
00074   typedef typename block_idx_type::const_iterator block_iterator;
00075   typedef CBlockDegreeCache<BooleEnv::dd_type>
00076   cache_type;
00077   typedef typename cache_type::manager_type manager_type;
00078 
00079   cached_block_deg(const manager_type& mgr):
00080     m_current_block(block_begin(mgr)),
00081     m_deg_cache(mgr) { }
00082 
00083   typename NavigatorType::size_type
00084   operator()(NavigatorType navi) const {
00085     return dd_cached_block_degree(m_deg_cache, navi, max());
00086   }
00087 
00088   idx_type min() const {
00089     PBORI_ASSERT(*m_current_block != 0); // assuming first element to be zero
00090     return *(m_current_block - 1);
00091   }
00092 
00093   idx_type max() const {
00094     return *m_current_block;
00095   }
00096   self& operator++(){
00097     PBORI_ASSERT(max() != CTypes::max_idx);
00098     ++m_current_block;
00099     return *this;
00100   }
00101 
00102   self& operator--(){
00103     PBORI_ASSERT(min() != 0);
00104     --m_current_block;
00105     return *this;
00106   }
00107 
00108 private:
00109   //  block_iterator m_indices;
00110   block_iterator m_current_block;
00111 
00112   cache_type m_deg_cache;
00113 };
00114 
00115 
00116 
00117 
00125 template <class NavigatorType, class BaseType = internal_tag>
00126 class CTermStackBase:
00127   public BaseType {
00128 
00129 public:
00130 
00131   template <class, class> friend class CTermStackBase;
00132 
00133   typedef CTermStackBase<NavigatorType, BaseType> self;
00134 
00136   typedef NavigatorType navigator;
00138   typedef typename navigator::idx_type idx_type;
00139 
00141   typedef typename navigator::size_type size_type;
00142   typedef typename navigator::deg_type deg_type;
00143   typedef typename navigator::bool_type bool_type;
00144 
00145 
00147   typedef std::deque<navigator> stack_type;
00148 
00149   typedef typename stack_type::reference       reference;
00150   typedef typename stack_type::const_reference const_reference;
00151 
00152   typedef boost::indirect_iterator<typename stack_type::const_iterator,
00153                                    typename navigator::value_type, 
00154                                    boost::use_default, 
00155                                    typename navigator::reference>
00156   const_iterator;
00157 
00158   typedef typename stack_type::const_iterator stack_iterator;
00159 
00160   typedef typename stack_type::const_reverse_iterator stack_reverse_iterator;
00161 
00162   typedef boost::indirect_iterator<typename stack_type::const_reverse_iterator,
00163                                    typename navigator::value_type, 
00164                                    boost::use_default, 
00165                                    typename navigator::reference>
00166   const_reverse_iterator;
00167 
00168 private:
00169   void pop() { m_stack.pop_back(); }
00170 
00171 protected:
00172   void push(navigator __x) { m_stack.push_back(__x); }
00173 
00174   void clear() { m_stack.clear(); }
00175 
00176 
00177 public:
00178   bool_type empty() const { return m_stack.empty(); }
00179   const_reference top() const { 
00180     PBORI_ASSERT(!empty());
00181     return m_stack.back();
00182   }
00183   idx_type index() const { return *top(); }
00184   size_type size() const { return m_stack.size(); }
00185 
00186   const_iterator begin() const { return stackBegin(); }
00187   const_iterator end() const { return stackEnd(); }
00188 
00189   const_reverse_iterator rbegin() const { return stackRBegin(); }
00190 
00191   const_reverse_iterator rend() const { return stackREnd(); }
00192 
00194   navigator navigation() const {
00195     PBORI_ASSERT(m_stack.begin() != m_stack.end());
00196     return *m_stack.begin();
00197   }
00198 
00200   typedef typename stack_type::value_type top_type;
00201 
00203   CTermStackBase(): BaseType(), m_stack() { }
00204 
00206   CTermStackBase(navigator navi): BaseType(), m_stack() {
00207     if (navi.isValid())
00208       push(navi);
00209   }
00210 
00212   CTermStackBase(const CTermStackBase& rhs):
00213     BaseType(rhs), m_stack(rhs.m_stack) { }
00214 
00216   bool_type equal(const self& rhs) const {
00217 
00218     if(empty() || rhs.empty())
00219       return (empty() && rhs.empty());
00220     else
00221       return (m_stack == rhs.m_stack);
00222   }
00223 
00224   void incrementThen() {
00225     PBORI_ASSERT(!top().isConstant());
00226 
00227     push(top());
00228     m_stack.back().incrementThen();
00229   }
00230   void incrementElse() {
00231     PBORI_ASSERT(!isConstant());
00232     m_stack.back().incrementElse();
00233   }
00234 
00235   void decrementNode() {
00236     PBORI_ASSERT(!empty());
00237     pop();
00238   }
00239 
00240   bool_type isConstant() const {
00241     PBORI_ASSERT(!empty());
00242     return top().isConstant();
00243   }
00244 
00245   bool_type isTerminated() const {
00246     PBORI_ASSERT(!empty());
00247     return top().isTerminated();
00248   }
00249 
00250   bool_type isInvalid() const {
00251     PBORI_ASSERT(!empty());
00252     return top().isEmpty();
00253   }
00254 
00255   void followThen() {
00256     PBORI_ASSERT(!empty());
00257     while(!isConstant())
00258       incrementThen();
00259   }
00260 
00261   void markOne() {
00262     PBORI_ASSERT(empty());
00263     push(navigator());
00264   }
00265 
00266   bool_type markedOne() const {
00267     if PBORI_UNLIKELY(empty())
00268       return false;
00269     else
00270       return !m_stack.front().isValid();
00271   }
00272 
00273   void clearOne() {
00274     pop();
00275     PBORI_ASSERT(empty());
00276   } 
00277 
00278   deg_type deg() const {
00279     return (markedOne()? 0: (deg_type)size());
00280   }
00281 
00282   void restart(navigator navi) {
00283     PBORI_ASSERT(empty());
00284     push(navi);
00285   }
00286 
00287   bool isOne() const { return markedOne(); }
00288   bool isZero() const { return empty(); }
00289 
00290   bool atBegin() const { return empty(); }
00291 
00292   bool atEnd() const { return atEnd(top()); }
00293   bool atEnd(navigator navi) const { return navi.isConstant(); }
00294 
00295   bool validEnd() const {  return validEnd(top()); }
00296   bool validEnd(navigator navi) const { 
00297     while(!navi.isConstant()) {
00298       navi.incrementElse();
00299     }
00300     return navi.terminalValue();
00301   }
00302 
00303   void print() const{
00304     std::cout <<"(";
00305     std::copy(begin(), end(), std::ostream_iterator<int>(std::cout, ", ")); 
00306     std::cout <<")";
00307   }
00308 
00309   stack_iterator stackBegin() const { 
00310     if (markedOne())
00311       return m_stack.end();
00312     else
00313       return m_stack.begin(); 
00314   }
00315 
00316   stack_iterator stackEnd() const {
00317     return m_stack.end();
00318   }
00319 
00320   stack_reverse_iterator stackRBegin() const { 
00321     if (markedOne())
00322       return m_stack.rend();
00323     else
00324       return m_stack.rbegin(); 
00325   }
00326 
00327   stack_reverse_iterator stackREnd() const {
00328     return m_stack.rend();
00329   }
00330 protected:
00331 
00332   template <class TermStack>
00333   void append(const TermStack& rhs) { 
00334     PBORI_ASSERT(empty() || rhs.empty() || ((*rhs.begin()) > (*top())) );
00335     m_stack.insert(m_stack.end(), rhs.m_stack.begin(), rhs.m_stack.end());
00336   }
00337 
00338 
00339 private:
00340   stack_type m_stack;
00341 
00342   navigator m_zero;
00343 };
00344 
00345 
00346 
00352 template <class NavigatorType, class Category, class BaseType = internal_tag>
00353 class CTermStack:
00354   public CTermStackBase<NavigatorType, BaseType> {
00355 
00356 public:
00357   typedef CTermStackBase<NavigatorType, BaseType> base;
00358   typedef CTermStack<NavigatorType, Category, BaseType> self;
00359 
00361   typedef CTermStack<NavigatorType, Category, internal_tag> purestack_type;
00362   typedef Category iterator_category;
00363 
00364   typedef typename base::navigator navigator;
00365   typedef typename on_same_type<Category, std::forward_iterator_tag, 
00366                                 project_ith<0>, 
00367                                 handle_else<NavigatorType> >::type
00368                                 else_handler;
00369 
00370   else_handler handleElse;
00371 
00372   using base::incrementThen;
00373   using base::followThen;
00374 
00376   CTermStack(): base() { }
00377 
00379   CTermStack(navigator navi): base(navi) { }
00380 
00382   CTermStack(const CTermStack& rhs):
00383     base(rhs), handleElse(rhs.handleElse) { }
00384 
00387   template <class Dummy>
00388   CTermStack(navigator navi, const Dummy&): base(navi) { }
00389 
00390   void init() {
00391     if (!base::empty()){
00392       followThen();
00393       terminate();
00394     }
00395   }
00396 
00397   void initLast() {
00398     if (!base::empty()){
00399       followElse();
00400       terminate();
00401     }
00402   }
00403 
00404   void incrementElse() {
00405     handleElse(base::top());
00406     base::incrementElse();
00407   }
00408 
00409   void next() {
00410 
00411     bool invalid = true;
00412     while (!base::empty() && invalid) {
00413       incrementElse();
00414       if ((invalid = base::isInvalid()))
00415         base::decrementNode();
00416     }
00417   }
00418 
00419   void previous() {
00420     previous(Category());
00421   }
00422 
00423 
00424   void increment() {
00425     PBORI_ASSERT(!base::empty());
00426     if PBORI_UNLIKELY(base::markedOne()) {
00427       base::clearOne();
00428       return;
00429     }
00430       
00431     next();
00432     if PBORI_UNLIKELY(!base::empty()) {
00433       followThen();
00434       terminate();
00435     }
00436 
00437   }
00438 
00439    void decrement() {
00440 
00441     if PBORI_UNLIKELY(base::markedOne()) {
00442       base::clearOne();
00443     }
00444     previous();
00445     if PBORI_UNLIKELY(!base::empty()){
00446       followElse();
00447       base::decrementNode();
00448     }
00449 
00450   }
00451 
00452   void terminate() {
00453     PBORI_ASSERT(!base::empty());
00454 
00455     bool isZero = base::isInvalid();
00456     base::decrementNode();
00457     if PBORI_UNLIKELY(base::empty() && !isZero)
00458       base::markOne();
00459   }
00460 
00461 
00462   void followElse() {
00463     while( !base::isConstant() ) // if still in interior of a path
00464       incrementValidElse();
00465   }
00466   
00467   void incrementValidElse() {
00468     PBORI_ASSERT(!base::empty() && !base::isConstant());
00469     if(!base::top().elseBranch().isEmpty())
00470       incrementElse();          // go in direction of last term, if possible
00471     else
00472       incrementThen();
00473   } 
00474 
00475 protected:
00476   template <class TermStack>
00477   void append(const TermStack& rhs) {
00478     base::append(rhs);
00479     append(rhs, Category());
00480   }
00481 
00482 private:
00483   void previous(std::forward_iterator_tag);
00484   void previous(std::bidirectional_iterator_tag);
00485 
00486   template <class TermStack>
00487   void append(const TermStack&, std::forward_iterator_tag){}
00488 
00489   template <class TermStack>
00490   void append(const TermStack& rhs, std::bidirectional_iterator_tag){
00491      handleElse.append(rhs.handleElse); 
00492   }
00493 };
00494 
00495 
00496 template <class NavigatorType, class Category, class BaseType>
00497 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
00498   std::forward_iterator_tag) { }
00499 
00500 template <class NavigatorType, class Category, class BaseType>
00501 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
00502   std::bidirectional_iterator_tag) { 
00503 
00504   if(handleElse.empty()) {
00505     base::clear();
00506     return;
00507   }
00508 
00509   navigator navi = handleElse.top();
00510   PBORI_ASSERT(base::empty() || base::top().isValid());
00511 
00512   while(!base::empty() && (base::index() >= *navi) ) {
00513     base::decrementNode();
00514   }
00515 
00516   handleElse.pop();
00517   base::push(navi);
00518   incrementThen();
00519 }
00520 
00526 template <class NavigatorType, class Category>
00527 class CReverseTermStack:
00528   public CTermStack<NavigatorType, Category> {
00529 public: 
00530   typedef NavigatorType navigator;
00531   typedef CTermStack<NavigatorType, Category> base;
00532 
00534   CReverseTermStack(): base() { }
00535 
00537   CReverseTermStack(navigator navi): base(navi) {  }
00538 
00540   CReverseTermStack(const CReverseTermStack& rhs):  base(rhs) { }
00541 
00544   template <class Dummy>
00545   CReverseTermStack(navigator navi, const Dummy&): base(navi) { }
00546 
00547   void init() { base::initLast(); }
00548   void initLast() { base::init(); }
00549   void increment() { base::decrement(); }
00550   void decrement() { base::increment(); }
00551 };
00552 
00553 template <class NavigatorType, class BlockProperty, class Category, class
00554           BaseType = internal_tag>
00555 class CDegStackCore;
00556 
00558 template <class NavigatorType, class Category, class BaseType>
00559 class CDegStackCore<NavigatorType, invalid_tag, Category, BaseType>:
00560   public CTermStack<NavigatorType, Category, BaseType> {
00561 
00562 public:
00563   typedef CTermStack<NavigatorType, Category, BaseType> base;
00564   typedef NavigatorType navigator;
00565   typedef typename cached_deg<navigator>::manager_type manager_type;
00566 
00567   //  CDegStackCore(): base(), getDeg(manager_type()) {}
00568 
00569   CDegStackCore(navigator navi, const manager_type& mgr):
00570     base(navi), getDeg(mgr) {}
00571 
00572   CDegStackCore(const CDegStackCore& rhs):
00573     base(rhs), getDeg(rhs.getDeg) {}
00574 
00575   void gotoEnd()  {
00576      PBORI_ASSERT(!base::empty());
00577      while(!base::isConstant()) {
00578        base::incrementElse();
00579      }
00580   }
00581 
00582   cached_deg<navigator> getDeg;
00583 };
00584 
00586 template <class NavigatorType, class Category, class BaseType>
00587 class CDegStackCore<NavigatorType, valid_tag, Category, BaseType> :
00588   public CTermStack<NavigatorType, Category, BaseType> {
00589 
00590 public:
00591   typedef CTermStack<NavigatorType, Category, BaseType> base;
00592   typedef NavigatorType navigator;
00593   typedef typename base::idx_type idx_type;
00594   typedef typename base::deg_type deg_type;
00595   typedef typename base::size_type size_type;
00596   typedef typename cached_block_deg<navigator>::manager_type manager_type;
00597 
00598   //  CDegStackCore(): base(), block(manager_type()) {}
00599   CDegStackCore(navigator navi, const manager_type& mgr): 
00600     base(navi), block(mgr) {}
00601 
00602   CDegStackCore(const CDegStackCore& rhs):
00603     base(rhs), block(rhs.block) {}
00604 
00605   deg_type getDeg(navigator navi) const { return block(navi); }
00606 
00607   bool atBegin() const { 
00608     return base::empty() || (base::index() < block.min()); 
00609   }
00610 
00611   bool atEnd() const { return atEnd(base::top()); }
00612   bool atEnd(navigator navi) const {
00613     return navi.isConstant() || (*navi >= block.max());
00614   }
00615 
00616   bool validEnd() const{ return validEnd(base::top()); }
00617   bool validEnd(navigator navi) const {
00618 
00619     while(!atEnd(navi))
00620       navi.incrementElse();
00621 
00622     return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
00623   }
00624 
00625   void next() {
00626 
00627     bool invalid = true;
00628     while (!atBegin() && invalid) {
00629       PBORI_ASSERT(!base::isConstant());
00630       base::incrementElse();
00631       if ((invalid = base::isInvalid()))
00632         base::decrementNode();
00633     }
00634   }
00635   void previous() {
00636 
00637     if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
00638       while(!atBegin())
00639         base::decrementNode();
00640       return;
00641     }
00642     navigator navi =  base::handleElse.top();
00643     PBORI_ASSERT(base::top().isValid());
00644 
00645     while(!atBegin() && (base::index() >= *navi) ) {
00646       base::decrementNode();
00647     }
00648 
00649     if (base::empty() || (base::index() < *navi)) {
00650       base::handleElse.pop();
00651       base::push(navi);
00652     }
00653       base::incrementThen();
00654   }
00655 
00656   void gotoEnd()  {
00657      PBORI_ASSERT(!base::empty());
00658      while( (!base::isConstant()) && (base::index() < block.max()) ) {
00659        base::incrementElse();
00660      }
00661   }
00662 
00663 protected:
00664    cached_block_deg<navigator> block;
00665 };
00666 
00667 template <class NavigatorType, class BlockProperty, class DescendingProperty,
00668           class BaseType = internal_tag>
00669 class CDegStackBase;
00670 
00671 template <class NavigatorType, class BlockProperty, class BaseType>
00672 class CDegStackBase<NavigatorType, valid_tag, BlockProperty, BaseType>:
00673   public CDegStackCore<NavigatorType, BlockProperty, 
00674                        std::forward_iterator_tag, BaseType> {
00675 
00676 public:
00677   typedef CDegStackCore<NavigatorType, BlockProperty, 
00678                         std::forward_iterator_tag, BaseType> base;
00679 
00680   typedef typename base::size_type size_type;
00681   typedef typename base::deg_type deg_type;
00682   typedef std::greater<size_type> size_comparer;
00683   typedef typename base::manager_type manager_type;
00684 
00685   //  CDegStackBase(): base() {}
00686   CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
00687 
00688   CDegStackBase(const CDegStackBase& rhs):  base(rhs) {}
00689 
00690   integral_constant<bool, false> takeLast;
00691 
00692   void proximate() { base::next(); }
00693 
00694   void incrementBranch() { base::incrementThen(); }
00695 
00696   bool maxOnThen(deg_type deg) const {
00697     return (base::getDeg(base::top().thenBranch()) + 1 == deg);
00698   }
00699 
00700 };
00701 
00702 
00703 template <class NavigatorType, class BlockProperty, class BaseType>
00704 class CDegStackBase<NavigatorType, invalid_tag, BlockProperty, BaseType>:
00705     public CDegStackCore<NavigatorType, BlockProperty, 
00706                          std::bidirectional_iterator_tag, BaseType> {
00707 
00708 public:
00709   typedef CDegStackCore<NavigatorType, BlockProperty, 
00710                          std::bidirectional_iterator_tag, BaseType> base;
00711   typedef typename base::size_type size_type;
00712   typedef typename base::deg_type deg_type;
00713   typedef std::greater_equal<size_type> size_comparer;
00714   typedef typename base::manager_type manager_type;
00715 
00716   //  CDegStackBase(): base() {}
00717   CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
00718 
00719   CDegStackBase(const CDegStackBase& rhs):  base(rhs) {}
00720 
00721   integral_constant<bool, true> takeLast;
00722 
00723   void proximate() { base::previous(); }
00724 
00725   void incrementBranch() { base::incrementValidElse(); }
00726 
00727   bool maxOnThen(deg_type deg) const {
00728     return !(base::getDeg(base::top().elseBranch())  ==  deg);
00729   }
00730 };
00731 
00732 
00733 template <class NavigatorType, class DescendingProperty, 
00734           class BlockProperty = invalid_tag, class BaseType = internal_tag>
00735 class CDegTermStack:
00736   public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
00737 
00738 public:
00739   typedef CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> base;
00740   typedef CDegTermStack<NavigatorType, DescendingProperty, BlockProperty, BaseType> self;
00741 
00742   typedef typename base::navigator navigator;
00743   typedef typename navigator::size_type size_type;
00744   typedef typename navigator::deg_type deg_type;
00745   typedef typename base::manager_type manager_type;
00746 
00747   //  CDegTermStack(): base(), m_start() {}
00748   CDegTermStack(navigator navi, const manager_type& mgr):
00749     base(navi, mgr), m_start(navi), m_zero(mgr.zero().navigation()) {}
00750 
00751   CDegTermStack(const CDegTermStack& rhs):
00752     base(rhs), m_start(rhs.m_start), m_zero(rhs.m_zero) {}
00753 
00754   void init() {  
00755     if (!base::empty()) {
00756       followDeg();
00757       base::terminate();    
00758     }
00759   }
00760   void followDeg() {
00761     PBORI_ASSERT(!base::empty());
00762     
00763     deg_type deg = base::getDeg(base::top());
00764 
00765     while (deg > 0) {
00766 
00767       if ( base::maxOnThen(deg) ) {
00768         --deg;
00769         base::incrementThen();
00770       }
00771       else
00772         base::incrementElse();
00773         
00774     }
00775   }
00776 
00777   void increment() {
00778     PBORI_ASSERT(!base::empty());
00779     if (base::markedOne()) {
00780       base::clearOne();
00781       return;
00782     }
00783 
00784 
00785     size_type upperbound = base::size();
00786     degTerm();
00787 
00788     if(base::empty()) {
00789       restart();
00790       findTerm(upperbound);
00791     }
00792     if(!base::empty())
00793       base::terminate();
00794   }
00795 
00796 
00797   void degTerm() {
00798     size_type size = base::size() + 1;
00799 
00800     PBORI_ASSERT(!base::isConstant());
00801     bool doloop;
00802     do {
00803       PBORI_ASSERT(!base::empty());
00804       base::proximate();
00805 
00806       if (base::atBegin()) 
00807         return;
00808 
00809         while (!base::atEnd() && (base::size() < size) ) {
00810           base::incrementBranch();
00811         }
00812         base::gotoEnd();
00813 
00814         if ((doloop = (base::isInvalid() || (base::size() != size)) ) )
00815           base::decrementNode();
00816 
00817     } while (!base::empty() && doloop);
00818 
00819   }
00820 
00821  
00822   void decrement() {}
00823 
00824   void findTerm(size_type upperbound) {
00825     PBORI_ASSERT(!base::empty());
00826 
00827     typename base::purestack_type max_elt, current(base::top());
00828     base::decrementNode();
00829 
00830     typename base::size_comparer comp;
00831 
00832     while (!current.empty() && 
00833            (base::takeLast() || (max_elt.size() != upperbound)) ) {
00834       
00835       while (!base::atEnd(current.top()) && (current.size() < upperbound) )
00836         current.incrementThen();
00837       
00838       if (base::validEnd(current.top())) {
00839         if (comp(current.size(), max_elt.size()))
00840           max_elt = current;
00841         current.decrementNode();
00842       }
00843       current.next();
00844     }
00845     base::append(max_elt);
00846 
00847     if(max_elt.empty())
00848       invalidate();
00849   }
00850 
00851   void restart() { base::restart(m_start); }
00852 
00853   void invalidate() {
00854     PBORI_ASSERT(m_zero.isValid());
00855     PBORI_ASSERT(m_zero.isEmpty());
00856 
00857     base::push(m_zero);
00858   }
00859 
00860 private:
00861   navigator m_start, m_zero;
00862 };
00863 
00864 
00865 
00867 template <class NavigatorType, class DescendingProperty, class BaseType = internal_tag>
00868 class CBlockTermStack:
00869   public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
00870 
00871 public:
00872   typedef CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> base; 
00873   typedef CBlockTermStack<NavigatorType, DescendingProperty, BaseType> self;
00874 
00875   typedef typename base::navigator navigator;
00876   typedef typename navigator::size_type size_type;
00877   typedef typename navigator::idx_type idx_type;
00878   typedef typename base::manager_type manager_type;
00879 
00881   CBlockTermStack(navigator navi, const manager_type& mgr):
00882     base(navi, mgr) { }
00883 
00885   CBlockTermStack(const CBlockTermStack& rhs):  base(rhs) { }
00886 
00887   void init() {
00888     if (!base::empty()) {
00889       followDeg();
00890       base::terminate();
00891     }
00892   }
00893 
00894   void increment() {
00895     PBORI_ASSERT(!base::empty());
00896 
00897     if (base::markedOne()) {
00898       base::clearOne();
00899       return;
00900     }
00901 
00902     navigator current = base::top(); 
00903     while (*current < base::block.min())
00904       --base::block;
00905 
00906     incrementBlock();
00907     while ( (base::size() > 1 ) && base::isInvalid()  ) {
00908       --base::block;
00909       base::decrementNode();
00910       incrementBlock();
00911     }
00912 
00913     followDeg();
00914 
00915     PBORI_ASSERT(!base::empty());
00916     base::terminate();
00917   }
00918 
00919   void followBlockDeg() { base::followDeg(); }
00920 
00921   void followDeg() {
00922     PBORI_ASSERT(base::top().isValid());
00923 
00924     if (!base::isConstant() ) 
00925       followBlockDeg();
00926 
00927     while (!base::isConstant()  ) {
00928       ++base::block;
00929       followBlockDeg();
00930     }
00931   }
00932 
00933   void incrementBlock() {
00934 
00935     PBORI_ASSERT(!base::empty());
00936     size_type size = base::size() + 1;
00937     
00938     if (base::index() < base::block.min()) {
00939       base::invalidate();
00940       return;
00941     }
00942     
00943     base::degTerm();
00944     
00945     if (base::size() == size) return;
00946     
00947     if (base::empty())
00948       base::restart();
00949     else {
00950       PBORI_ASSERT(base::index() < base::block.min());
00951       base::incrementThen();
00952     }
00953     
00954     while (!base::isConstant() && (base::index() <  base::block.min()))
00955       base::incrementElse();
00956     
00957     PBORI_ASSERT(size > base::size()); 
00958     
00959     base::findTerm(size - base::size());
00960     base::gotoEnd();
00961   }
00962 };
00963 
00964 END_NAMESPACE_PBORI
00965 
00966 #endif