PolyBoRi
BoolePolynomial.h
Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00016 //*****************************************************************************
00017 
00018 #ifndef BoolePolynomial_h_
00019 #define 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 "BoolePolyRing.h"
00031 
00032 // include definition of sets of Boolean variables
00033 
00034 #include "pbori_func.h"
00035 #include "pbori_tags.h"
00036 #include "BooleSet.h"
00037 
00038 #include "CTermIter.h"
00039 #include "CGenericIter.h"
00040 #include "CBidirectTermIter.h"
00041 
00042 #include "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(constant_type isOne, const ring_type& ring):
00213     m_dd(isOne? ring.one(): ring.zero() )  { }
00214 
00216   BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
00217 
00219                  //  BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
00220 
00222   BoolePolynomial(const exp_type&, const ring_type&); 
00223 
00225   BoolePolynomial(const navigator& rhs, const ring_type& ring):
00226     m_dd(ring, rhs)  {
00227     assert(rhs.isValid());
00228   }
00229 
00231   ~BoolePolynomial() {}
00232 
00233   //-------------------------------------------------------------------------
00234   // operators and member functions
00235   //-------------------------------------------------------------------------
00236 
00237   //  self& operator=(const self& rhs) { 
00238   //  return m_dd = rhs.m_dd;
00239   // }
00240 
00241   self& operator=(constant_type rhs) { 
00242     return (*this) = self(rhs);//rhs.generate(*this); 
00243   }
00245 
00246   const self& operator-() const { return *this; }
00247   self& operator+=(const self&);
00248   self& operator+=(constant_type rhs) {
00249 
00250     //return *this = (self(*this) + (rhs).generate(*this));
00251     if (rhs) (*this) = (*this + ring().one());
00252      return *this;
00253   }
00254   template <class RHSType>
00255   self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
00256   self& operator*=(const monom_type&);
00257   self& operator*=(const exp_type&);
00258   self& operator*=(const self&);
00259   self& operator*=(constant_type rhs) {
00260     if (!rhs) *this = ring().zero();
00261     return *this;
00262   }
00263   self& operator/=(const var_type&);
00264   self& operator/=(const monom_type&);
00265   self& operator/=(const exp_type&);
00266   self& operator/=(const self& rhs);
00267   self& operator/=(constant_type rhs);
00268   self& operator%=(const var_type&);
00269   self& operator%=(const monom_type&);
00270   self& operator%=(const self& rhs) { 
00271     return (*this) -= (self(rhs) *= (self(*this) /= rhs)); 
00272   }
00273   self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }
00275 
00277 
00278   bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
00279   bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
00280   bool_type operator==(constant_type rhs) const { 
00281     return ( rhs? isOne(): isZero() );
00282   }
00283   bool_type operator!=(constant_type rhs) const {
00284     //return ( rhs? (!(isOne())): (!(isZero())) );
00285       return (!(*this==rhs));
00286   }
00288 
00290   bool_type isZero() const { return m_dd.isZero(); }
00291 
00293   bool_type isOne() const { return m_dd.isOne(); }
00294 
00296   bool_type isConstant() const { return m_dd.isConstant(); }
00297 
00299   bool_type hasConstantPart() const { return m_dd.ownsOne(); }
00300 
00302   bool_type firstReducibleBy(const self&) const;
00303 
00305   monom_type lead() const;
00306 
00308   monom_type lexLead() const;
00309 
00311 
00314   monom_type boundedLead(deg_type bound) const;
00315 
00317   exp_type leadExp() const;
00318 
00321   exp_type boundedLeadExp(deg_type bound) const;
00322 
00324   set_type leadDivisors() const { return leadFirst().firstDivisors(); };
00325   
00327   hash_type hash() const { return m_dd.hash(); }
00328 
00330   hash_type stableHash() const { return m_dd.stableHash(); } 
00331 
00333   hash_type leadStableHash() const;
00334   
00336   deg_type deg() const;
00337 
00339   deg_type leadDeg() const;
00340 
00342   deg_type lexLeadDeg() const;
00343 
00345   deg_type totalDeg() const;
00346 
00348   deg_type leadTotalDeg() const;
00349 
00351   self gradedPart(deg_type deg) const;
00352 
00354   size_type nNodes() const;
00355 
00357   size_type nUsedVariables() const;
00358 
00360   monom_type usedVariables() const;
00361 
00363   exp_type usedVariablesExp() const;
00364 
00366   size_type length() const;
00367 
00369   ostream_type& print(ostream_type&) const;
00370 
00372   const_iterator begin() const;
00373 
00375   const_iterator end() const;
00376 
00378   exp_iterator expBegin() const;
00379 
00381   exp_iterator expEnd() const;
00382 
00384   first_iterator firstBegin() const;
00385 
00387   first_iterator firstEnd() const;
00388 
00390   monom_type firstTerm() const;
00391 
00393   deg_iterator degBegin() const;
00394 
00396   deg_iterator degEnd() const;
00397 
00399   ordered_iterator orderedBegin() const; 
00400 
00402   ordered_iterator orderedEnd() const;
00403 
00405   ordered_exp_iterator orderedExpBegin() const; 
00406 
00408   ordered_exp_iterator orderedExpEnd() const;
00409 
00411 
00412   lex_iterator genericBegin(lex_tag) const;
00413   lex_iterator genericEnd(lex_tag) const;
00414   dlex_iterator genericBegin(dlex_tag) const;
00415   dlex_iterator genericEnd(dlex_tag) const;
00416   dp_asc_iterator genericBegin(dp_asc_tag) const;
00417   dp_asc_iterator genericEnd(dp_asc_tag) const;
00418   block_dlex_iterator genericBegin(block_dlex_tag) const;
00419   block_dlex_iterator genericEnd(block_dlex_tag) const;
00420   block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
00421   block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;
00422 
00423 
00424   lex_exp_iterator genericExpBegin(lex_tag) const;
00425   lex_exp_iterator genericExpEnd(lex_tag) const;
00426   dlex_exp_iterator genericExpBegin(dlex_tag) const;
00427   dlex_exp_iterator genericExpEnd(dlex_tag) const;
00428   dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
00429   dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
00430   block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
00431   block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
00432   block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
00433   block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;
00435 
00437   navigator navigation() const { return m_dd.navigation(); }
00438  
00440   navigator endOfNavigation() const { return navigator(); }
00441   
00443   dd_type copyDiagram(){   return diagram();  }
00444 
00446   operator set_type() const { return set(); };
00447 
00448   size_type eliminationLength() const;
00449   size_type eliminationLengthWithDegBound(deg_type garantied_deg_bound) const;
00451   void fetchTerms(termlist_type&) const;
00452 
00454   termlist_type terms() const;
00455 
00457   const dd_type& diagram() const { return m_dd; }
00458 
00460   set_type set() const { return m_dd; }
00461 
00463   bool_type isSingleton() const { return dd_is_singleton(navigation()); }
00464 
00466   bool_type isSingletonOrPair() const { 
00467     return dd_is_singleton_or_pair(navigation()); 
00468   }
00469 
00471   bool_type isPair() const { return dd_is_pair(navigation()); }
00472 
00474   const ring_type& ring() const {  return m_dd.ring(); } 
00475 
00477   comp_type compare(const self&) const;
00478 
00479 protected:
00480 
00482   dd_type& internalDiagram() { return m_dd; }
00483 
00485   self leadFirst() const;
00486 
00488   set_type firstDivisors() const;
00489 
00490 private:
00492   dd_type m_dd;
00493 };
00494 
00495 
00497 inline BoolePolynomial 
00498 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
00499 
00500   return BoolePolynomial(lhs) += rhs;
00501 }
00503 inline BoolePolynomial 
00504 operator+(const BoolePolynomial& lhs, BooleConstant rhs) {
00505   return BoolePolynomial(lhs) +=  (rhs);
00506   //return BoolePolynomial(lhs) +=  BoolePolynomial(rhs);
00507 }
00508 
00510 inline BoolePolynomial 
00511 operator+(BooleConstant lhs, const BoolePolynomial& rhs) {
00512 
00513   return BoolePolynomial(rhs) += (lhs);
00514 }
00515 
00516 
00518 template <class RHSType>
00519 inline BoolePolynomial 
00520 operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
00521 
00522   return BoolePolynomial(lhs) -= rhs;
00523 }
00525 inline BoolePolynomial 
00526 operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
00527 
00528   return -(BoolePolynomial(rhs) -= lhs);
00529 }
00530 
00531 
00533 #define PBORI_RHS_MULT(type) inline BoolePolynomial \
00534 operator*(const BoolePolynomial& lhs, const type& rhs) { \
00535     return BoolePolynomial(lhs) *= rhs; }
00536 
00537 PBORI_RHS_MULT(BoolePolynomial)
00538 PBORI_RHS_MULT(BooleMonomial)
00539 PBORI_RHS_MULT(BooleExponent)
00540 PBORI_RHS_MULT(BooleConstant)
00541 
00542 
00543 #undef PBORI_RHS_MULT
00544 
00546 #define PBORI_LHS_MULT(type)  inline BoolePolynomial \
00547 operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
00548 
00549 PBORI_LHS_MULT(BooleMonomial)
00550 PBORI_LHS_MULT(BooleExponent)
00551 PBORI_LHS_MULT(BooleConstant)
00552 
00553 #undef PBORI_LHS_MULT
00554 
00555 
00557 template <class RHSType>
00558 inline BoolePolynomial
00559 operator/(const BoolePolynomial& lhs, const RHSType& rhs){
00560   return BoolePolynomial(lhs) /= rhs;
00561 }
00562 
00564 template <class RHSType>
00565 inline BoolePolynomial
00566 operator%(const BoolePolynomial& lhs, const RHSType& rhs){
00567 
00568   return BoolePolynomial(lhs) %= rhs;
00569 }
00570 
00572 inline BoolePolynomial::bool_type
00573 operator==(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
00574 
00575   return (rhs == lhs); 
00576 }
00577 
00579 inline BoolePolynomial::bool_type
00580 operator!=(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
00581 
00582   return (rhs != lhs); 
00583 }
00584 
00586 BoolePolynomial::ostream_type& 
00587 operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);
00588 
00589 // tests whether polynomial can be reduced by rhs
00590 inline BoolePolynomial::bool_type
00591 BoolePolynomial::firstReducibleBy(const self& rhs) const {
00592 
00593   if( rhs.isOne() )
00594     return true;
00595 
00596   if( isZero() )
00597     return rhs.isZero();
00598 
00599   return std::includes(firstBegin(), firstEnd(), 
00600                        rhs.firstBegin(), rhs.firstEnd());
00601 
00602 }
00603 
00604 
00605 END_NAMESPACE_PBORI
00606 
00607 #endif // of BoolePolynomial_h_