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