PolyBoRi
BoolePolynomial.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
319 //*****************************************************************************
320 
321 #ifndef BoolePolynomial_h_
322 #define BoolePolynomial_h_
323 
324 // include standard definitions
325 #include <vector>
326 
327 // get standard map functionality
328 #include <map>
329 
330 // get standard algorithmic functionalites
331 #include <algorithm>
332 
333 #include "BooleRing.h"
334 // include basic definitions and decision diagram interface
335 #include "CDDInterface.h"
336 
337 // include definition of sets of Boolean variables
338 #include "CTermIter.h"
339 #include "CBidirectTermIter.h"
340 
341 #include "pbori_func.h"
342 #include "pbori_tags.h"
343 #include "BooleSet.h"
344 
345 #include "CTermIter.h"
346 #include "BooleConstant.h"
347 
349 
350 
351 // forward declarations
352 class LexOrder;
353 class DegLexOrder;
354 class DegRevLexAscOrder;
355 class BlockDegLexOrder;
356 class BlockDegRevLexAscOrder;
357 
358 class BooleMonomial;
359 class BooleVariable;
360 class BooleExponent;
361 
362 
363 template <class IteratorType, class MonomType>
364 class CIndirectIter;
365 
366 template <class IteratorType, class MonomType>
367 class COrderedIter;
368 
369 
370 //template<class, class, class, class> class CGenericIter;
371 template<class, class, class, class> class CDelayedTermIter;
372 
373 template<class OrderType, class NavigatorType, class MonomType>
374 class CGenericIter;
375 
376 template<class OrderType, class NavigatorType, class MonomType>
377 class MyCGenericIter;
378 
379 
380 template<class NavigatorType, class ExpType>
381 class CExpIter;
382 
383 
389 class BoolePolynomial;
390 BoolePolynomial
391 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);
392 
394 
395 public:
396 
398  friend class BooleMonomial;
399 
400  //-------------------------------------------------------------------------
401  // types definitions
402  //-------------------------------------------------------------------------
403 
405  typedef BoolePolynomial self;
406 
408 
419 
422 
425 
428 
431 
433 
436 
439 
442 
445 
448 
450  typedef
454 
456  typedef
460 
461 
462 
464  // typedef COrderedIter<exp_type> ordered_exp_iterator;
465  typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
466 
468  // typedef COrderedIter<monom_type> ordered_iterator;
469  typedef COrderedIter<navigator, monom_type> ordered_iterator;
470 
472 
473  typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
475  typedef CGenericIter<DegLexOrder, navigator, monom_type> dlex_iterator;
476  typedef CGenericIter<DegRevLexAscOrder, navigator, monom_type>
478 
479  typedef CGenericIter<BlockDegLexOrder, navigator, monom_type>
481  typedef CGenericIter<BlockDegRevLexAscOrder, navigator, monom_type>
483 
484  typedef CGenericIter<LexOrder, navigator, exp_type> lex_exp_iterator;
485  typedef CGenericIter<DegLexOrder, navigator, exp_type> dlex_exp_iterator;
486  typedef CGenericIter<DegRevLexAscOrder, navigator, exp_type>
488  typedef CGenericIter<BlockDegLexOrder, navigator, exp_type>
490  typedef CGenericIter<BlockDegRevLexAscOrder, navigator, exp_type>
493 
496 
499 
501  typedef CGenericIter<LexOrder, navigator, size_type> deg_iterator;
502 
504  typedef std::vector<monom_type> termlist_type;
505 
508 
511 
513  typedef std::map<self, idx_type, symmetric_composition<
514  std::less<navigator>, navigates<self> > > idx_map_type;
515  typedef std::map<self, std::vector<self>, symmetric_composition<
516  std::less<navigator>, navigates<self> > > poly_vec_map_type;
517 
518  //-------------------------------------------------------------------------
519  // constructors and destructor
520  //-------------------------------------------------------------------------
521 
523  BoolePolynomial();
524 
526  explicit BoolePolynomial(constant_type);
527 
530  m_dd(isOne? ring.one(): ring.zero() ) { }
531 
533  BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
534 
536  BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
537 
539  BoolePolynomial(const exp_type&, const ring_type&);
540 
542  BoolePolynomial(const navigator& rhs, const ring_type& ring):
543  m_dd(ring.manager().manager(), rhs) {
544  assert(rhs.isValid());
545  }
546 
549 
550  //-------------------------------------------------------------------------
551  // operators and member functions
552  //-------------------------------------------------------------------------
553 
554  // self& operator=(const self& rhs) {
555  // return m_dd = rhs.m_dd;
556  // }
557 
558  self& operator=(constant_type rhs) {
559  return (*this) = self(rhs);//rhs.generate(*this);
560  }
562 
563  const self& operator-() const { return *this; }
564  self& operator+=(const self&);
566 
567  //return *this = (self(*this) + (rhs).generate(*this));
568  if (rhs) (*this) = (*this + ring().one());
569  return *this;
570  }
571  template <class RHSType>
572  self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
573  self& operator*=(const monom_type&);
574  self& operator*=(const exp_type&);
575  self& operator*=(const self&);
577  if (!rhs) *this = ring().zero();
578  return *this;
579  }
580  self& operator/=(const monom_type&);
581  self& operator/=(const exp_type&);
582  self& operator/=(const self& rhs);
583  self& operator/=(constant_type rhs);
584  self& operator%=(const monom_type&);
585  self& operator%=(const self& rhs) {
586  return (*this) -= (self(rhs) *= (self(*this) /= rhs));
587  }
588  self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }
590 
592 
593  bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
594  bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
596  return ( rhs? isOne(): isZero() );
597  }
599  return ( rhs? (!(isZero())): (!(isOne())) );
600  }
602 
604  bool_type isZero() const { return m_dd.emptiness(); }
605 
607  bool_type isOne() const { return m_dd.blankness(); }
608 
610  bool_type isConstant() const { return m_dd.isConstant(); }
611 
613  bool_type hasConstantPart() const { return m_dd.ownsOne(); }
614 
616  bool_type reducibleBy(const self&) const;
617 
619  monom_type lead() const;
620 
622  monom_type lexLead() const;
623 
625  monom_type boundedLead(size_type bound) const;
626 
628  exp_type leadExp() const;
629 
631  exp_type boundedLeadExp(size_type bound) const;
632 
634  set_type lmDivisors() const { return leadFirst().firstDivisors(); };
635 
637  hash_type hash() const { return m_dd.hash(); }
638 
640  hash_type stableHash() const { return m_dd.stableHash(); }
641 
643  hash_type lmStableHash() const;
644 
646  size_type deg() const;
647 
649  size_type lmDeg() const;
650 
652  size_type lexLmDeg() const;
653 
655  size_type totalDeg() const;
656 
658  size_type lmTotalDeg() const;
659 
661  self gradedPart(size_type deg) const;
662 
664  size_type nNodes() const;
665 
667  size_type nUsedVariables() const;
668 
670  monom_type usedVariables() const;
671 
673  exp_type usedVariablesExp() const;
674 
676  size_type length() const;
677 
679  ostream_type& print(ostream_type&) const;
680 
682  void prettyPrint() const;
683 
685  void prettyPrint(const char* filename) const;
686 
688  const_iterator begin() const;
689 
691  const_iterator end() const;
692 
694  exp_iterator expBegin() const;
695 
697  exp_iterator expEnd() const;
698 
700  first_iterator firstBegin() const;
701 
703  first_iterator firstEnd() const;
704 
706  monom_type firstTerm() const;
707 
709  deg_iterator degBegin() const;
710 
712  deg_iterator degEnd() const;
713 
715  ordered_iterator orderedBegin() const;
716 
718  ordered_iterator orderedEnd() const;
719 
721  ordered_exp_iterator orderedExpBegin() const;
722 
724  ordered_exp_iterator orderedExpEnd() const;
725 
727 
728  lex_iterator genericBegin(lex_tag) const;
729  lex_iterator genericEnd(lex_tag) const;
730  dlex_iterator genericBegin(dlex_tag) const;
731  dlex_iterator genericEnd(dlex_tag) const;
732  dp_asc_iterator genericBegin(dp_asc_tag) const;
733  dp_asc_iterator genericEnd(dp_asc_tag) const;
734  block_dlex_iterator genericBegin(block_dlex_tag) const;
735  block_dlex_iterator genericEnd(block_dlex_tag) const;
736  block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
737  block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;
738 
739 
740  lex_exp_iterator genericExpBegin(lex_tag) const;
741  lex_exp_iterator genericExpEnd(lex_tag) const;
742  dlex_exp_iterator genericExpBegin(dlex_tag) const;
743  dlex_exp_iterator genericExpEnd(dlex_tag) const;
744  dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
745  dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
746  block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
747  block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
748  block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
749  block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;
751 
753  navigator navigation() const { return m_dd.navigation(); }
754 
756  navigator endOfNavigation() const { return navigator(); }
757 
759  dd_type copyDiagram(){ return diagram(); }
760 
762  operator set_type() const { return set(); };
763 
764  size_type eliminationLength() const;
765  size_type eliminationLengthWithDegBound(size_type garantied_deg_bound) const;
767  void fetchTerms(termlist_type&) const;
768 
770  termlist_type terms() const;
771 
773  const dd_type& diagram() const { return m_dd; }
774 
776  set_type set() const { return m_dd; }
777 
779  bool_type isSingleton() const { return dd_is_singleton(navigation()); }
780 
783  return dd_is_singleton_or_pair(navigation());
784  }
785 
787  bool_type isPair() const { return dd_is_pair(navigation()); }
788 
790  ring_type ring() const { return ring_type(m_dd.manager()); }
791 
792 protected:
793 
795  dd_type& internalDiagram() { return m_dd; }
796 
798  self leadFirst() const;
799 
801  set_type firstDivisors() const;
802 
803 
804 private:
806  dd_type m_dd;
807 };
808 
809 
811 inline BoolePolynomial
812 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
813 
814  return BoolePolynomial(lhs) += rhs;
815 }
817 inline BoolePolynomial
819  return BoolePolynomial(lhs) += (rhs);
820  //return BoolePolynomial(lhs) += BoolePolynomial(rhs);
821 }
822 
824 inline BoolePolynomial
826 
827  return BoolePolynomial(rhs) += (lhs);
828 }
829 
830 
832 template <class RHSType>
833 inline BoolePolynomial
834 operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
835 
836  return BoolePolynomial(lhs) -= rhs;
837 }
839 inline BoolePolynomial
840 operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
841 
842  return -(BoolePolynomial(rhs) -= lhs);
843 }
844 
845 
847 #define PBORI_RHS_MULT(type) inline BoolePolynomial \
848 operator*(const BoolePolynomial& lhs, const type& rhs) { \
849  return BoolePolynomial(lhs) *= rhs; }
850 
855 
856 
857 #undef PBORI_RHS_MULT
858 
860 #define PBORI_LHS_MULT(type) inline BoolePolynomial \
861 operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
862 
866 
867 #undef PBORI_LHS_MULT
868 
869 
871 template <class RHSType>
872 inline BoolePolynomial
873 operator/(const BoolePolynomial& lhs, const RHSType& rhs){
874  return BoolePolynomial(lhs) /= rhs;
875 }
876 
878 template <class RHSType>
879 inline BoolePolynomial
880 operator%(const BoolePolynomial& lhs, const RHSType& rhs){
881 
882  return BoolePolynomial(lhs) %= rhs;
883 }
884 
886 inline BoolePolynomial::bool_type
888 
889  return (rhs == lhs);
890 }
891 
893 inline BoolePolynomial::bool_type
895 
896  return (rhs != lhs);
897 }
898 
900 BoolePolynomial::ostream_type&
901 operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);
902 
903 // tests whether polynomial can be reduced by rhs
904 inline BoolePolynomial::bool_type
905 BoolePolynomial::reducibleBy(const self& rhs) const {
906 
907  PBORI_TRACE_FUNC( "BoolePolynomial::reducibleBy(const self&) const" );
908 
909  if( rhs.isOne() )
910  return true;
911 
912  if( isZero() )
913  return rhs.isZero();
914 
915  return std::includes(firstBegin(), firstEnd(),
916  rhs.firstBegin(), rhs.firstEnd());
917 
918 }
919 
920 
922 
923 #endif // of BoolePolynomial_h_