PolyBoRi
|
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