PolyBoRi
BoolePolynomial.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00016 //*****************************************************************************
00017 
00018 #ifndef polybori_BoolePolynomial_h_
00019 #define polybori_BoolePolynomial_h_
00020 
00021 // include standard definitions
00022 #include <vector>
00023 
00024 // get standard map functionality
00025 #include <map>
00026 
00027 // get standard algorithmic functionalites
00028 #include <algorithm>
00029 
00030 #include <polybori/BoolePolyRing.h>
00031 
00032 // include definition of sets of Boolean variables
00033 
00034 #include <polybori/routines/pbori_func.h>
00035 #include <polybori/common/tags.h>
00036 #include <polybori/BooleSet.h>
00037 
00038 #include <polybori/iterators/CTermIter.h>
00039 #include <polybori/iterators/CGenericIter.h>
00040 #include <polybori/iterators/CBidirectTermIter.h>
00041 
00042 #include <polybori/BooleConstant.h>
00043 
00044 BEGIN_NAMESPACE_PBORI
00045 
00046 
00047 // forward declarations
00048 class LexOrder;
00049 class DegLexOrder;
00050 class DegRevLexAscOrder;
00051 class BlockDegLexOrder;
00052 class BlockDegRevLexAscOrder;
00053 
00054 class BooleMonomial;
00055 class BooleVariable;
00056 class BooleExponent;
00057 
00058 
00059 template <class IteratorType, class MonomType>
00060 class CIndirectIter;
00061 
00062 template <class IteratorType, class MonomType>
00063 class COrderedIter;
00064 
00065 
00066 //template<class, class, class, class> class CGenericIter;
00067 template<class, class, class, class> class CDelayedTermIter;
00068 
00069 template<class OrderType, class NavigatorType, class MonomType>
00070 class CGenericIter;
00071 
00072 template<class NavigatorType, class ExpType>
00073 class CExpIter;
00074 
00075 
00081 class BoolePolynomial;
00082 BoolePolynomial 
00083 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);
00084 
00085 class BoolePolynomial:
00086   public CAuxTypes{
00087 
00088 public:
00089 
00091   friend class BooleMonomial;
00092 
00093   //-------------------------------------------------------------------------
00094   // types definitions
00095   //-------------------------------------------------------------------------
00096 
00098   typedef BoolePolynomial self;
00099 
00101 
00102   typedef BooleSet dd_type;
00103   typedef CTypes::ostream_type ostream_type;
00105 
00107   typedef dd_type::first_iterator first_iterator;
00108 
00110   typedef dd_type::navigator navigator;
00111 
00113 
00115   typedef BooleMonomial monom_type; 
00116 
00118   typedef BooleVariable var_type; 
00119 
00121   typedef BooleExponent exp_type; 
00122 
00124   typedef BooleConstant constant_type;
00125 
00127   typedef BoolePolyRing ring_type;
00128 
00130   typedef CTypes::comp_type comp_type;
00131 
00133   typedef 
00134   binary_composition< std::plus<size_type>, 
00135                       project_ith<1>, integral_constant<size_type, 1> > 
00136   increment_type;
00137 
00139   typedef 
00140   binary_composition< std::minus<size_type>, 
00141                       project_ith<1>, integral_constant<size_type, 1> > 
00142   decrement_type;
00143 
00144 
00145 
00147   //  typedef COrderedIter<exp_type> ordered_exp_iterator;
00148   typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
00149 
00151   //  typedef COrderedIter<monom_type> ordered_iterator;
00152   typedef COrderedIter<navigator, monom_type> ordered_iterator;
00153 
00155 
00156   typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
00158   typedef CGenericIter<DegLexOrder, navigator, monom_type> dlex_iterator;
00159   typedef CGenericIter<DegRevLexAscOrder, navigator, monom_type> 
00160   dp_asc_iterator;
00161 
00162   typedef CGenericIter<BlockDegLexOrder,  navigator, monom_type> 
00163   block_dlex_iterator;
00164   typedef CGenericIter<BlockDegRevLexAscOrder,  navigator, monom_type> 
00165   block_dp_asc_iterator;
00166 
00167   typedef CGenericIter<LexOrder, navigator, exp_type> lex_exp_iterator;
00168   typedef CGenericIter<DegLexOrder,  navigator, exp_type> dlex_exp_iterator;
00169   typedef CGenericIter<DegRevLexAscOrder,  navigator, exp_type> 
00170   dp_asc_exp_iterator;
00171   typedef CGenericIter<BlockDegLexOrder, navigator, exp_type> 
00172   block_dlex_exp_iterator;
00173   typedef CGenericIter<BlockDegRevLexAscOrder, navigator, exp_type> 
00174   block_dp_asc_exp_iterator;
00176 
00178   typedef lex_iterator const_iterator;
00179 
00181   typedef CExpIter<navigator, exp_type> exp_iterator;
00182 
00184   typedef CGenericIter<LexOrder, navigator, deg_type> deg_iterator;
00185 
00187   typedef std::vector<monom_type> termlist_type;
00188 
00190   typedef dd_type::easy_equality_property easy_equality_property;
00191 
00193   typedef BooleSet set_type;
00194 
00196   typedef std::map<self, idx_type, symmetric_composition<
00197     std::less<navigator>, navigates<self> > > idx_map_type;
00198   typedef std::map<self, std::vector<self>, symmetric_composition<
00199     std::less<navigator>, navigates<self> > > poly_vec_map_type;
00200 
00201   //-------------------------------------------------------------------------
00202   // constructors and destructor
00203   //-------------------------------------------------------------------------
00204 
00206   //  BoolePolynomial();
00207 
00209   //  explicit BoolePolynomial(constant_type);
00210 
00212   BoolePolynomial(const ring_type& ring):
00213     m_dd(ring.zero() )  { }
00214 
00216   BoolePolynomial(constant_type isOne, const ring_type& ring):
00217     m_dd(isOne? ring.one(): ring.zero() )  { }
00218 
00220   BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
00221 
00223                  //  BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
00224 
00226   BoolePolynomial(const exp_type&, const ring_type&); 
00227 
00229   BoolePolynomial(const navigator& rhs, const ring_type& ring):
00230     m_dd(ring, rhs)  {
00231     PBORI_ASSERT(rhs.isValid());
00232   }
00233 
00235   ~BoolePolynomial() {}
00236 
00237   //-------------------------------------------------------------------------
00238   // operators and member functions
00239   //-------------------------------------------------------------------------
00240 
00241   //  self& operator=(const self& rhs) { 
00242   //  return m_dd = rhs.m_dd;
00243   // }
00244 
00245   self& operator=(constant_type rhs) { 
00246     return (*this) = self(rhs, ring());
00247   }
00249 
00250   const self& operator-() const { return *this; }
00251   self& operator+=(const self&);
00252   self& operator+=(constant_type rhs) {
00253 
00254     //return *this = (self(*this) + (rhs).generate(*this));
00255     if (rhs) (*this) = (*this + ring().one());
00256      return *this;
00257   }
00258   template <class RHSType>
00259   self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
00260   self& operator*=(const monom_type&);
00261   self& operator*=(const exp_type&);
00262   self& operator*=(const self&);
00263   self& operator*=(constant_type rhs) {
00264     if (!rhs) *this = ring().zero();
00265     return *this;
00266   }
00267   self& operator/=(const var_type&);
00268   self& operator/=(const monom_type&);
00269   self& operator/=(const exp_type&);
00270   self& operator/=(const self& rhs);
00271   self& operator/=(constant_type rhs);
00272   self& operator%=(const var_type&);
00273   self& operator%=(const monom_type&);
00274   self& operator%=(const self& rhs) { 
00275     return (*this) -= (self(rhs) *= (self(*this) /= rhs)); 
00276   }
00277   self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }
00279 
00281 
00282   bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
00283   bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
00284   bool_type operator==(constant_type rhs) const { 
00285     return ( rhs? isOne(): isZero() );
00286   }
00287   bool_type operator!=(constant_type rhs) const {
00288     //return ( rhs? (!(isOne())): (!(isZero())) );
00289       return (!(*this==rhs));
00290   }
00292 
00294   bool_type isZero() const { return m_dd.isZero(); }
00295 
00297   bool_type isOne() const { return m_dd.isOne(); }
00298 
00300   bool_type isConstant() const { return m_dd.isConstant(); }
00301 
00303   bool_type hasConstantPart() const { return m_dd.ownsOne(); }
00304 
00306   bool_type firstReducibleBy(const self&) const;
00307 
00309   monom_type lead() const;
00310 
00312   monom_type lexLead() const;
00313 
00315 
00318   monom_type boundedLead(deg_type bound) const;
00319 
00321   exp_type leadExp() const;
00322 
00325   exp_type boundedLeadExp(deg_type bound) const;
00326 
00328   set_type leadDivisors() const { return leadFirst().firstDivisors(); };
00329   
00331   hash_type hash() const { return m_dd.hash(); }
00332 
00334   hash_type stableHash() const { return m_dd.stableHash(); } 
00335 
00337   hash_type leadStableHash() const;
00338   
00340   deg_type deg() const;
00341 
00343   deg_type leadDeg() const;
00344 
00346   deg_type lexLeadDeg() const;
00347 
00349   deg_type totalDeg() const;
00350 
00352   deg_type leadTotalDeg() const;
00353 
00355   self gradedPart(deg_type deg) const;
00356 
00358   size_type nNodes() const;
00359 
00361   size_type nUsedVariables() const;
00362 
00364   monom_type usedVariables() const;
00365 
00367   exp_type usedVariablesExp() const;
00368 
00370   size_type length() const;
00371 
00373   ostream_type& print(ostream_type&) const;
00374 
00376   const_iterator begin() const;
00377 
00379   const_iterator end() const;
00380 
00382   exp_iterator expBegin() const;
00383 
00385   exp_iterator expEnd() const;
00386 
00388   first_iterator firstBegin() const;
00389 
00391   first_iterator firstEnd() const;
00392 
00394   monom_type firstTerm() const;
00395 
00397   deg_iterator degBegin() const;
00398 
00400   deg_iterator degEnd() const;
00401 
00403   ordered_iterator orderedBegin() const; 
00404 
00406   ordered_iterator orderedEnd() const;
00407 
00409   ordered_exp_iterator orderedExpBegin() const; 
00410 
00412   ordered_exp_iterator orderedExpEnd() const;
00413 
00415 
00416   lex_iterator genericBegin(lex_tag) const;
00417   lex_iterator genericEnd(lex_tag) const;
00418   dlex_iterator genericBegin(dlex_tag) const;
00419   dlex_iterator genericEnd(dlex_tag) const;
00420   dp_asc_iterator genericBegin(dp_asc_tag) const;
00421   dp_asc_iterator genericEnd(dp_asc_tag) const;
00422   block_dlex_iterator genericBegin(block_dlex_tag) const;
00423   block_dlex_iterator genericEnd(block_dlex_tag) const;
00424   block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
00425   block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;
00426 
00427 
00428   lex_exp_iterator genericExpBegin(lex_tag) const;
00429   lex_exp_iterator genericExpEnd(lex_tag) const;
00430   dlex_exp_iterator genericExpBegin(dlex_tag) const;
00431   dlex_exp_iterator genericExpEnd(dlex_tag) const;
00432   dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
00433   dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
00434   block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
00435   block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
00436   block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
00437   block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;
00439 
00441   navigator navigation() const { return m_dd.navigation(); }
00442  
00444   navigator endOfNavigation() const { return navigator(); }
00445   
00447   dd_type copyDiagram(){   return diagram();  }
00448 
00450   operator set_type() const { return set(); };
00451 
00452   size_type eliminationLength() const;
00453   size_type eliminationLengthWithDegBound(deg_type garantied_deg_bound) const;
00455   void fetchTerms(termlist_type&) const;
00456 
00458   termlist_type terms() const;
00459 
00461   const dd_type& diagram() const { return m_dd; }
00462 
00464   set_type set() const { return m_dd; }
00465 
00467   bool_type isSingleton() const { return dd_is_singleton(navigation()); }
00468 
00470   bool_type isSingletonOrPair() const { 
00471     return dd_is_singleton_or_pair(navigation()); 
00472   }
00473 
00475   bool_type isPair() const { return dd_is_pair(navigation()); }
00476 
00478   const ring_type& ring() const {  return m_dd.ring(); } 
00479 
00481   comp_type compare(const self&) const;
00482 
00484   bool_type inSingleBlock() const;
00485 
00486 protected:
00488   dd_type& internalDiagram() { return m_dd; }
00489 
00491   self leadFirst() const;
00492 
00494   set_type firstDivisors() const;
00495 
00496 private:
00498   dd_type m_dd;
00499 };
00500 
00501 
00503 inline BoolePolynomial 
00504 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
00505 
00506   return BoolePolynomial(lhs) += rhs;
00507 }
00509 inline BoolePolynomial 
00510 operator+(const BoolePolynomial& lhs, BooleConstant rhs) {
00511   return BoolePolynomial(lhs) +=  (rhs);
00512   //return BoolePolynomial(lhs) +=  BoolePolynomial(rhs);
00513 }
00514 
00516 inline BoolePolynomial 
00517 operator+(BooleConstant lhs, const BoolePolynomial& rhs) {
00518 
00519   return BoolePolynomial(rhs) += (lhs);
00520 }
00521 
00522 
00524 template <class RHSType>
00525 inline BoolePolynomial 
00526 operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
00527 
00528   return BoolePolynomial(lhs) -= rhs;
00529 }
00531 inline BoolePolynomial 
00532 operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
00533 
00534   return -(BoolePolynomial(rhs) -= lhs);
00535 }
00536 
00537 
00539 #define PBORI_RHS_MULT(type) inline BoolePolynomial \
00540 operator*(const BoolePolynomial& lhs, const type& rhs) { \
00541     return BoolePolynomial(lhs) *= rhs; }
00542 
00543 PBORI_RHS_MULT(BoolePolynomial)
00544 PBORI_RHS_MULT(BooleMonomial)
00545 PBORI_RHS_MULT(BooleExponent)
00546 PBORI_RHS_MULT(BooleConstant)
00547 
00548 
00549 #undef PBORI_RHS_MULT
00550 
00552 #define PBORI_LHS_MULT(type)  inline BoolePolynomial \
00553 operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
00554 
00555 PBORI_LHS_MULT(BooleMonomial)
00556 PBORI_LHS_MULT(BooleExponent)
00557 PBORI_LHS_MULT(BooleConstant)
00558 
00559 #undef PBORI_LHS_MULT
00560 
00561 
00563 template <class RHSType>
00564 inline BoolePolynomial
00565 operator/(const BoolePolynomial& lhs, const RHSType& rhs){
00566   return BoolePolynomial(lhs) /= rhs;
00567 }
00568 
00570 template <class RHSType>
00571 inline BoolePolynomial
00572 operator%(const BoolePolynomial& lhs, const RHSType& rhs){
00573 
00574   return BoolePolynomial(lhs) %= rhs;
00575 }
00576 
00578 inline BoolePolynomial::bool_type
00579 operator==(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
00580 
00581   return (rhs == lhs); 
00582 }
00583 
00585 inline BoolePolynomial::bool_type
00586 operator!=(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
00587 
00588   return (rhs != lhs); 
00589 }
00590 
00592 BoolePolynomial::ostream_type& 
00593 operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);
00594 
00595 // tests whether polynomial can be reduced by rhs
00596 inline BoolePolynomial::bool_type
00597 BoolePolynomial::firstReducibleBy(const self& rhs) const {
00598 
00599   if( rhs.isOne() )
00600     return true;
00601 
00602   if( isZero() )
00603     return rhs.isZero();
00604 
00605   return std::includes(firstBegin(), firstEnd(), 
00606                        rhs.firstBegin(), rhs.firstEnd());
00607 
00608 }
00609 
00610 
00611 END_NAMESPACE_PBORI
00612 
00613 #endif // of polybori_BoolePolynomial_h_