PolyBoRi
CTermStack.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
99 //*****************************************************************************
100 
101 // get standard header
102 #include <stack>
103 #include <iterator>
104 #include <utility> // for std::pair
105 
106 // include basic definitions
107 #include "pbori_defs.h"
108 
109 // include polybori functionals
110 #include "pbori_func.h"
111 
112 // include polybori properties
113 #include "pbori_traits.h"
114 
115 #include "pbori_routines.h"
116 
117 // include boost's indirect iterator facilities
118 #include <boost/iterator/indirect_iterator.hpp>
119 
120 #include "BooleEnv.h"
121 #include "CDegreeCache.h"
122 #include "CBidirectTermIter.h"
123 
124 
125 
126 #ifndef CTermStack_h_
127 #define CTermStack_h_
128 
130 
132 template<class NavigatorType>
133 struct cached_deg {
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) {}
137 
138  typename NavigatorType::size_type
139  operator()(NavigatorType navi) const {
140  return dd_cached_degree(m_deg_cache, navi);
141  }
142  cache_type m_deg_cache;
143 };
144 
146 
147 template <class NavigatorType>
148 class cached_block_deg {
149 public:
150  typedef typename NavigatorType::idx_type idx_type;
151 
152  typedef cached_block_deg<NavigatorType> self;
153 
155  typedef std::vector<idx_type> block_idx_type;
156 
158  typedef typename block_idx_type::const_iterator block_iterator;
159  typedef CBlockDegreeCache<CCacheTypes::block_degree, CTypes::dd_type>
160  cache_type;
161  typedef typename cache_type::manager_type manager_type;
162 
163  cached_block_deg(const manager_type& mgr):
164  // m_indices(BoolePolyRing::blockRingBegin()),
165  m_current_block(BooleEnv::blockBegin()),
166  m_deg_cache(mgr) { }
167 
168  typename NavigatorType::size_type
169  operator()(NavigatorType navi) const {
170  return dd_cached_block_degree(m_deg_cache, navi, max());
171  }
172 
173  idx_type min() const {
174  assert(*m_current_block != 0); // assuming first element to be zero
175  return *(m_current_block - 1);
176  }
177 
178  idx_type max() const {
179  return *m_current_block;
180  }
181  self& operator++(){
182  assert(max() != CTypes::max_idx);
183  ++m_current_block;
184  return *this;
185  }
186 
187  self& operator--(){
188  assert(min() != 0);
189  --m_current_block;
190  return *this;
191  }
192 
193 private:
194  // block_iterator m_indices;
195  block_iterator m_current_block;
196 
197  cache_type m_deg_cache;
198 };
199 
200 
201 
202 
210 template <class NavigatorType, class BaseType = internal_tag>
211 class CTermStackBase:
212  public BaseType {
213 
214 public:
215 
216  template <class, class> friend class CTermStackBase;
217 
218  typedef CTermStackBase<NavigatorType, BaseType> self;
219 
221  typedef NavigatorType navigator;
223  typedef typename navigator::idx_type idx_type;
224 
226  typedef typename navigator::size_type size_type;
227  typedef typename navigator::bool_type bool_type;
228 
229 
231  typedef std::deque<navigator> stack_type;
232 
233  typedef typename stack_type::reference reference;
234  typedef typename stack_type::const_reference const_reference;
235 
236  typedef boost::indirect_iterator<typename stack_type::const_iterator,
237  typename navigator::value_type,
238  boost::use_default,
239  typename navigator::reference>
240  const_iterator;
241 
242  typedef typename stack_type::const_iterator stack_iterator;
243 
244  typedef typename stack_type::const_reverse_iterator stack_reverse_iterator;
245 
246  typedef boost::indirect_iterator<typename stack_type::const_reverse_iterator,
247  typename navigator::value_type,
248  boost::use_default,
249  typename navigator::reference>
250  const_reverse_iterator;
251 
252 private:
253  void pop() { m_stack.pop_back(); }
254 
255 protected:
256  void push(navigator __x) { m_stack.push_back(__x); }
257 
258  void clear() { m_stack.clear(); }
259 
260  // reference top() { return m_stack.back(); }
261 
262 public:
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(); }
267 
268  const_iterator begin() const { return stackBegin(); }
269  const_iterator end() const { return stackEnd(); }
270 
271  const_reverse_iterator rbegin() const { return stackRBegin(); }
272 
273  const_reverse_iterator rend() const { return stackREnd(); }
274 
276  navigator navigation() const {
277  assert(m_stack.begin() != m_stack.end());
278  return *m_stack.begin();
279  }
280 
282  typedef typename stack_type::value_type top_type;
283 
285  CTermStackBase(): BaseType(), m_stack() { }
286 
288  CTermStackBase(navigator navi): BaseType(), m_stack() {
289  push(navi);
290  }
291 
293 
294 
296  bool_type equal(const self& rhs) const {
297 
298  if(empty() || rhs.empty())
299  return (empty() && rhs.empty());
300  else
301  return (m_stack == rhs.m_stack);
302  }
303 
304  void incrementThen() {
305  assert(!top().isConstant());
306 
307  push(top());
308  m_stack.back().incrementThen();
309  }
310  void incrementElse() {
311  assert(!isConstant());
312  m_stack.back().incrementElse();
313  }
314 
315  void decrementNode() {
316  assert(!empty());
317  pop();
318  }
319 
320  bool_type isConstant() const {
321  assert(!empty());
322  return top().isConstant();
323  }
324 
325  bool_type isTerminated() const {
326  assert(!empty());
327  return top().isTerminated();
328  }
329 
330  bool_type isInvalid() const {
331  assert(!empty());
332  return top().isEmpty();
333  }
334 
335  void followThen() {
336  assert(!empty());
337  while(!isConstant())
338  incrementThen();
339  }
340 
341  void markOne() {
342  assert(empty());
343  push(navigator());
344  }
345 
346  bool_type markedOne() const {
347  if (empty())
348  return false;
349  else
350  return !m_stack.front().isValid();
351  }
352 
353  void clearOne() {
354  pop();
355  assert(empty());
356  }
357 
358  size_type deg() const {
359  return (markedOne()? 0: size());
360  }
361 
362  void invalidate() {
363  push(BooleEnv::zero().navigation());
364  }
365 
366  void restart(navigator navi) {
367  assert(empty());
368  push(navi);
369  }
370 
371  bool isOne() const { return markedOne(); }
372  bool isZero() const { return empty(); }
373 
374  bool atBegin() const { return empty(); }
375 
376  bool atEnd() const { return atEnd(top()); }
377  bool atEnd(navigator navi) const { return navi.isConstant(); }
378 
379  bool validEnd() const { return validEnd(top()); }
380  bool validEnd(navigator navi) const {
381  while(!navi.isConstant()) {
382  navi.incrementElse();
383  }
384  return navi.terminalValue();
385  }
386 
387  void print() const{
388  std::cout <<"(";
389  std::copy(begin(), end(), std::ostream_iterator<int>(cout, ", "));
390  std::cout <<")";
391  }
392 
393  stack_iterator stackBegin() const {
394  if (markedOne())
395  return m_stack.end();
396  else
397  return m_stack.begin();
398  }
399 
400  stack_iterator stackEnd() const {
401  return m_stack.end();
402  }
403 
404  stack_reverse_iterator stackRBegin() const {
405  if (markedOne())
406  return m_stack.rend();
407  else
408  return m_stack.rbegin();
409  }
410 
411  stack_reverse_iterator stackREnd() const {
412  return m_stack.rend();
413  }
414 protected:
415 
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());
420  }
421 
422 
423 private:
424  stack_type m_stack;
425 };
426 
427 
428 
429 
430 template <class NavigatorType, class Category, class BaseType = internal_tag>
431 class CTermStack:
432  public CTermStackBase<NavigatorType, BaseType> {
433 
434 public:
435  typedef CTermStackBase<NavigatorType, BaseType> base;
436  typedef CTermStack<NavigatorType, Category, BaseType> self;
437 
439  typedef CTermStack<NavigatorType, Category, internal_tag> purestack_type;
440  typedef Category iterator_category;
441 
442  typedef typename base::navigator navigator;
443  typedef typename on_same_type<Category, std::forward_iterator_tag,
445  handle_else<NavigatorType> >::type
446  else_handler;
447 
448  else_handler handleElse;
449 
450  using base::incrementThen;
451  using base::followThen;
452 
454  CTermStack(): base() { }
455 
457  CTermStack(navigator navi): base(navi) { }
458 
461  template <class Dummy>
462  CTermStack(navigator navi, const Dummy&): base(navi) { }
463 
464  void init() {
465  followThen();
466  terminate();
467  }
468 
469  void initLast() {
470  followElse();
471  terminate();
472  }
473 
474  void incrementElse() {
475  assert(!base::empty());
476  handleElse(base::top());
477  base::incrementElse();
478  }
479 
480  void next() {
481 
482  bool invalid = true;
483  while (!base::empty() && invalid) {
484  incrementElse();
485  if (invalid = base::isInvalid())
486  base::decrementNode();
487  }
488  }
489 
490  void previous() {
491  previous(Category());
492  }
493 
494 
495  void increment() {
496  assert(!base::empty());
497  if (base::markedOne()) {
498  base::clearOne();
499  return;
500  }
501 
502  next();
503  if (!base::empty()) {
504  followThen();
505  terminate();
506  }
507 
508  }
509 
510  void decrement() {
511 
512  if (base::markedOne()) {
513  base::clearOne();
514  }
515 
516  previous();
517  followElse();
518  base::decrementNode();
519 
520  }
521 
522  void terminate() {
523  assert(!base::empty());
524 
525  bool isZero = base::isInvalid();
526  base::decrementNode();
527  if (base::empty() && !isZero)
528  base::markOne();
529  }
530 
531 
532  void followElse() {
533  while( !base::isConstant() ) // if still in interior of a path
534  incrementValidElse();
535  }
536 
537  void incrementValidElse() {
538  assert(!base::empty() && !base::isConstant());
539  if(!base::top().elseBranch().isEmpty())
540  incrementElse(); // go in direction of last term, if possible
541  else
542  incrementThen();
543  }
544 protected:
545  template <class TermStack>
546  void append(const TermStack& rhs) {
547  base::append(rhs);
548  append(rhs, Category());
549  }
550 
551 private:
552  void previous(std::forward_iterator_tag);
553  void previous(std::bidirectional_iterator_tag);
554 
555  template <class TermStack>
556  void append(const TermStack&, std::forward_iterator_tag){}
557 
558  template <class TermStack>
559  void append(const TermStack& rhs, std::bidirectional_iterator_tag){
560  handleElse.append(rhs.handleElse);
561  }
562 };
563 
564 
565 template <class NavigatorType, class Category, class BaseType>
566 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
567  std::forward_iterator_tag) { }
568 
569 template <class NavigatorType, class Category, class BaseType>
570 inline void CTermStack<NavigatorType, Category, BaseType>::previous(
571  std::bidirectional_iterator_tag) {
572 
573  if(handleElse.empty()) {
574  base::clear();
575  return;
576  }
577 
578  navigator navi = handleElse.top();
579 
580  assert(base::top().isValid());
581 
582  while(!base::empty() && (base::index() >= *navi) ) {
583  base::decrementNode();
584  }
585 
586  handleElse.pop();
587  base::push(navi);
588  incrementThen();
589 }
590 
591 
592 template <class NavigatorType, class BlockProperty, class Category, class
593  BaseType = internal_tag>
594 class CDegStackCore;
595 
597 template <class NavigatorType, class Category, class BaseType>
598 class CDegStackCore<NavigatorType, invalid_tag, Category, BaseType>:
599  public CTermStack<NavigatorType, Category, BaseType> {
600 
601 public:
602  typedef CTermStack<NavigatorType, Category, BaseType> base;
603  typedef NavigatorType navigator;
604  typedef typename cached_deg<navigator>::manager_type manager_type;
605 
606  CDegStackCore(): base(), getDeg(typename manager_type::mgrcore_ptr()) {}
607 
608  CDegStackCore(navigator navi, const manager_type& mgr):
609  base(navi), getDeg(mgr) {}
610 
611 
612  void gotoEnd() {
613  assert(!base::empty());
614  while(!base::isConstant()) {
615  base::incrementElse();
616  }
617  }
618 
619  cached_deg<navigator> getDeg;
620 };
621 
623 template <class NavigatorType, class Category, class BaseType>
624 class CDegStackCore<NavigatorType, valid_tag, Category, BaseType> :
625  public CTermStack<NavigatorType, Category, BaseType> {
626 
627 public:
628  typedef CTermStack<NavigatorType, Category, BaseType> base;
629  typedef NavigatorType navigator;
630  typedef typename base::idx_type idx_type;
631  typedef typename base::size_type size_type;
632  typedef typename cached_block_deg<navigator>::manager_type manager_type;
633 
634  CDegStackCore(): base(), block(typename manager_type::mgrcore_ptr()) {}
635  CDegStackCore(navigator navi, const manager_type& mgr):
636  base(navi), block(mgr) {}
637 
638  size_type getDeg(navigator navi) const { return block(navi); }
639 
640  bool atBegin() const {
641  return base::empty() || (base::index() < block.min());
642  }
643 
644  bool atEnd() const { return atEnd(base::top()); }
645  bool atEnd(navigator navi) const {
646  return navi.isConstant() || (*navi >= block.max());
647  }
648 
649  bool validEnd() const{ return validEnd(base::top()); }
650  bool validEnd(navigator navi) const {
651 
652  while(!atEnd(navi))
653  navi.incrementElse();
654 
655  return (navi.isConstant()? navi.terminalValue(): *navi >= block.max());
656  }
657 
658  void next() {
659 
660  bool invalid = true;
661  while (!atBegin() && invalid) {
662  assert(!base::isConstant());
663  base::incrementElse();
664  if (invalid = base::isInvalid())
665  base::decrementNode();
666  }
667  }
668  void previous() {
669 
670  if( base::handleElse.empty() || (*base::handleElse.top() < block.min()) ) {
671  while(!atBegin())
672  base::decrementNode();
673  return;
674  }
675  navigator navi = base::handleElse.top();
676  assert(base::top().isValid());
677 
678  while(!atBegin() && (base::index() >= *navi) ) {
679  base::decrementNode();
680  }
681 
682  if (base::empty() || (base::index() < *navi)) {
683  base::handleElse.pop();
684  base::push(navi);
685  }
686  base::incrementThen();
687  }
688 
689  void gotoEnd() {
690  assert(!base::empty());
691  while( (!base::isConstant()) && (base::index() < block.max()) ) {
692  base::incrementElse();
693  }
694  }
695 
696 protected:
697  cached_block_deg<navigator> block;
698 };
699 
700 template <class NavigatorType, class BlockProperty, class DescendingProperty,
701  class BaseType = internal_tag>
702 class CDegStackBase;
703 
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> {
708 
709 public:
710  typedef CDegStackCore<NavigatorType, BlockProperty,
711  std::forward_iterator_tag, BaseType> base;
712 
713  typedef typename base::size_type size_type;
714  typedef std::greater<size_type> size_comparer;
715  typedef typename base::manager_type manager_type;
716 
717  CDegStackBase(): base() {}
718  CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
719 
720  integral_constant<bool, false> takeLast;
721 
722  void proximate() { base::next(); }
723 
724  void incrementBranch() { base::incrementThen(); }
725 
726  bool maxOnThen(size_type deg) const {
727  return (base::getDeg(base::top().thenBranch()) + 1 == deg);
728  }
729 
730 };
731 
732 
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> {
737 
738 public:
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;
744 
745  CDegStackBase(): base() {}
746  CDegStackBase(NavigatorType navi, const manager_type& mgr): base(navi, mgr) {}
747 
748  integral_constant<bool, true> takeLast;
749 
750  void proximate() { base::previous(); }
751 
752  void incrementBranch() { base::incrementValidElse(); }
753 
754  bool maxOnThen(size_type deg) const {
755  return !(base::getDeg(base::top().elseBranch()) == deg);
756  }
757 };
758 
759 
760 template <class NavigatorType, class DescendingProperty,
761  class BlockProperty = invalid_tag, class BaseType = internal_tag>
762 class CDegTermStack:
763  public CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> {
764 
765 public:
766  typedef CDegStackBase<NavigatorType, DescendingProperty, BlockProperty, BaseType> base;
767  typedef CDegTermStack<NavigatorType, DescendingProperty, BlockProperty, BaseType> self;
768 
769  typedef typename base::navigator navigator;
770  typedef typename navigator::size_type size_type;
771  typedef typename base::manager_type manager_type;
772 
773  CDegTermStack(): base(), m_start() {}
774  CDegTermStack(navigator navi, const manager_type& mgr):
775  base(navi, mgr), m_start(navi) {}
776 
777  void init() {
778  followDeg();
779  base::terminate();
780  }
781  void followDeg() {
782  assert(!base::empty());
783 
784  size_type deg = base::getDeg(base::top());
785 
786  while (deg > 0) {
787 
788  if ( base::maxOnThen(deg) ) {
789  --deg;
790  base::incrementThen();
791  }
792  else
793  base::incrementElse();
794 
795  }
796  }
797 
798  void increment() {
799  assert(!base::empty());
800  if (base::markedOne()) {
801  base::clearOne();
802  return;
803  }
804 
805 
806  size_type upperbound = base::size();
807  degTerm();
808 
809  if(base::empty()) {
810  restart();
811  findTerm(upperbound);
812  }
813  if(!base::empty())
814  base::terminate();
815  }
816 
817 
818  void degTerm() {
819  size_type size = base::size() + 1;
820 
821  assert(!base::isConstant());
822  bool doloop;
823  do {
824  assert(!base::empty());
825  base::proximate();
826 
827  if (base::atBegin())
828  return;
829 
830  while (!base::atEnd() && (base::size() < size) ) {
831  base::incrementBranch();
832  }
833  base::gotoEnd();
834 
835  if (doloop = (base::isInvalid() || (base::size() != size)) )
836  base::decrementNode();
837 
838  } while (!base::empty() && doloop);
839 
840  }
841 
842 
843  void decrement() {}
844 
845  void findTerm(size_type upperbound) {
846  assert(!base::empty());
847 
848  typename base::purestack_type max_elt, current(base::top());
849  base::decrementNode();
850 
851  typename base::size_comparer comp;
852 
853  while (!current.empty() &&
854  (base::takeLast() || (max_elt.size() != upperbound)) ) {
855 
856  while (!base::atEnd(current.top()) && (current.size() < upperbound) )
857  current.incrementThen();
858 
859  if (base::validEnd(current.top())) {
860  if (comp(current.size(), max_elt.size()))
861  max_elt = current;
862  current.decrementNode();
863  }
864  current.next();
865  }
866  base::append(max_elt);
867 
868  if(max_elt.empty())
869  base::invalidate();
870  }
871 
872  void restart() { base::restart(m_start); }
873 
874 private:
875  navigator m_start;
876 };
877 
878 
879 
881 template <class NavigatorType, class DescendingProperty, class BaseType = internal_tag>
882 class CBlockTermStack:
883  public CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> {
884 
885 public:
886  typedef CDegTermStack<NavigatorType, DescendingProperty, valid_tag, BaseType> base;
887  typedef CBlockTermStack<NavigatorType, DescendingProperty, BaseType> self;
888 
889  typedef typename base::navigator navigator;
890  typedef typename navigator::size_type size_type;
891  typedef typename navigator::idx_type idx_type;
892  typedef typename base::manager_type manager_type;
893 
895  CBlockTermStack(navigator navi, const manager_type& mgr):
896  base(navi, mgr) { }
897 
899  CBlockTermStack(): base() {}
900 
901 
902  void init() {
903  assert(!base::empty());
904  followDeg();
905  base::terminate();
906  }
907 
908  void increment() {
909  assert(!base::empty());
910 
911  if (base::markedOne()) {
912  base::clearOne();
913  return;
914  }
915 
916  navigator current = base::top();
917  while (*current < base::block.min())
918  --base::block;
919 
920  incrementBlock();
921  while ( (base::size() > 1 ) && base::isInvalid() ) {
922  --base::block;
923  base::decrementNode();
924  incrementBlock();
925  }
926 
927  followDeg();
928 
929  assert(!base::empty());
930  base::terminate();
931  }
932 
933  void followBlockDeg() { base::followDeg(); }
934 
935  void followDeg() {
936  assert(base::top().isValid());
937 
938  if (!base::isConstant() )
939  followBlockDeg();
940 
941  while (!base::isConstant() ) {
942  ++base::block;
943  followBlockDeg();
944  }
945  }
946 
947  void incrementBlock() {
948 
949  assert(!base::empty());
950  size_type size = base::size() + 1;
951 
952  if (base::index() < base::block.min()) {
953  base::invalidate();
954  return;
955  }
956 
957  base::degTerm();
958 
959  if (base::size() == size) return;
960 
961  if (base::empty())
962  base::restart();
963  else {
964  assert(base::index() < base::block.min());
965  base::incrementThen();
966  }
967 
968  while (!base::isConstant() && (base::index() < base::block.min()))
969  base::incrementElse();
970 
971  assert(size > base::size());
972 
973  base::findTerm(size - base::size());
974  base::gotoEnd();
975  }
976 };
977 
979 
980 #endif