PolyBoRi
CTermStack.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_iterators_CTermStack_h_
17 #define polybori_iterators_CTermStack_h_
18 
19 // get standard header
20 #include <stack>
21 #include <iterator>
22 #include <utility> // for std::pair
23 
24 // include basic definitions
25 #include <polybori/pbori_defs.h>
26 
27 // include polybori functionals
29 
30 // include polybori properties
31 #include <polybori/common/traits.h>
32 
34 
35 // include boost's indirect iterator facilities
36 #include <boost/iterator/indirect_iterator.hpp>
37 
38 #include <polybori/BoolePolyRing.h>
39 #include <polybori/BooleEnv.h>
41 #include "CBidirectTermIter.h"
42 
43 #include <polybori/BooleSet.h>
44 
46 
48 template<class NavigatorType>
49 struct cached_deg {
52  cached_deg(const manager_type & mgr): m_deg_cache(mgr) {}
53 
55  operator()(NavigatorType navi) const {
56  return dd_cached_degree(m_deg_cache, navi);
57  }
59 };
60 
62 
63 template <class NavigatorType>
65 public:
67 
69 
71  typedef std::vector<idx_type> block_idx_type;
72 
74  typedef typename block_idx_type::const_iterator block_iterator;
78 
80  m_current_block(block_begin(mgr)),
81  m_deg_cache(mgr) { }
82 
83  typename NavigatorType::size_type
84  operator()(NavigatorType navi) const {
85  return dd_cached_block_degree(m_deg_cache, navi, max());
86  }
87 
88  idx_type min() const {
89  PBORI_ASSERT(*m_current_block != 0); // assuming first element to be zero
90  return *(m_current_block - 1);
91  }
92 
93  idx_type max() const {
94  return *m_current_block;
95  }
96  self& operator++(){
97  PBORI_ASSERT(max() != CTypes::max_idx);
98  ++m_current_block;
99  return *this;
100  }
101 
102  self& operator--(){
103  PBORI_ASSERT(min() != 0);
104  --m_current_block;
105  return *this;
106  }
107 
108 private:
109  // block_iterator m_indices;
110  block_iterator m_current_block;
111 
112  cache_type m_deg_cache;
113 };
114 
115 
116 
117 
125 template <class NavigatorType, class BaseType = internal_tag>
127  public BaseType {
128 
129 public:
130 
131  template <class, class> friend class CTermStackBase;
132 
134 
136  typedef NavigatorType navigator;
138  typedef typename navigator::idx_type idx_type;
139 
141  typedef typename navigator::size_type size_type;
142  typedef typename navigator::deg_type deg_type;
143  typedef typename navigator::bool_type bool_type;
144 
145 
147  typedef std::deque<navigator> stack_type;
148 
149  typedef typename stack_type::reference reference;
150  typedef typename stack_type::const_reference const_reference;
151 
152  typedef boost::indirect_iterator<typename stack_type::const_iterator,
153  typename navigator::value_type,
154  boost::use_default,
155  typename navigator::reference>
157 
158  typedef typename stack_type::const_iterator stack_iterator;
159 
160  typedef typename stack_type::const_reverse_iterator stack_reverse_iterator;
161 
162  typedef boost::indirect_iterator<typename stack_type::const_reverse_iterator,
163  typename navigator::value_type,
164  boost::use_default,
165  typename navigator::reference>
167 
168 private:
169  void pop() { m_stack.pop_back(); }
170 
171 protected:
172  void push(navigator __x) { m_stack.push_back(__x); }
173 
174  void clear() { m_stack.clear(); }
175 
176 
177 public:
178  bool_type empty() const { return m_stack.empty(); }
179  const_reference top() const {
180  PBORI_ASSERT(!empty());
181  return m_stack.back();
182  }
183  idx_type index() const { return *top(); }
184  size_type size() const { return m_stack.size(); }
185 
186  const_iterator begin() const { return stackBegin(); }
187  const_iterator end() const { return stackEnd(); }
188 
189  const_reverse_iterator rbegin() const { return stackRBegin(); }
190 
191  const_reverse_iterator rend() const { return stackREnd(); }
192 
195  PBORI_ASSERT(m_stack.begin() != m_stack.end());
196  return *m_stack.begin();
197  }
198 
200  typedef typename stack_type::value_type top_type;
201 
203  CTermStackBase(): BaseType(), m_stack() { }
204 
206  CTermStackBase(navigator navi): BaseType(), m_stack() {
207  if (navi.isValid())
208  push(navi);
209  }
210 
213  BaseType(rhs), m_stack(rhs.m_stack) { }
214 
216  bool_type equal(const self& rhs) const {
217 
218  if(empty() || rhs.empty())
219  return (empty() && rhs.empty());
220  else
221  return (m_stack == rhs.m_stack);
222  }
223 
224  void incrementThen() {
225  PBORI_ASSERT(!top().isConstant());
226 
227  push(top());
228  m_stack.back().incrementThen();
229  }
230  void incrementElse() {
231  PBORI_ASSERT(!isConstant());
232  m_stack.back().incrementElse();
233  }
234 
235  void decrementNode() {
236  PBORI_ASSERT(!empty());
237  pop();
238  }
239 
241  PBORI_ASSERT(!empty());
242  return top().isConstant();
243  }
244 
246  PBORI_ASSERT(!empty());
247  return top().isTerminated();
248  }
249 
251  PBORI_ASSERT(!empty());
252  return top().isEmpty();
253  }
254 
255  void followThen() {
256  PBORI_ASSERT(!empty());
257  while(!isConstant())
258  incrementThen();
259  }
260 
261  void markOne() {
262  PBORI_ASSERT(empty());
263  push(navigator());
264  }
265 
267  if PBORI_UNLIKELY(empty())
268  return false;
269  else
270  return !m_stack.front().isValid();
271  }
272 
273  void clearOne() {
274  pop();
275  PBORI_ASSERT(empty());
276  }
277 
278  deg_type deg() const {
279  return (markedOne()? 0: (deg_type)size());
280  }
281 
282  void restart(navigator navi) {
283  PBORI_ASSERT(empty());
284  push(navi);
285  }
286 
287  bool isOne() const { return markedOne(); }
288  bool isZero() const { return empty(); }
289 
290  bool atBegin() const { return empty(); }
291 
292  bool atEnd() const { return atEnd(top()); }
293  bool atEnd(navigator navi) const { return navi.isConstant(); }
294 
295  bool validEnd() const { return validEnd(top()); }
296  bool validEnd(navigator navi) const {
297  while(!navi.isConstant()) {
298  navi.incrementElse();
299  }
300  return navi.terminalValue();
301  }
302 
303  void print() const{
304  std::cout <<"(";
305  std::copy(begin(), end(), std::ostream_iterator<int>(std::cout, ", "));
306  std::cout <<")";
307  }
308 
310  if (markedOne())
311  return m_stack.end();
312  else
313  return m_stack.begin();
314  }
315 
317  return m_stack.end();
318  }
319 
321  if (markedOne())
322  return m_stack.rend();
323  else
324  return m_stack.rbegin();
325  }
326 
328  return m_stack.rend();
329  }
330 protected:
331 
332  template <class TermStack>
333  void append(const TermStack& rhs) {
334  PBORI_ASSERT(empty() || rhs.empty() || ((*rhs.begin()) > (*top())) );
335  m_stack.insert(m_stack.end(), rhs.m_stack.begin(), rhs.m_stack.end());
336  }
337 
338 
339 private:
340  stack_type m_stack;
341 
342  navigator m_zero;
343 };
344 
345 
346 
352 template <class NavigatorType, class Category, class BaseType = internal_tag>
354  public CTermStackBase<NavigatorType, BaseType> {
355 
356 public:
359 
362  typedef Category iterator_category;
363 
364  typedef typename base::navigator navigator;
365  typedef typename on_same_type<Category, std::forward_iterator_tag,
369 
371 
372  using base::incrementThen;
373  using base::followThen;
374 
376  CTermStack(): base() { }
377 
379  CTermStack(navigator navi): base(navi) { }
380 
382  CTermStack(const CTermStack& rhs):
383  base(rhs), handleElse(rhs.handleElse) { }
384 
387  template <class Dummy>
388  CTermStack(navigator navi, const Dummy&): base(navi) { }
389 
390  void init() {
391  if (!base::empty()){
392  followThen();
393  terminate();
394  }
395  }
396 
397  void initLast() {
398  if (!base::empty()){
399  followElse();
400  terminate();
401  }
402  }
403 
404  void incrementElse() {
405  handleElse(base::top());
406  base::incrementElse();
407  }
408 
409  void next() {
410 
411  bool invalid = true;
412  while (!base::empty() && invalid) {
413  incrementElse();
414  if ((invalid = base::isInvalid()))
415  base::decrementNode();
416  }
417  }
418 
419  void previous() {
420  previous(Category());
421  }
422 
423 
424  void increment() {
425  PBORI_ASSERT(!base::empty());
426  if PBORI_UNLIKELY(base::markedOne()) {
427  base::clearOne();
428  return;
429  }
430 
431  next();
432  if PBORI_UNLIKELY(!base::empty()) {
433  followThen();
434  terminate();
435  }
436 
437  }
438 
439  void decrement() {
440 
441  if PBORI_UNLIKELY(base::markedOne()) {
442  base::clearOne();
443  }
444  previous();
445  if PBORI_UNLIKELY(!base::empty()){
446  followElse();
447  base::decrementNode();
448  }
449 
450  }
451 
452  void terminate() {
453  PBORI_ASSERT(!base::empty());
454 
455  bool isZero = base::isInvalid();
456  base::decrementNode();
457  if PBORI_UNLIKELY(base::empty() && !isZero)
458  base::markOne();
459  }
460 
461 
462  void followElse() {
463  while( !base::isConstant() ) // if still in interior of a path
464  incrementValidElse();
465  }
466 
468  PBORI_ASSERT(!base::empty() && !base::isConstant());
469  if(!base::top().elseBranch().isEmpty())
470  incrementElse(); // go in direction of last term, if possible
471  else
472  incrementThen();
473  }
474 
475 protected:
476  template <class TermStack>
477  void append(const TermStack& rhs) {
478  base::append(rhs);
479  append(rhs, Category());
480  }
481 
482 private:
483  void previous(std::forward_iterator_tag);
484  void previous(std::bidirectional_iterator_tag);
485 
486  template <class TermStack>
487  void append(const TermStack&, std::forward_iterator_tag){}
488 
489  template <class TermStack>
490  void append(const TermStack& rhs, std::bidirectional_iterator_tag){
491  handleElse.append(rhs.handleElse);
492  }
493 };
494 
495 
496 template <class NavigatorType, class Category, class BaseType>
497 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
498  std::forward_iterator_tag) { }
499 
500 template <class NavigatorType, class Category, class BaseType>
501 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
502  std::bidirectional_iterator_tag) {
503 
504  if(handleElse.empty()) {
505  base::clear();
506  return;
507  }
508 
509  navigator navi = handleElse.top();
510  PBORI_ASSERT(base::empty() || base::top().isValid());
511 
512  while(!base::empty() && (base::index() >= *navi) ) {
513  base::decrementNode();
514  }
515 
516  handleElse.pop();
517  base::push(navi);
518  incrementThen();
519 }
520 
526 template <class NavigatorType, class Category>
528  public CTermStack<NavigatorType, Category> {
529 public:
530  typedef NavigatorType navigator;
532 
535 
538 
541 
544  template <class Dummy>
545  CReverseTermStack(navigator navi, const Dummy&): base(navi) { }
546 
547  void init() { base::initLast(); }
548  void initLast() { base::init(); }
549  void increment() { base::decrement(); }
550  void decrement() { base::increment(); }
551 };
552 
553 template <class NavigatorType, class BlockProperty, class Category, class
554  BaseType = internal_tag>
556 
558 template <class NavigatorType, class Category, class BaseType>
559 class CDegStackCore<NavigatorType, invalid_tag, Category, BaseType>:
560  public CTermStack<NavigatorType, Category, BaseType> {
561 
562 public:
564  typedef NavigatorType navigator;
566 
567  // CDegStackCore(): base(), getDeg(manager_type()) {}
568 
570  base(navi), getDeg(mgr) {}
571 
573  base(rhs), getDeg(rhs.getDeg) {}
574 
575  void gotoEnd() {
576  PBORI_ASSERT(!base::empty());
577  while(!base::isConstant()) {
578  base::incrementElse();
579  }
580  }
581 
583 };
584 
586 template <class NavigatorType, class Category, class BaseType>
587 class CDegStackCore<NavigatorType, valid_tag, Category, BaseType> :
588  public CTermStack<NavigatorType, Category, BaseType> {
589 
590 public:
592  typedef NavigatorType navigator;
593  typedef typename base::idx_type idx_type;
594  typedef typename base::deg_type deg_type;
595  typedef typename base::size_type size_type;
597 
598  // CDegStackCore(): base(), block(manager_type()) {}
600  base(navi), block(mgr) {}
601 
603  base(rhs), block(rhs.block) {}
604 
605  deg_type getDeg(navigator navi) const { return block(navi); }
606 
607  bool atBegin() const {
608  return base::empty() || (base::index() < block.min());
609  }
610 
611  bool atEnd() const { return atEnd(base::top()); }
612  bool atEnd(navigator navi) const {
613  return navi.isConstant() || (*navi >= block.max());
614  }
615 
616  bool validEnd() const{ return validEnd(base::top()); }
617  bool validEnd(navigator navi) const {
618 
619  while(!atEnd(navi))
620  navi.incrementElse();
621 
622  return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
623  }
624 
625  void next() {
626 
627  bool invalid = true;
628  while (!atBegin() && invalid) {
629  PBORI_ASSERT(!base::isConstant());
630  base::incrementElse();
631  if ((invalid = base::isInvalid()))
632  base::decrementNode();
633  }
634  }
635  void previous() {
636 
637  if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
638  while(!atBegin())
639  base::decrementNode();
640  return;
641  }
642  navigator navi = base::handleElse.top();
643  PBORI_ASSERT(base::top().isValid());
644 
645  while(!atBegin() && (base::index() >= *navi) ) {
646  base::decrementNode();
647  }
648 
649  if (base::empty() || (base::index() < *navi)) {
650  base::handleElse.pop();
651  base::push(navi);
652  }
653  base::incrementThen();
654  }
655 
656  void gotoEnd() {
657  PBORI_ASSERT(!base::empty());
658  while( (!base::isConstant()) && (base::index() < block.max()) ) {
659  base::incrementElse();
660  }
661  }
662 
663 protected:
665 };
666 
667 template <class NavigatorType, class BlockProperty, class DescendingProperty,
668  class BaseType = internal_tag>
670 
671 template <class NavigatorType, class BlockProperty, class BaseType>
672 class CDegStackBase<NavigatorType, valid_tag, BlockProperty, BaseType>:
673  public CDegStackCore<NavigatorType, BlockProperty,
674  std::forward_iterator_tag, BaseType> {
675 
676 public:
677  typedef CDegStackCore<NavigatorType, BlockProperty,
678  std::forward_iterator_tag, BaseType> base;
679 
680  typedef typename base::size_type size_type;
681  typedef typename base::deg_type deg_type;
682  typedef std::greater<size_type> size_comparer;
683  typedef typename base::manager_type manager_type;
684 
685  // CDegStackBase(): base() {}
686  CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
687 
688  CDegStackBase(const CDegStackBase& rhs): base(rhs) {}
689 
691 
692  void proximate() { base::next(); }
693 
694  void incrementBranch() { base::incrementThen(); }
695 
696  bool maxOnThen(deg_type deg) const {
697  return (base::getDeg(base::top().thenBranch()) + 1 == deg);
698  }
699 
700 };
701 
702 
703 template <class NavigatorType, class BlockProperty, class BaseType>
704 class CDegStackBase<NavigatorType, invalid_tag, BlockProperty, BaseType>:
705  public CDegStackCore<NavigatorType, BlockProperty,
706  std::bidirectional_iterator_tag, BaseType> {
707 
708 public:
709  typedef CDegStackCore<NavigatorType, BlockProperty,
710  std::bidirectional_iterator_tag, BaseType> base;
711  typedef typename base::size_type size_type;
712  typedef typename base::deg_type deg_type;
713  typedef std::greater_equal<size_type> size_comparer;
714  typedef typename base::manager_type manager_type;
715 
716  // CDegStackBase(): base() {}
717  CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
718 
719  CDegStackBase(const CDegStackBase& rhs): base(rhs) {}
720 
722 
723  void proximate() { base::previous(); }
724 
725  void incrementBranch() { base::incrementValidElse(); }
726 
727  bool maxOnThen(deg_type deg) const {
728  return !(base::getDeg(base::top().elseBranch()) == deg);
729  }
730 };
731 
732 
733 template <class NavigatorType, class DescendingProperty,
734  class BlockProperty = invalid_tag, class BaseType = internal_tag>
736  public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
737 
738 public:
741 
742  typedef typename base::navigator navigator;
743  typedef typename navigator::size_type size_type;
744  typedef typename navigator::deg_type deg_type;
745  typedef typename base::manager_type manager_type;
746 
747  // CDegTermStack(): base(), m_start() {}
749  base(navi, mgr), m_start(navi), m_zero(mgr.zero().navigation()) {}
750 
752  base(rhs), m_start(rhs.m_start), m_zero(rhs.m_zero) {}
753 
754  void init() {
755  if (!base::empty()) {
756  followDeg();
757  base::terminate();
758  }
759  }
760  void followDeg() {
761  PBORI_ASSERT(!base::empty());
762 
763  deg_type deg = base::getDeg(base::top());
764 
765  while (deg > 0) {
766 
767  if ( base::maxOnThen(deg) ) {
768  --deg;
769  base::incrementThen();
770  }
771  else
772  base::incrementElse();
773 
774  }
775  }
776 
777  void increment() {
778  PBORI_ASSERT(!base::empty());
779  if (base::markedOne()) {
780  base::clearOne();
781  return;
782  }
783 
784 
785  size_type upperbound = base::size();
786  degTerm();
787 
788  if(base::empty()) {
789  restart();
790  findTerm(upperbound);
791  }
792  if(!base::empty())
793  base::terminate();
794  }
795 
796 
797  void degTerm() {
798  size_type size = base::size() + 1;
799 
800  PBORI_ASSERT(!base::isConstant());
801  bool doloop;
802  do {
803  PBORI_ASSERT(!base::empty());
804  base::proximate();
805 
806  if (base::atBegin())
807  return;
808 
809  while (!base::atEnd() && (base::size() < size) ) {
810  base::incrementBranch();
811  }
812  base::gotoEnd();
813 
814  if ((doloop = (base::isInvalid() || (base::size() != size)) ) )
815  base::decrementNode();
816 
817  } while (!base::empty() && doloop);
818 
819  }
820 
821 
822  void decrement() {}
823 
824  void findTerm(size_type upperbound) {
825  PBORI_ASSERT(!base::empty());
826 
827  typename base::purestack_type max_elt, current(base::top());
828  base::decrementNode();
829 
830  typename base::size_comparer comp;
831 
832  while (!current.empty() &&
833  (base::takeLast() || (max_elt.size() != upperbound)) ) {
834 
835  while (!base::atEnd(current.top()) && (current.size() < upperbound) )
836  current.incrementThen();
837 
838  if (base::validEnd(current.top())) {
839  if (comp(current.size(), max_elt.size()))
840  max_elt = current;
841  current.decrementNode();
842  }
843  current.next();
844  }
845  base::append(max_elt);
846 
847  if(max_elt.empty())
848  invalidate();
849  }
850 
851  void restart() { base::restart(m_start); }
852 
853  void invalidate() {
854  PBORI_ASSERT(m_zero.isValid());
855  PBORI_ASSERT(m_zero.isEmpty());
856 
857  base::push(m_zero);
858  }
859 
860 private:
861  navigator m_start, m_zero;
862 };
863 
864 
865 
867 template <class NavigatorType, class DescendingProperty, class BaseType = internal_tag>
869  public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
870 
871 public:
874 
875  typedef typename base::navigator navigator;
876  typedef typename navigator::size_type size_type;
877  typedef typename navigator::idx_type idx_type;
879 
882  base(navi, mgr) { }
883 
885  CBlockTermStack(const CBlockTermStack& rhs): base(rhs) { }
886 
887  void init() {
888  if (!base::empty()) {
889  followDeg();
890  base::terminate();
891  }
892  }
893 
894  void increment() {
895  PBORI_ASSERT(!base::empty());
896 
897  if (base::markedOne()) {
898  base::clearOne();
899  return;
900  }
901 
902  navigator current = base::top();
903  while (*current < base::block.min())
904  --base::block;
905 
906  incrementBlock();
907  while ( (base::size() > 1 ) && base::isInvalid() ) {
908  --base::block;
909  base::decrementNode();
910  incrementBlock();
911  }
912 
913  followDeg();
914 
915  PBORI_ASSERT(!base::empty());
916  base::terminate();
917  }
918 
919  void followBlockDeg() { base::followDeg(); }
920 
921  void followDeg() {
922  PBORI_ASSERT(base::top().isValid());
923 
924  if (!base::isConstant() )
925  followBlockDeg();
926 
927  while (!base::isConstant() ) {
928  ++base::block;
929  followBlockDeg();
930  }
931  }
932 
933  void incrementBlock() {
934 
935  PBORI_ASSERT(!base::empty());
936  size_type size = base::size() + 1;
937 
938  if (base::index() < base::block.min()) {
939  base::invalidate();
940  return;
941  }
942 
943  base::degTerm();
944 
945  if (base::size() == size) return;
946 
947  if (base::empty())
948  base::restart();
949  else {
950  PBORI_ASSERT(base::index() < base::block.min());
951  base::incrementThen();
952  }
953 
954  while (!base::isConstant() && (base::index() < base::block.min()))
955  base::incrementElse();
956 
957  PBORI_ASSERT(size > base::size());
958 
959  base::findTerm(size - base::size());
960  base::gotoEnd();
961  }
962 };
963 
965 
966 #endif