PolyBoRi
|
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_