PolyBoRi
CTermStack.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00014 //*****************************************************************************
00015 
00016 // get standard header
00017 #include <stack>
00018 #include <iterator>
00019 #include <utility> // for std::pair
00020 
00021 // include basic definitions
00022 #include "pbori_defs.h"
00023 
00024 // include polybori functionals
00025 #include "pbori_func.h"
00026 
00027 // include polybori properties
00028 #include "pbori_traits.h"
00029 
00030 #include "pbori_routines.h"
00031  
00032 // include boost's indirect iterator facilities
00033 #include <boost/iterator/indirect_iterator.hpp>
00034    
00035 #include "BooleEnv.h"
00036 #include "CDegreeCache.h"
00037 #include "CBidirectTermIter.h"
00038   
00039 #include "BooleSet.h"
00040 
00041 #ifndef CTermStack_h_
00042 #define CTermStack_h_
00043 
00044 BEGIN_NAMESPACE_PBORI
00045 
00047 template<class NavigatorType>
00048 struct cached_deg {
00049   typedef CDegreeCache<BooleSet> cache_type;
00050   typedef typename cache_type::manager_type manager_type;
00051   cached_deg(const manager_type & mgr): m_deg_cache(mgr) {}
00052 
00053   typename NavigatorType::size_type
00054   operator()(NavigatorType navi) const {
00055     return dd_cached_degree(m_deg_cache, navi);
00056   }
00057   cache_type m_deg_cache;
00058 };
00059 
00061 
00062 template <class NavigatorType>
00063 class cached_block_deg {
00064 public:
00065   typedef typename NavigatorType::idx_type idx_type;
00066 
00067   typedef cached_block_deg<NavigatorType> self;
00068 
00070   typedef std::vector<idx_type> block_idx_type;
00071 
00073   typedef typename block_idx_type::const_iterator block_iterator;
00074   typedef CBlockDegreeCache<BooleEnv::dd_type>
00075   cache_type;
00076   typedef typename cache_type::manager_type manager_type;
00077 
00078   cached_block_deg(const manager_type& mgr):
00079     //  m_indices(BoolePolyRing::blockRingBegin()), 
00080     m_current_block(BooleEnv::blockBegin()), 
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     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     assert(max() != CTypes::max_idx);
00098     ++m_current_block;
00099     return *this;
00100   }
00101 
00102   self& operator--(){
00103     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     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     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     push(navi);
00208   }
00209 
00211 
00212 
00214   bool_type equal(const self& rhs) const {
00215 
00216     if(empty() || rhs.empty())
00217       return (empty() && rhs.empty());
00218     else
00219       return (m_stack == rhs.m_stack);
00220   }
00221 
00222   void incrementThen() {
00223     assert(!top().isConstant());
00224 
00225     push(top());
00226     m_stack.back().incrementThen();
00227   }
00228   void incrementElse() {
00229     assert(!isConstant());
00230     m_stack.back().incrementElse();
00231   }
00232 
00233   void decrementNode() {
00234     assert(!empty());
00235     pop();
00236   }
00237 
00238   bool_type isConstant() const {
00239     assert(!empty());
00240     return top().isConstant();
00241   }
00242 
00243   bool_type isTerminated() const {
00244     assert(!empty());
00245     return top().isTerminated();
00246   }
00247 
00248   bool_type isInvalid() const {
00249     assert(!empty());
00250     return top().isEmpty();
00251   }
00252 
00253   void followThen() {
00254     assert(!empty());
00255     while(!isConstant())
00256       incrementThen();
00257   }
00258 
00259   void markOne() {
00260     assert(empty());
00261     push(navigator());
00262   }
00263 
00264   bool_type markedOne() const {
00265     if UNLIKELY(empty())
00266       return false;
00267     else
00268       return !m_stack.front().isValid();
00269   }
00270 
00271   void clearOne() {
00272     pop();
00273     assert(empty());
00274   } 
00275 
00276   deg_type deg() const {
00277     return (markedOne()? 0: (deg_type)size());
00278   }
00279 
00280   void invalidate() {
00281     push(BooleEnv::zero().navigation());
00282   }
00283 
00284   void restart(navigator navi) {
00285     assert(empty());
00286     push(navi);
00287   }
00288 
00289   bool isOne() const { return markedOne(); }
00290   bool isZero() const { return empty(); }
00291 
00292   bool atBegin() const { return empty(); }
00293 
00294   bool atEnd() const { return atEnd(top()); }
00295   bool atEnd(navigator navi) const { return navi.isConstant(); }
00296 
00297   bool validEnd() const {  return validEnd(top()); }
00298   bool validEnd(navigator navi) const { 
00299     while(!navi.isConstant()) {
00300       navi.incrementElse();
00301     }
00302     return navi.terminalValue();
00303   }
00304 
00305   void print() const{
00306     std::cout <<"(";
00307     std::copy(begin(), end(), std::ostream_iterator<int>(std::cout, ", ")); 
00308     std::cout <<")";
00309   }
00310 
00311   stack_iterator stackBegin() const { 
00312     if (markedOne())
00313       return m_stack.end();
00314     else
00315       return m_stack.begin(); 
00316   }
00317 
00318   stack_iterator stackEnd() const {
00319     return m_stack.end();
00320   }
00321 
00322   stack_reverse_iterator stackRBegin() const { 
00323     if (markedOne())
00324       return m_stack.rend();
00325     else
00326       return m_stack.rbegin(); 
00327   }
00328 
00329   stack_reverse_iterator stackREnd() const {
00330     return m_stack.rend();
00331   }
00332 protected:
00333 
00334   template <class TermStack>
00335   void append(const TermStack& rhs) { 
00336     assert(empty() || rhs.empty() || ((*rhs.begin()) > (*top())) );
00337     m_stack.insert(m_stack.end(), rhs.m_stack.begin(), rhs.m_stack.end());
00338   }
00339 
00340 
00341 private:
00342   stack_type m_stack;
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 
00383   template <class Dummy>
00384   CTermStack(navigator navi, const Dummy&): base(navi) { }
00385 
00386   void init() {
00387     followThen();
00388     terminate();
00389   }
00390 
00391   void initLast() {
00392     followElse();
00393     terminate();
00394   }
00395 
00396   void incrementElse() {
00397     handleElse(base::top());
00398     base::incrementElse();
00399   }
00400 
00401   void next() {
00402 
00403     bool invalid = true;
00404     while (!base::empty() && invalid) {
00405       incrementElse();
00406       if ((invalid = base::isInvalid()))
00407         base::decrementNode();
00408     }
00409   }
00410 
00411   void previous() {
00412     previous(Category());
00413   }
00414 
00415 
00416   void increment() {
00417     assert(!base::empty());
00418     if UNLIKELY(base::markedOne()) {
00419       base::clearOne();
00420       return;
00421     }
00422       
00423     next();
00424     if UNLIKELY(!base::empty()) {
00425       followThen();
00426       terminate();
00427     }
00428 
00429   }
00430 
00431    void decrement() {
00432 
00433     if UNLIKELY(base::markedOne()) {
00434       base::clearOne();
00435     }
00436     previous();
00437     if UNLIKELY(!base::empty()){
00438       followElse();
00439       base::decrementNode();
00440     }
00441 
00442   }
00443 
00444   void terminate() {
00445     assert(!base::empty());
00446 
00447     bool isZero = base::isInvalid();
00448     base::decrementNode();
00449     if UNLIKELY(base::empty() && !isZero)
00450       base::markOne();
00451   }
00452 
00453 
00454   void followElse() {
00455     while( !base::isConstant() ) // if still in interior of a path
00456       incrementValidElse();
00457   }
00458   
00459   void incrementValidElse() {
00460     assert(!base::empty() && !base::isConstant());
00461     if(!base::top().elseBranch().isEmpty())
00462       incrementElse();          // go in direction of last term, if possible
00463     else
00464       incrementThen();
00465   } 
00466 
00467 protected:
00468   template <class TermStack>
00469   void append(const TermStack& rhs) {
00470     base::append(rhs);
00471     append(rhs, Category());
00472   }
00473 
00474 private:
00475   void previous(std::forward_iterator_tag);
00476   void previous(std::bidirectional_iterator_tag);
00477 
00478   template <class TermStack>
00479   void append(const TermStack&, std::forward_iterator_tag){}
00480 
00481   template <class TermStack>
00482   void append(const TermStack& rhs, std::bidirectional_iterator_tag){
00483      handleElse.append(rhs.handleElse); 
00484   }
00485 };
00486 
00487 
00488 template <class NavigatorType, class Category, class BaseType>
00489 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
00490   std::forward_iterator_tag) { }
00491 
00492 template <class NavigatorType, class Category, class BaseType>
00493 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
00494   std::bidirectional_iterator_tag) { 
00495 
00496   if(handleElse.empty()) {
00497     base::clear();
00498     return;
00499   }
00500 
00501   navigator navi = handleElse.top();
00502   assert(base::empty() || base::top().isValid());
00503 
00504   while(!base::empty() && (base::index() >= *navi) ) {
00505     base::decrementNode();
00506   }
00507 
00508   handleElse.pop();
00509   base::push(navi);
00510   incrementThen();
00511 }
00512 
00518 template <class NavigatorType, class Category>
00519 class CReverseTermStack:
00520   public CTermStack<NavigatorType, Category> {
00521 public: 
00522   typedef NavigatorType navigator;
00523   typedef CTermStack<NavigatorType, Category> base;
00524 
00526   CReverseTermStack(): base() { }
00527 
00529   CReverseTermStack(navigator navi): base(navi) {  }
00530 
00533   template <class Dummy>
00534   CReverseTermStack(navigator navi, const Dummy&): base(navi) { }
00535 
00536   void init() { base::initLast(); }
00537   void initLast() { base::init(); }
00538   void increment() { base::decrement(); }
00539   void decrement() { base::increment(); }
00540 };
00541 
00542 template <class NavigatorType, class BlockProperty, class Category, class
00543           BaseType = internal_tag>
00544 class CDegStackCore;
00545 
00547 template <class NavigatorType, class Category, class BaseType>
00548 class CDegStackCore<NavigatorType, invalid_tag, Category, BaseType>:
00549   public CTermStack<NavigatorType, Category, BaseType> {
00550 
00551 public:
00552   typedef CTermStack<NavigatorType, Category, BaseType> base;
00553   typedef NavigatorType navigator;
00554   typedef typename cached_deg<navigator>::manager_type manager_type;
00555 
00556   CDegStackCore(): base(), getDeg(manager_type()) {}
00557 
00558   CDegStackCore(navigator navi, const manager_type& mgr):
00559     base(navi), getDeg(mgr) {}
00560 
00561 
00562   void gotoEnd()  {
00563      assert(!base::empty());
00564      while(!base::isConstant()) {
00565        base::incrementElse();
00566      }
00567   }
00568 
00569   cached_deg<navigator> getDeg;
00570 };
00571 
00573 template <class NavigatorType, class Category, class BaseType>
00574 class CDegStackCore<NavigatorType, valid_tag, Category, BaseType> :
00575   public CTermStack<NavigatorType, Category, BaseType> {
00576 
00577 public:
00578   typedef CTermStack<NavigatorType, Category, BaseType> base;
00579   typedef NavigatorType navigator;
00580   typedef typename base::idx_type idx_type;
00581   typedef typename base::size_type size_type;
00582   typedef typename cached_block_deg<navigator>::manager_type manager_type;
00583 
00584   CDegStackCore(): base(), block(manager_type()) {}
00585   CDegStackCore(navigator navi, const manager_type& mgr): 
00586     base(navi), block(mgr) {}
00587 
00588   size_type getDeg(navigator navi) const { return block(navi); }
00589 
00590   bool atBegin() const { 
00591     return base::empty() || (base::index() < block.min()); 
00592   }
00593 
00594   bool atEnd() const { return atEnd(base::top()); }
00595   bool atEnd(navigator navi) const {
00596     return navi.isConstant() || (*navi >= block.max());
00597   }
00598 
00599   bool validEnd() const{ return validEnd(base::top()); }
00600   bool validEnd(navigator navi) const {
00601 
00602     while(!atEnd(navi))
00603       navi.incrementElse();
00604 
00605     return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
00606   }
00607 
00608   void next() {
00609 
00610     bool invalid = true;
00611     while (!atBegin() && invalid) {
00612       assert(!base::isConstant());
00613       base::incrementElse();
00614       if ((invalid = base::isInvalid()))
00615         base::decrementNode();
00616     }
00617   }
00618   void previous() {
00619 
00620     if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
00621       while(!atBegin())
00622         base::decrementNode();
00623       return;
00624     }
00625     navigator navi =  base::handleElse.top();
00626     assert(base::top().isValid());
00627 
00628     while(!atBegin() && (base::index() >= *navi) ) {
00629       base::decrementNode();
00630     }
00631 
00632     if (base::empty() || (base::index() < *navi)) {
00633       base::handleElse.pop();
00634       base::push(navi);
00635     }
00636       base::incrementThen();
00637   }
00638 
00639   void gotoEnd()  {
00640      assert(!base::empty());
00641      while( (!base::isConstant()) && (base::index() < block.max()) ) {
00642        base::incrementElse();
00643      }
00644   }
00645 
00646 protected:
00647    cached_block_deg<navigator> block;
00648 };
00649 
00650 template <class NavigatorType, class BlockProperty, class DescendingProperty,
00651           class BaseType = internal_tag>
00652 class CDegStackBase;
00653 
00654 template <class NavigatorType, class BlockProperty, class BaseType>
00655 class CDegStackBase<NavigatorType, valid_tag, BlockProperty, BaseType>:
00656   public CDegStackCore<NavigatorType, BlockProperty, 
00657                        std::forward_iterator_tag, BaseType> {
00658 
00659 public:
00660   typedef CDegStackCore<NavigatorType, BlockProperty, 
00661                         std::forward_iterator_tag, BaseType> base;
00662 
00663   typedef typename base::size_type size_type;
00664   typedef typename base::deg_type deg_type;
00665   typedef std::greater<size_type> size_comparer;
00666   typedef typename base::manager_type manager_type;
00667 
00668   CDegStackBase(): base() {}
00669   CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
00670 
00671   integral_constant<bool, false> takeLast;
00672 
00673   void proximate() { base::next(); }
00674 
00675   void incrementBranch() { base::incrementThen(); }
00676 
00677   bool maxOnThen(deg_type deg) const {
00678     return (base::getDeg(base::top().thenBranch()) + 1 == deg);
00679   }
00680 
00681 };
00682 
00683 
00684 template <class NavigatorType, class BlockProperty, class BaseType>
00685 class CDegStackBase<NavigatorType, invalid_tag, BlockProperty, BaseType>:
00686     public CDegStackCore<NavigatorType, BlockProperty, 
00687                          std::bidirectional_iterator_tag, BaseType> {
00688 
00689 public:
00690   typedef CDegStackCore<NavigatorType, BlockProperty, 
00691                          std::bidirectional_iterator_tag, BaseType> base;
00692   typedef typename base::size_type size_type;
00693   typedef typename base::deg_type deg_type;
00694   typedef std::greater_equal<size_type> size_comparer;
00695   typedef typename base::manager_type manager_type;
00696 
00697   CDegStackBase(): base() {}
00698   CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
00699 
00700   integral_constant<bool, true> takeLast;
00701 
00702   void proximate() { base::previous(); }
00703 
00704   void incrementBranch() { base::incrementValidElse(); }
00705 
00706   bool maxOnThen(deg_type deg) const {
00707     return !(base::getDeg(base::top().elseBranch())  ==  deg);
00708   }
00709 };
00710 
00711 
00712 template <class NavigatorType, class DescendingProperty, 
00713           class BlockProperty = invalid_tag, class BaseType = internal_tag>
00714 class CDegTermStack:
00715   public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
00716 
00717 public:
00718   typedef CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> base;
00719   typedef CDegTermStack<NavigatorType, DescendingProperty, BlockProperty, BaseType> self;
00720 
00721   typedef typename base::navigator navigator;
00722   typedef typename navigator::size_type size_type;
00723   typedef typename navigator::deg_type deg_type;
00724   typedef typename base::manager_type manager_type;
00725 
00726   CDegTermStack(): base(), m_start() {}
00727   CDegTermStack(navigator navi, const manager_type& mgr):
00728     base(navi, mgr), m_start(navi) {}
00729 
00730   void init() {
00731     followDeg();
00732     base::terminate();    
00733   }
00734   void followDeg() {
00735     assert(!base::empty());
00736     
00737     deg_type deg = base::getDeg(base::top());
00738 
00739     while (deg > 0) {
00740 
00741       if ( base::maxOnThen(deg) ) {
00742         --deg;
00743         base::incrementThen();
00744       }
00745       else
00746         base::incrementElse();
00747         
00748     }
00749   }
00750 
00751   void increment() {
00752     assert(!base::empty());
00753     if (base::markedOne()) {
00754       base::clearOne();
00755       return;
00756     }
00757 
00758 
00759     size_type upperbound = base::size();
00760     degTerm();
00761 
00762     if(base::empty()) {
00763       restart();
00764       findTerm(upperbound);
00765     }
00766     if(!base::empty())
00767       base::terminate();
00768   }
00769 
00770 
00771   void degTerm() {
00772     size_type size = base::size() + 1;
00773 
00774     assert(!base::isConstant());
00775     bool doloop;
00776     do {
00777       assert(!base::empty());
00778       base::proximate();
00779 
00780       if (base::atBegin()) 
00781         return;
00782 
00783         while (!base::atEnd() && (base::size() < size) ) {
00784           base::incrementBranch();
00785         }
00786         base::gotoEnd();
00787 
00788         if ((doloop = (base::isInvalid() || (base::size() != size)) ))
00789           base::decrementNode();
00790 
00791     } while (!base::empty() && doloop);
00792 
00793   }
00794 
00795  
00796   void decrement() {}
00797 
00798   void findTerm(size_type upperbound) {
00799     assert(!base::empty());
00800 
00801     typename base::purestack_type max_elt, current(base::top());
00802     base::decrementNode();
00803 
00804     typename base::size_comparer comp;
00805 
00806     while (!current.empty() && 
00807            (base::takeLast() || (max_elt.size() != upperbound)) ) {
00808       
00809       while (!base::atEnd(current.top()) && (current.size() < upperbound) )
00810         current.incrementThen();
00811       
00812       if (base::validEnd(current.top())) {
00813         if (comp(current.size(), max_elt.size()))
00814           max_elt = current;
00815         current.decrementNode();
00816       }
00817       current.next();
00818     }
00819     base::append(max_elt);
00820 
00821     if(max_elt.empty())
00822       base::invalidate();
00823   }
00824 
00825   void restart() { base::restart(m_start); }
00826 
00827 private:
00828   navigator m_start;
00829 };
00830 
00831 
00832 
00834 template <class NavigatorType, class DescendingProperty, class BaseType = internal_tag>
00835 class CBlockTermStack:
00836   public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
00837 
00838 public:
00839   typedef CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> base; 
00840   typedef CBlockTermStack<NavigatorType, DescendingProperty, BaseType> self;
00841 
00842   typedef typename base::navigator navigator;
00843   typedef typename navigator::size_type size_type;
00844   typedef typename navigator::idx_type idx_type;
00845   typedef typename base::manager_type manager_type;
00846 
00848   CBlockTermStack(navigator navi, const manager_type& mgr):
00849     base(navi, mgr) { }
00850 
00852   CBlockTermStack(): base() {}
00853 
00854 
00855   void init() {
00856     assert(!base::empty());
00857     followDeg();
00858     base::terminate();
00859   }
00860 
00861   void increment() {
00862     assert(!base::empty());
00863 
00864     if (base::markedOne()) {
00865       base::clearOne();
00866       return;
00867     }
00868 
00869     navigator current = base::top(); 
00870     while (*current < base::block.min())
00871       --base::block;
00872 
00873     incrementBlock();
00874     while ( (base::size() > 1 ) && base::isInvalid()  ) {
00875       --base::block;
00876       base::decrementNode();
00877       incrementBlock();
00878     }
00879 
00880     followDeg();
00881 
00882     assert(!base::empty());
00883     base::terminate();
00884   }
00885 
00886   void followBlockDeg() { base::followDeg(); }
00887 
00888   void followDeg() {
00889     assert(base::top().isValid());
00890 
00891     if (!base::isConstant() ) 
00892       followBlockDeg();
00893 
00894     while (!base::isConstant()  ) {
00895       ++base::block;
00896       followBlockDeg();
00897     }
00898   }
00899 
00900   void incrementBlock() {
00901 
00902     assert(!base::empty());
00903     size_type size = base::size() + 1;
00904     
00905     if (base::index() < base::block.min()) {
00906       base::invalidate();
00907       return;
00908     }
00909     
00910     base::degTerm();
00911     
00912     if (base::size() == size) return;
00913     
00914     if (base::empty())
00915       base::restart();
00916     else {
00917       assert(base::index() < base::block.min());
00918       base::incrementThen();
00919     }
00920     
00921     while (!base::isConstant() && (base::index() <  base::block.min()))
00922       base::incrementElse();
00923     
00924     assert(size > base::size()); 
00925     
00926     base::findTerm(size - base::size());
00927     base::gotoEnd();
00928   }
00929 };
00930 
00931 END_NAMESPACE_PBORI
00932 
00933 #endif