118 #include <boost/iterator/indirect_iterator.hpp>
126 #ifndef CTermStack_h_
127 #define CTermStack_h_
132 template<
class NavigatorType>
134 typedef CDegreeCache<> cache_type;
135 typedef typename cache_type::manager_type manager_type;
136 cached_deg(
const manager_type & mgr): m_deg_cache(mgr) {}
138 typename NavigatorType::size_type
139 operator()(NavigatorType navi)
const {
142 cache_type m_deg_cache;
147 template <
class NavigatorType>
148 class cached_block_deg {
152 typedef cached_block_deg<NavigatorType>
self;
155 typedef std::vector<idx_type> block_idx_type;
158 typedef typename block_idx_type::const_iterator block_iterator;
159 typedef CBlockDegreeCache<CCacheTypes::block_degree, CTypes::dd_type>
161 typedef typename cache_type::manager_type manager_type;
163 cached_block_deg(
const manager_type& mgr):
165 m_current_block(BooleEnv::blockBegin()),
168 typename NavigatorType::size_type
169 operator()(NavigatorType navi)
const {
174 assert(*m_current_block != 0);
175 return *(m_current_block - 1);
179 return *m_current_block;
182 assert(max() != CTypes::max_idx);
195 block_iterator m_current_block;
197 cache_type m_deg_cache;
210 template <
class NavigatorType,
class BaseType =
internal_tag>
211 class CTermStackBase:
216 template <
class,
class>
friend class CTermStackBase;
218 typedef CTermStackBase<NavigatorType, BaseType>
self;
221 typedef NavigatorType navigator;
226 typedef typename navigator::size_type size_type;
227 typedef typename navigator::bool_type bool_type;
231 typedef std::deque<navigator> stack_type;
233 typedef typename stack_type::reference reference;
234 typedef typename stack_type::const_reference const_reference;
236 typedef boost::indirect_iterator<
typename stack_type::const_iterator,
237 typename navigator::value_type,
239 typename navigator::reference>
242 typedef typename stack_type::const_iterator stack_iterator;
244 typedef typename stack_type::const_reverse_iterator stack_reverse_iterator;
246 typedef boost::indirect_iterator<
typename stack_type::const_reverse_iterator,
247 typename navigator::value_type,
249 typename navigator::reference>
250 const_reverse_iterator;
253 void pop() { m_stack.pop_back(); }
256 void push(navigator __x) { m_stack.push_back(__x); }
258 void clear() { m_stack.clear(); }
263 const_reference top()
const {
return m_stack.back(); }
264 idx_type index()
const {
return *top(); }
265 bool_type empty()
const {
return m_stack.empty(); }
266 size_type size()
const {
return m_stack.size(); }
268 const_iterator begin()
const {
return stackBegin(); }
269 const_iterator end()
const {
return stackEnd(); }
271 const_reverse_iterator rbegin()
const {
return stackRBegin(); }
273 const_reverse_iterator rend()
const {
return stackREnd(); }
276 navigator navigation()
const {
277 assert(m_stack.begin() != m_stack.end());
278 return *m_stack.begin();
282 typedef typename stack_type::value_type top_type;
285 CTermStackBase(): BaseType(), m_stack() { }
288 CTermStackBase(navigator navi): BaseType(), m_stack() {
296 bool_type equal(
const self& rhs)
const {
298 if(empty() || rhs.empty())
299 return (empty() && rhs.empty());
301 return (m_stack == rhs.m_stack);
304 void incrementThen() {
305 assert(!top().isConstant());
308 m_stack.back().incrementThen();
310 void incrementElse() {
311 assert(!isConstant());
312 m_stack.back().incrementElse();
315 void decrementNode() {
320 bool_type isConstant()
const {
322 return top().isConstant();
325 bool_type isTerminated()
const {
327 return top().isTerminated();
330 bool_type isInvalid()
const {
332 return top().isEmpty();
346 bool_type markedOne()
const {
350 return !m_stack.front().isValid();
358 size_type deg()
const {
359 return (markedOne()? 0: size());
363 push(BooleEnv::zero().navigation());
366 void restart(navigator navi) {
371 bool isOne()
const {
return markedOne(); }
372 bool isZero()
const {
return empty(); }
374 bool atBegin()
const {
return empty(); }
376 bool atEnd()
const {
return atEnd(top()); }
377 bool atEnd(navigator navi)
const {
return navi.isConstant(); }
379 bool validEnd()
const {
return validEnd(top()); }
380 bool validEnd(navigator navi)
const {
381 while(!navi.isConstant()) {
382 navi.incrementElse();
384 return navi.terminalValue();
389 std::copy(begin(), end(), std::ostream_iterator<int>(cout,
", "));
393 stack_iterator stackBegin()
const {
395 return m_stack.end();
397 return m_stack.begin();
400 stack_iterator stackEnd()
const {
401 return m_stack.end();
404 stack_reverse_iterator stackRBegin()
const {
406 return m_stack.rend();
408 return m_stack.rbegin();
411 stack_reverse_iterator stackREnd()
const {
412 return m_stack.rend();
416 template <
class TermStack>
417 void append(
const TermStack& rhs) {
418 assert(empty() || rhs.empty() || ((*rhs.begin()) > (*top())) );
419 m_stack.insert(m_stack.end(), rhs.m_stack.begin(), rhs.m_stack.end());
430 template <
class NavigatorType,
class Category,
class BaseType =
internal_tag>
432 public CTermStackBase<NavigatorType, BaseType> {
435 typedef CTermStackBase<NavigatorType, BaseType> base;
436 typedef CTermStack<NavigatorType, Category, BaseType>
self;
439 typedef CTermStack<NavigatorType, Category, internal_tag> purestack_type;
440 typedef Category iterator_category;
442 typedef typename base::navigator navigator;
443 typedef typename on_same_type<Category, std::forward_iterator_tag,
445 handle_else<NavigatorType> >::type
448 else_handler handleElse;
450 using base::incrementThen;
451 using base::followThen;
454 CTermStack(): base() { }
457 CTermStack(navigator navi): base(navi) { }
461 template <
class Dummy>
462 CTermStack(navigator navi,
const Dummy&): base(navi) { }
474 void incrementElse() {
475 assert(!base::empty());
476 handleElse(base::top());
477 base::incrementElse();
483 while (!base::empty() && invalid) {
485 if (invalid = base::isInvalid())
486 base::decrementNode();
491 previous(Category());
496 assert(!base::empty());
497 if (base::markedOne()) {
503 if (!base::empty()) {
512 if (base::markedOne()) {
518 base::decrementNode();
523 assert(!base::empty());
525 bool isZero = base::isInvalid();
526 base::decrementNode();
527 if (base::empty() && !isZero)
533 while( !base::isConstant() )
534 incrementValidElse();
537 void incrementValidElse() {
538 assert(!base::empty() && !base::isConstant());
539 if(!base::top().elseBranch().isEmpty())
545 template <
class TermStack>
546 void append(
const TermStack& rhs) {
548 append(rhs, Category());
552 void previous(std::forward_iterator_tag);
553 void previous(std::bidirectional_iterator_tag);
555 template <
class TermStack>
556 void append(
const TermStack&, std::forward_iterator_tag){}
558 template <
class TermStack>
559 void append(
const TermStack& rhs, std::bidirectional_iterator_tag){
560 handleElse.append(rhs.handleElse);
565 template <
class NavigatorType,
class Category,
class BaseType>
566 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
567 std::forward_iterator_tag) { }
569 template <
class NavigatorType,
class Category,
class BaseType>
570 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
571 std::bidirectional_iterator_tag) {
573 if(handleElse.empty()) {
578 navigator navi = handleElse.top();
580 assert(base::top().isValid());
582 while(!base::empty() && (base::index() >= *navi) ) {
583 base::decrementNode();
592 template <
class NavigatorType,
class BlockProperty,
class Category,
class
593 BaseType = internal_tag>
597 template <
class NavigatorType,
class Category,
class BaseType>
598 class CDegStackCore<NavigatorType, invalid_tag, Category, BaseType>:
599 public CTermStack<NavigatorType, Category, BaseType> {
602 typedef CTermStack<NavigatorType, Category, BaseType> base;
603 typedef NavigatorType navigator;
604 typedef typename cached_deg<navigator>::manager_type manager_type;
606 CDegStackCore(): base(), getDeg(typename manager_type::mgrcore_ptr()) {}
608 CDegStackCore(navigator navi,
const manager_type& mgr):
609 base(navi), getDeg(mgr) {}
613 assert(!base::empty());
614 while(!base::isConstant()) {
615 base::incrementElse();
619 cached_deg<navigator> getDeg;
623 template <
class NavigatorType,
class Category,
class BaseType>
624 class CDegStackCore<NavigatorType, valid_tag, Category, BaseType> :
625 public CTermStack<NavigatorType, Category, BaseType> {
628 typedef CTermStack<NavigatorType, Category, BaseType> base;
629 typedef NavigatorType navigator;
631 typedef typename base::size_type size_type;
632 typedef typename cached_block_deg<navigator>::manager_type manager_type;
634 CDegStackCore(): base(), block(typename manager_type::mgrcore_ptr()) {}
635 CDegStackCore(navigator navi,
const manager_type& mgr):
636 base(navi), block(mgr) {}
638 size_type getDeg(navigator navi)
const {
return block(navi); }
640 bool atBegin()
const {
641 return base::empty() || (base::index() < block.min());
644 bool atEnd()
const {
return atEnd(base::top()); }
645 bool atEnd(navigator navi)
const {
646 return navi.isConstant() || (*navi >= block.max());
649 bool validEnd()
const{
return validEnd(base::top()); }
650 bool validEnd(navigator navi)
const {
653 navi.incrementElse();
655 return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
661 while (!atBegin() && invalid) {
662 assert(!base::isConstant());
663 base::incrementElse();
664 if (invalid = base::isInvalid())
665 base::decrementNode();
670 if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
672 base::decrementNode();
675 navigator navi = base::handleElse.top();
676 assert(base::top().isValid());
678 while(!atBegin() && (base::index() >= *navi) ) {
679 base::decrementNode();
682 if (base::empty() || (base::index() < *navi)) {
683 base::handleElse.pop();
686 base::incrementThen();
690 assert(!base::empty());
691 while( (!base::isConstant()) && (base::index() < block.max()) ) {
692 base::incrementElse();
697 cached_block_deg<navigator> block;
700 template <
class NavigatorType,
class BlockProperty,
class DescendingProperty,
701 class BaseType = internal_tag>
704 template <
class NavigatorType,
class BlockProperty,
class BaseType>
705 class CDegStackBase<NavigatorType, valid_tag, BlockProperty, BaseType>:
706 public CDegStackCore<NavigatorType, BlockProperty,
707 std::forward_iterator_tag, BaseType> {
710 typedef CDegStackCore<NavigatorType, BlockProperty,
711 std::forward_iterator_tag, BaseType> base;
713 typedef typename base::size_type size_type;
714 typedef std::greater<size_type> size_comparer;
715 typedef typename base::manager_type manager_type;
717 CDegStackBase(): base() {}
718 CDegStackBase(NavigatorType navi,
const manager_type& mgr): base(navi, mgr) {}
720 integral_constant<bool, false> takeLast;
722 void proximate() { base::next(); }
724 void incrementBranch() { base::incrementThen(); }
726 bool maxOnThen(size_type deg)
const {
727 return (base::getDeg(base::top().thenBranch()) + 1 == deg);
733 template <
class NavigatorType,
class BlockProperty,
class BaseType>
734 class CDegStackBase<NavigatorType, invalid_tag, BlockProperty, BaseType>:
735 public CDegStackCore<NavigatorType, BlockProperty,
736 std::bidirectional_iterator_tag, BaseType> {
739 typedef CDegStackCore<NavigatorType, BlockProperty,
740 std::bidirectional_iterator_tag, BaseType> base;
741 typedef typename base::size_type size_type;
742 typedef std::greater_equal<size_type> size_comparer;
743 typedef typename base::manager_type manager_type;
745 CDegStackBase(): base() {}
746 CDegStackBase(NavigatorType navi,
const manager_type& mgr): base(navi, mgr) {}
748 integral_constant<bool, true> takeLast;
750 void proximate() { base::previous(); }
752 void incrementBranch() { base::incrementValidElse(); }
754 bool maxOnThen(size_type deg)
const {
755 return !(base::getDeg(base::top().elseBranch()) == deg);
760 template <
class NavigatorType,
class DescendingProperty,
761 class BlockProperty = invalid_tag,
class BaseType = internal_tag>
763 public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
766 typedef CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> base;
767 typedef CDegTermStack<NavigatorType, DescendingProperty, BlockProperty, BaseType>
self;
769 typedef typename base::navigator navigator;
770 typedef typename navigator::size_type size_type;
771 typedef typename base::manager_type manager_type;
773 CDegTermStack(): base(), m_start() {}
774 CDegTermStack(navigator navi,
const manager_type& mgr):
775 base(navi, mgr), m_start(navi) {}
782 assert(!base::empty());
784 size_type deg = base::getDeg(base::top());
788 if ( base::maxOnThen(deg) ) {
790 base::incrementThen();
793 base::incrementElse();
799 assert(!base::empty());
800 if (base::markedOne()) {
806 size_type upperbound = base::size();
811 findTerm(upperbound);
819 size_type size = base::size() + 1;
821 assert(!base::isConstant());
824 assert(!base::empty());
830 while (!base::atEnd() && (base::size() < size) ) {
831 base::incrementBranch();
835 if (doloop = (base::isInvalid() || (base::size() != size)) )
836 base::decrementNode();
838 }
while (!base::empty() && doloop);
845 void findTerm(size_type upperbound) {
846 assert(!base::empty());
848 typename base::purestack_type max_elt, current(base::top());
849 base::decrementNode();
851 typename base::size_comparer comp;
853 while (!current.empty() &&
854 (base::takeLast() || (max_elt.size() != upperbound)) ) {
856 while (!base::atEnd(current.top()) && (current.size() < upperbound) )
857 current.incrementThen();
859 if (base::validEnd(current.top())) {
860 if (comp(current.size(), max_elt.size()))
862 current.decrementNode();
866 base::append(max_elt);
872 void restart() { base::restart(m_start); }
881 template <
class NavigatorType,
class DescendingProperty,
class BaseType =
internal_tag>
882 class CBlockTermStack:
883 public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
886 typedef CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> base;
887 typedef CBlockTermStack<NavigatorType, DescendingProperty, BaseType>
self;
889 typedef typename base::navigator navigator;
890 typedef typename navigator::size_type size_type;
892 typedef typename base::manager_type manager_type;
895 CBlockTermStack(navigator navi,
const manager_type& mgr):
899 CBlockTermStack(): base() {}
903 assert(!base::empty());
909 assert(!base::empty());
911 if (base::markedOne()) {
916 navigator current = base::top();
917 while (*current < base::block.min())
921 while ( (base::size() > 1 ) && base::isInvalid() ) {
923 base::decrementNode();
929 assert(!base::empty());
933 void followBlockDeg() { base::followDeg(); }
936 assert(base::top().isValid());
938 if (!base::isConstant() )
941 while (!base::isConstant() ) {
947 void incrementBlock() {
949 assert(!base::empty());
950 size_type size = base::size() + 1;
952 if (base::index() < base::block.min()) {
959 if (base::size() == size)
return;
964 assert(base::index() < base::block.min());
965 base::incrementThen();
968 while (!base::isConstant() && (base::index() < base::block.min()))
969 base::incrementElse();
971 assert(size > base::size());
973 base::findTerm(size - base::size());