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