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