16 #ifndef polybori_iterators_CTermStack_h_
17 #define polybori_iterators_CTermStack_h_
36 #include <boost/iterator/indirect_iterator.hpp>
48 template<
class NavigatorType>
52 cached_deg(
const manager_type & mgr): m_deg_cache(mgr) {}
63 template <
class NavigatorType>
83 typename NavigatorType::size_type
88 idx_type
min()
const {
90 return *(m_current_block - 1);
93 idx_type
max()
const {
94 return *m_current_block;
110 block_iterator m_current_block;
112 cache_type m_deg_cache;
125 template <
class NavigatorType,
class BaseType =
internal_tag>
152 typedef boost::indirect_iterator<
typename stack_type::const_iterator,
153 typename navigator::value_type,
155 typename navigator::reference>
162 typedef boost::indirect_iterator<
typename stack_type::const_reverse_iterator,
163 typename navigator::value_type,
165 typename navigator::reference>
169 void pop() { m_stack.pop_back(); }
172 void push(navigator __x) { m_stack.push_back(__x); }
178 bool_type
empty()
const {
return m_stack.empty(); }
179 const_reference
top()
const {
181 return m_stack.back();
183 idx_type
index()
const {
return *top(); }
184 size_type
size()
const {
return m_stack.size(); }
196 return *m_stack.begin();
213 BaseType(rhs), m_stack(rhs.m_stack) { }
216 bool_type
equal(
const self& rhs)
const {
218 if(empty() || rhs.empty())
219 return (empty() && rhs.empty());
221 return (m_stack == rhs.m_stack);
228 m_stack.back().incrementThen();
232 m_stack.back().incrementElse();
242 return top().isConstant();
247 return top().isTerminated();
252 return top().isEmpty();
270 return !m_stack.front().isValid();
279 return (markedOne()? 0: (deg_type)size());
287 bool isOne()
const {
return markedOne(); }
293 bool atEnd(navigator navi)
const {
return navi.isConstant(); }
297 while(!navi.isConstant()) {
298 navi.incrementElse();
300 return navi.terminalValue();
305 std::copy(begin(), end(), std::ostream_iterator<int>(std::cout,
", "));
311 return m_stack.end();
313 return m_stack.begin();
317 return m_stack.end();
322 return m_stack.rend();
324 return m_stack.rbegin();
328 return m_stack.rend();
332 template <
class TermStack>
334 PBORI_ASSERT(empty() || rhs.empty() || ((*rhs.begin()) > (*top())) );
335 m_stack.insert(m_stack.end(), rhs.m_stack.begin(), rhs.m_stack.end());
352 template <
class NavigatorType,
class Category,
class BaseType =
internal_tag>
365 typedef typename on_same_type<Category, std::forward_iterator_tag,
372 using base::incrementThen;
373 using base::followThen;
383 base(rhs), handleElse(rhs.handleElse) { }
387 template <
class Dummy>
405 handleElse(base::top());
406 base::incrementElse();
412 while (!base::empty() && invalid) {
414 if ((invalid = base::isInvalid()))
415 base::decrementNode();
420 previous(Category());
447 base::decrementNode();
455 bool isZero = base::isInvalid();
456 base::decrementNode();
463 while( !base::isConstant() )
464 incrementValidElse();
469 if(!base::top().elseBranch().isEmpty())
476 template <
class TermStack>
479 append(rhs, Category());
483 void previous(std::forward_iterator_tag);
484 void previous(std::bidirectional_iterator_tag);
486 template <
class TermStack>
487 void append(
const TermStack&, std::forward_iterator_tag){}
489 template <
class TermStack>
490 void append(
const TermStack& rhs, std::bidirectional_iterator_tag){
491 handleElse.append(rhs.handleElse);
496 template <
class NavigatorType,
class Category,
class BaseType>
497 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
498 std::forward_iterator_tag) { }
500 template <
class NavigatorType,
class Category,
class BaseType>
501 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
502 std::bidirectional_iterator_tag) {
504 if(handleElse.empty()) {
509 navigator navi = handleElse.top();
512 while(!base::empty() && (base::index() >= *navi) ) {
513 base::decrementNode();
526 template <
class NavigatorType,
class Category>
544 template <
class Dummy>
547 void init() { base::initLast(); }
553 template <
class NavigatorType,
class BlockProperty,
class Category,
class
554 BaseType = internal_tag>
558 template <
class NavigatorType,
class Category,
class BaseType>
560 public CTermStack<NavigatorType, Category, BaseType> {
563 typedef CTermStack<NavigatorType, Category, BaseType>
base;
570 base(navi), getDeg(mgr) {}
573 base(rhs), getDeg(rhs.getDeg) {}
577 while(!base::isConstant()) {
578 base::incrementElse();
586 template <
class NavigatorType,
class Category,
class BaseType>
588 public CTermStack<NavigatorType, Category, BaseType> {
591 typedef CTermStack<NavigatorType, Category, BaseType>
base;
600 base(navi), block(mgr) {}
603 base(rhs), block(rhs.block) {}
605 deg_type
getDeg(navigator navi)
const {
return block(navi); }
608 return base::empty() || (base::index() < block.min());
613 return navi.isConstant() || (*navi >= block.max());
620 navi.incrementElse();
622 return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
628 while (!atBegin() && invalid) {
630 base::incrementElse();
631 if ((invalid = base::isInvalid()))
632 base::decrementNode();
637 if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
639 base::decrementNode();
642 navigator navi = base::handleElse.top();
645 while(!atBegin() && (base::index() >= *navi) ) {
646 base::decrementNode();
649 if (base::empty() || (base::index() < *navi)) {
650 base::handleElse.pop();
653 base::incrementThen();
658 while( (!base::isConstant()) && (base::index() < block.max()) ) {
659 base::incrementElse();
667 template <
class NavigatorType,
class BlockProperty,
class DescendingProperty,
671 template <
class NavigatorType,
class BlockProperty,
class BaseType>
674 std::forward_iterator_tag, BaseType> {
678 std::forward_iterator_tag, BaseType>
base;
686 CDegStackBase(NavigatorType navi,
const manager_type& mgr): base(navi, mgr) {}
697 return (base::getDeg(base::top().thenBranch()) + 1 == deg);
703 template <
class NavigatorType,
class BlockProperty,
class BaseType>
706 std::bidirectional_iterator_tag, BaseType> {
710 std::bidirectional_iterator_tag, BaseType>
base;
717 CDegStackBase(NavigatorType navi,
const manager_type& mgr): base(navi, mgr) {}
728 return !(base::getDeg(base::top().elseBranch()) == deg);
733 template <
class NavigatorType,
class DescendingProperty,
734 class BlockProperty = invalid_tag,
class BaseType = internal_tag>
736 public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
749 base(navi, mgr), m_start(navi), m_zero(mgr.zero().navigation()) {}
752 base(rhs), m_start(rhs.m_start), m_zero(rhs.m_zero) {}
755 if (!base::empty()) {
763 deg_type deg = base::getDeg(base::top());
767 if ( base::maxOnThen(deg) ) {
769 base::incrementThen();
772 base::incrementElse();
779 if (base::markedOne()) {
785 size_type upperbound = base::size();
790 findTerm(upperbound);
798 size_type size = base::size() + 1;
809 while (!base::atEnd() && (base::size() < size) ) {
810 base::incrementBranch();
814 if ((doloop = (base::isInvalid() || (base::size() != size)) ) )
815 base::decrementNode();
817 }
while (!base::empty() && doloop);
827 typename base::purestack_type max_elt, current(base::top());
828 base::decrementNode();
830 typename base::size_comparer comp;
832 while (!current.empty() &&
833 (base::takeLast() || (max_elt.size() != upperbound)) ) {
835 while (!base::atEnd(current.top()) && (current.size() < upperbound) )
836 current.incrementThen();
838 if (base::validEnd(current.top())) {
839 if (comp(current.size(), max_elt.size()))
841 current.decrementNode();
845 base::append(max_elt);
861 navigator m_start, m_zero;
867 template <
class NavigatorType,
class DescendingProperty,
class BaseType =
internal_tag>
869 public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
888 if (!base::empty()) {
897 if (base::markedOne()) {
902 navigator current = base::top();
903 while (*current < base::block.min())
907 while ( (base::size() > 1 ) && base::isInvalid() ) {
909 base::decrementNode();
924 if (!base::isConstant() )
927 while (!base::isConstant() ) {
936 size_type size = base::size() + 1;
938 if (base::index() < base::block.min()) {
945 if (base::size() == size)
return;
951 base::incrementThen();
954 while (!base::isConstant() && (base::index() < base::block.min()))
955 base::incrementElse();
959 base::findTerm(size - base::size());
This class defines an iterator for the monomials in a Boolean polynomial in reversed lexicographicxal...
Definition: CTermStack.h:527
boost::indirect_iterator< typename stack_type::const_iterator, typename navigator::value_type, boost::use_default, typename navigator::reference > const_iterator
Definition: CTermStack.h:156
This class shows, whether a property of an order is invalid.
Definition: tags.h:27
void increment()
Definition: CTermStack.h:777
BooleEnv::block_iterator block_begin(const BooleEnv::ring_type &ring)
please use BooleEnv::ring()
Definition: BooleEnv.cc:138
base::size_type size_type
Definition: CTermStack.h:711
base::manager_type manager_type
Definition: CTermStack.h:878
CDegStackCore(navigator navi, const manager_type &mgr)
Definition: CTermStack.h:599
bool isOne() const
Definition: CTermStack.h:287
deg_type getDeg(navigator navi) const
Definition: CTermStack.h:605
void clear()
Definition: CTermStack.h:174
#define END_NAMESPACE_PBORI
Finish project's namespace.
Definition: pbori_defs.h:77
void next()
Definition: CTermStack.h:625
cached_block_deg< navigator > block
Definition: CTermStack.h:664
const_reverse_iterator rend() const
Definition: CTermStack.h:191
base::manager_type manager_type
Definition: CTermStack.h:683
CDegStackCore(const CDegStackCore &rhs)
Definition: CTermStack.h:572
bool validEnd() const
Definition: CTermStack.h:616
navigator::idx_type idx_type
Definition: CTermStack.h:877
idx_type max() const
Definition: CTermStack.h:93
#define BEGIN_NAMESPACE_PBORI
Start project's namespace.
Definition: pbori_defs.h:74
void proximate()
Definition: CTermStack.h:723
Definition: CTermStack.h:555
deg_type deg() const
Definition: CTermStack.h:278
stack_type::const_iterator stack_iterator
Definition: CTermStack.h:158
CReverseTermStack(navigator navi)
Construct from initial navigator.
Definition: CTermStack.h:537
void initLast()
Definition: CTermStack.h:397
base::size_type size_type
Definition: CTermStack.h:595
stack_type::const_reference const_reference
Definition: CTermStack.h:150
void increment()
Definition: CTermStack.h:424
NavigatorType navigator
Get type of navigators.
Definition: CTermStack.h:136
integral_constant< bool, false > takeLast
Definition: CTermStack.h:690
CTermStack< NavigatorType, Category, internal_tag > purestack_type
Defining a type for simple stacking of term elements.
Definition: CTermStack.h:361
cached_deg(const manager_type &mgr)
Definition: CTermStack.h:52
NaviType::deg_type dd_cached_degree(const DegreeCacher &cache, NaviType navi)
Definition: pbori_routines_misc.h:49
Definition: CBidirectTermIter.h:31
CDegStackBase(const CDegStackBase &rhs)
Definition: CTermStack.h:719
bool validEnd(navigator navi) const
Definition: CTermStack.h:617
int deg_type
Definition: groebner_defs.h:42
void previous()
Definition: CTermStack.h:419
base::navigator navigator
Definition: CTermStack.h:742
This class switches betweem two types, depending on equality of types.
Definition: pbori_func.h:589
CReverseTermStack()
Default constructor.
Definition: CTermStack.h:534
bool_type equal(const self &rhs) const
Equality test (assume iterators from same instance)
Definition: CTermStack.h:216
on_same_type< Category, std::forward_iterator_tag, project_ith< 0 >, handle_else< NavigatorType > >::type else_handler
Definition: CTermStack.h:368
void previous()
Definition: CTermStack.h:635
bool maxOnThen(deg_type deg) const
Definition: CTermStack.h:727
Accessing ith of n arguments (ITH = 0 returns default value of first type)
Definition: pbori_func.h:144
size_type size() const
Definition: CTermStack.h:184
CBlockTermStack(navigator navi, const manager_type &mgr)
Construct stack from navigator.
Definition: CTermStack.h:881
void restart()
Definition: CTermStack.h:851
CTermStackBase(const CTermStackBase &rhs)
Copy constructor.
Definition: CTermStack.h:212
void proximate()
Definition: CTermStack.h:692
void invalidate()
Definition: CTermStack.h:853
bool validEnd(navigator navi) const
Definition: CTermStack.h:296
Definition: CTermStack.h:868
std::deque< navigator > stack_type
Define type for stacking.
Definition: CTermStack.h:147
base::navigator navigator
Definition: CTermStack.h:364
idx_type index() const
Definition: CTermStack.h:183
NavigatorType::deg_type operator()(NavigatorType navi) const
Definition: CTermStack.h:55
void gotoEnd()
Definition: CTermStack.h:575
bool isZero() const
Definition: CTermStack.h:288
CTermStack(navigator navi)
Construct from initial navigator.
Definition: CTermStack.h:379
void next()
Definition: CTermStack.h:409
bool_type isInvalid() const
Definition: CTermStack.h:250
stack_reverse_iterator stackRBegin() const
Definition: CTermStack.h:320
CTermStack< NavigatorType, Category, BaseType > base
Definition: CTermStack.h:563
integral_constant< bool, true > takeLast
Definition: CTermStack.h:721
NavigatorType::size_type operator()(NavigatorType navi) const
Definition: CTermStack.h:84
void decrement()
Definition: CTermStack.h:822
CTermStackBase()
Default constructor.
Definition: CTermStack.h:203
void init()
Definition: CTermStack.h:547
void append(const TermStack &rhs)
Definition: CTermStack.h:333
else_handler handleElse
Definition: CTermStack.h:370
base::navigator navigator
Definition: CTermStack.h:875
self & operator--()
Definition: CTermStack.h:102
bool_type empty() const
Definition: CTermStack.h:178
cached_deg< navigator >::manager_type manager_type
Definition: CTermStack.h:565
navigator::bool_type bool_type
Definition: CTermStack.h:143
CBlockTermStack(const CBlockTermStack &rhs)
Copy constructor.
Definition: CTermStack.h:885
CTermStack(const CTermStack &rhs)
Copy constructor.
Definition: CTermStack.h:382
cached_deg< navigator > getDeg
Definition: CTermStack.h:582
stack_reverse_iterator stackREnd() const
Definition: CTermStack.h:327
void init()
Definition: CTermStack.h:754
void incrementElse()
Definition: CTermStack.h:230
CDegStackBase(NavigatorType navi, const manager_type &mgr)
Definition: CTermStack.h:717
boost::indirect_iterator< typename stack_type::const_reverse_iterator, typename navigator::value_type, boost::use_default, typename navigator::reference > const_reverse_iterator
Definition: CTermStack.h:166
void incrementBranch()
Definition: CTermStack.h:725
void init()
Definition: CTermStack.h:887
NaviType::deg_type dd_cached_block_degree(const DegreeCacher &cache, NaviType navi, IdxType nextBlock)
Definition: pbori_routines_order.h:278
Definition: CTermStack.h:735
Definition: CTermStack.h:64
CDegStackBase(NavigatorType navi, const manager_type &mgr)
Definition: CTermStack.h:686
void degTerm()
Definition: CTermStack.h:797
bool atEnd(navigator navi) const
Definition: CTermStack.h:612
navigator::idx_type idx_type
Type for indices.
Definition: CTermStack.h:138
void decrementNode()
Definition: CTermStack.h:235
NavigatorType navigator
Definition: CTermStack.h:564
void append(const TermStack &rhs)
Definition: CTermStack.h:477
stack_type::const_reverse_iterator stack_reverse_iterator
Definition: CTermStack.h:160
bool_type isConstant() const
Definition: CTermStack.h:240
bool validEnd() const
Definition: CTermStack.h:295
cache_type m_deg_cache
Definition: CTermStack.h:58
stack_iterator stackEnd() const
Definition: CTermStack.h:316
void init()
Definition: CTermStack.h:390
void findTerm(size_type upperbound)
Definition: CTermStack.h:824
void increment()
Definition: CTermStack.h:894
CDegStackCore< NavigatorType, BlockProperty, std::bidirectional_iterator_tag, BaseType > base
Definition: CTermStack.h:710
void followThen()
Definition: CTermStack.h:255
base::manager_type manager_type
Definition: CDegreeCache.h:274
Definition: CTermStack.h:49
void terminate()
Definition: CTermStack.h:452
base::deg_type deg_type
Definition: CTermStack.h:712
This class defines an iterator for the monomials in a Boolean polynomial.
Definition: CTermStack.h:353
CDegreeCache< BooleSet > cache_type
Definition: CTermStack.h:50
std::greater< size_type > size_comparer
Definition: CTermStack.h:682
base::size_type size_type
Definition: CTermStack.h:680
CDegTermStack(const CDegTermStack &rhs)
Definition: CTermStack.h:751
CDegTermStack< NavigatorType, DescendingProperty, valid_tag, BaseType > base
Definition: CTermStack.h:872
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
void followElse()
Definition: CTermStack.h:462
base::deg_type deg_type
Definition: CTermStack.h:681
bool atBegin() const
Definition: CTermStack.h:607
bool_type markedOne() const
Definition: CTermStack.h:266
void incrementBranch()
Definition: CTermStack.h:694
cache_type::manager_type manager_type
Definition: CTermStack.h:51
idx_type min() const
Definition: CTermStack.h:88
void incrementThen()
Definition: CTermStack.h:224
navigator navigation() const
Get navigator of stack start.
Definition: CTermStack.h:194
CDegStackCore(navigator navi, const manager_type &mgr)
Definition: CTermStack.h:569
stack_iterator stackBegin() const
Definition: CTermStack.h:309
void decrement()
Definition: CTermStack.h:550
cached_block_deg< navigator >::manager_type manager_type
Definition: CTermStack.h:596
std::vector< idx_type > block_idx_type
Type for block indices.
Definition: CTermStack.h:71
CTermStackBase(navigator navi)
Construct from initial navigator.
Definition: CTermStack.h:206
navigator::size_type size_type
Type for lengths.
Definition: CTermStack.h:141
void decrement()
Definition: CTermStack.h:439
self & operator++()
Definition: CTermStack.h:96
bool_type isTerminated() const
Definition: CTermStack.h:245
base::deg_type deg_type
Definition: CTermStack.h:594
const_iterator end() const
Definition: CTermStack.h:187
void print() const
Definition: CTermStack.h:303
stack_type::value_type top_type
result type of top()
Definition: CTermStack.h:200
std::greater_equal< size_type > size_comparer
Definition: CTermStack.h:713
CBlockDegreeCache< BooleEnv::dd_type > cache_type
Definition: CTermStack.h:76
cache_type::manager_type manager_type
Definition: CTermStack.h:77
base::manager_type manager_type
Definition: CTermStack.h:714
This class marks an internal part of a procedure.
Definition: pbori_func.h:607
CDegTermStack(navigator navi, const manager_type &mgr)
Definition: CTermStack.h:748
void initLast()
Definition: CTermStack.h:548
void followBlockDeg()
Definition: CTermStack.h:919
base::manager_type manager_type
Definition: CDegreeCache.h:151
CTermStack< NavigatorType, Category, BaseType > base
Definition: CTermStack.h:591
bool maxOnThen(deg_type deg) const
Definition: CTermStack.h:696
bool atEnd() const
Definition: CTermStack.h:611
CReverseTermStack(const CReverseTermStack &rhs)
Copy constructor.
Definition: CTermStack.h:540
CTermStack< NavigatorType, Category > base
Definition: CTermStack.h:531
base::idx_type idx_type
Definition: CTermStack.h:593
Category iterator_category
Definition: CTermStack.h:362
cached_block_deg(const manager_type &mgr)
Definition: CTermStack.h:79
polybori::CTypes::idx_type idx_type
Definition: groebner_defs.h:44
bool atBegin() const
Definition: CTermStack.h:290
void increment()
Definition: CTermStack.h:549
void incrementElse()
Definition: CTermStack.h:404
Definition: CTermStack.h:669
This class defines an iterator for the monomials in a Boolean polynomial.
Definition: CTermStack.h:126
CDegStackBase(const CDegStackBase &rhs)
Definition: CTermStack.h:688
NavigatorType navigator
Definition: CTermStack.h:530
NavigatorType navigator
Definition: CTermStack.h:592
void incrementValidElse()
Definition: CTermStack.h:467
navigator::size_type size_type
Definition: CTermStack.h:743
CDegStackCore< NavigatorType, BlockProperty, std::forward_iterator_tag, BaseType > base
Definition: CTermStack.h:678
CTermStack(navigator navi, const Dummy &)
Definition: CTermStack.h:388
stack_type::reference reference
Definition: CTermStack.h:149
void followDeg()
Definition: CTermStack.h:760
CDegStackBase< NavigatorType, DescendingProperty, BlockProperty, BaseType > base
Definition: CTermStack.h:739
void followDeg()
Definition: CTermStack.h:921
CDegStackCore(const CDegStackCore &rhs)
Definition: CTermStack.h:602
CTermStack()
Default constructor.
Definition: CTermStack.h:376
void clearOne()
Definition: CTermStack.h:273
navigator::size_type size_type
Definition: CTermStack.h:876
base::manager_type manager_type
Definition: CTermStack.h:745
void gotoEnd()
Definition: CTermStack.h:656
const_iterator begin() const
Definition: CTermStack.h:186
CTermStackBase< NavigatorType, BaseType > base
Definition: CTermStack.h:357
#define PBORI_UNLIKELY(expression)
Definition: pbori_defs.h:59
bool atEnd() const
Definition: CTermStack.h:292
void restart(navigator navi)
Definition: CTermStack.h:282
void markOne()
Definition: CTermStack.h:261
NavigatorType::idx_type idx_type
Definition: CTermStack.h:66
block_idx_type::const_iterator block_iterator
Type for block iterators.
Definition: CTermStack.h:74
bool atEnd(navigator navi) const
Definition: CTermStack.h:293
void incrementBlock()
Definition: CTermStack.h:933
This class shows, whether a property of an order is valid.
Definition: tags.h:32
const_reference top() const
Definition: CTermStack.h:179
const_reverse_iterator rbegin() const
Definition: CTermStack.h:189
CReverseTermStack(navigator navi, const Dummy &)
Definition: CTermStack.h:545
navigator::deg_type deg_type
Definition: CTermStack.h:744
void push(navigator __x)
Definition: CTermStack.h:172
navigator::deg_type deg_type
Definition: CTermStack.h:142