16 #ifndef polybori_iterators_CTermStack_h_
17 #define polybori_iterators_CTermStack_h_
36 #include <boost/iterator/indirect_iterator.hpp>
48 template<
class NavigatorType>
63 template <
class NavigatorType>
83 typename NavigatorType::size_type
90 return *(m_current_block - 1);
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(); }
181 return m_stack.back();
196 return *m_stack.begin();
213 BaseType(rhs), m_stack(rhs.m_stack) { }
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(); }
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> {
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> {
600 base(navi), block(mgr) {}
603 base(rhs), block(rhs.block) {}
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();
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;
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;
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()) {
790 findTerm(upperbound);
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()) {
903 while (*current < base::block.min())
907 while ( (base::size() > 1 ) && base::isInvalid() ) {
909 base::decrementNode();
924 if (!base::isConstant() )
927 while (!base::isConstant() ) {
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());