PolyBoRi
BoolePolynomial.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
16 //*****************************************************************************
17 
18 #ifndef polybori_BoolePolynomial_h_
19 #define polybori_BoolePolynomial_h_
20 
21 // include standard definitions
22 #include <vector>
23 
24 // get standard map functionality
25 #include <map>
26 
27 // get standard algorithmic functionalites
28 #include <algorithm>
29 
30 #include <polybori/BoolePolyRing.h>
31 
32 // include definition of sets of Boolean variables
33 
35 #include <polybori/common/tags.h>
36 #include <polybori/BooleSet.h>
37 
41 
42 #include <polybori/BooleConstant.h>
43 
45 
46 
47 // forward declarations
48 class LexOrder;
49 class DegLexOrder;
50 class DegRevLexAscOrder;
51 class BlockDegLexOrder;
52 class BlockDegRevLexAscOrder;
53 
54 class BooleMonomial;
55 class BooleVariable;
56 class BooleExponent;
57 
58 
59 template <class IteratorType, class MonomType>
61 
62 template <class IteratorType, class MonomType>
64 
65 
66 //template<class, class, class, class> class CGenericIter;
67 template<class, class, class, class> class CDelayedTermIter;
68 
69 template<class OrderType, class NavigatorType, class MonomType>
71 
72 template<class NavigatorType, class ExpType>
73 class CExpIter;
74 
75 
81 class BoolePolynomial;
83 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);
84 
86  public CAuxTypes{
87 
88 public:
89 
91  friend class BooleMonomial;
92 
93  //-------------------------------------------------------------------------
94  // types definitions
95  //-------------------------------------------------------------------------
96 
98  typedef BoolePolynomial self;
99 
101 
102  typedef BooleSet dd_type;
105 
108 
111 
113 
116 
119 
122 
125 
128 
131 
133  typedef
137 
139  typedef
143 
144 
145 
147  // typedef COrderedIter<exp_type> ordered_exp_iterator;
149 
151  // typedef COrderedIter<monom_type> ordered_iterator;
153 
155 
161 
166 
176 
179 
182 
185 
187  typedef std::vector<monom_type> termlist_type;
188 
191 
194 
196  typedef std::map<self, idx_type, symmetric_composition<
197  std::less<navigator>, navigates<self> > > idx_map_type;
198  typedef std::map<self, std::vector<self>, symmetric_composition<
199  std::less<navigator>, navigates<self> > > poly_vec_map_type;
200 
201  //-------------------------------------------------------------------------
202  // constructors and destructor
203  //-------------------------------------------------------------------------
204 
206  // BoolePolynomial();
207 
209  // explicit BoolePolynomial(constant_type);
210 
213  m_dd(ring.zero() ) { }
214 
217  m_dd(isOne? ring.one(): ring.zero() ) { }
218 
220  BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
221 
223  // BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
224 
226  BoolePolynomial(const exp_type&, const ring_type&);
227 
229  BoolePolynomial(const navigator& rhs, const ring_type& ring):
230  m_dd(ring, rhs) {
231  PBORI_ASSERT(rhs.isValid());
232  }
233 
236 
237  //-------------------------------------------------------------------------
238  // operators and member functions
239  //-------------------------------------------------------------------------
240 
241  // self& operator=(const self& rhs) {
242  // return m_dd = rhs.m_dd;
243  // }
244 
245  self& operator=(constant_type rhs) {
246  return (*this) = self(rhs, ring());
247  }
249 
250  const self& operator-() const { return *this; }
251  self& operator+=(const self&);
253 
254  //return *this = (self(*this) + (rhs).generate(*this));
255  if (rhs) (*this) = (*this + ring().one());
256  return *this;
257  }
258  template <class RHSType>
259  self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
260  self& operator*=(const monom_type&);
261  self& operator*=(const exp_type&);
262  self& operator*=(const self&);
264  if (!rhs) *this = ring().zero();
265  return *this;
266  }
267  self& operator/=(const var_type&);
268  self& operator/=(const monom_type&);
269  self& operator/=(const exp_type&);
270  self& operator/=(const self& rhs);
271  self& operator/=(constant_type rhs);
272  self& operator%=(const var_type&);
273  self& operator%=(const monom_type&);
274  self& operator%=(const self& rhs) {
275  return (*this) -= (self(rhs) *= (self(*this) /= rhs));
276  }
277  self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }
279 
281 
282  bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
283  bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
285  return ( rhs? isOne(): isZero() );
286  }
288  //return ( rhs? (!(isOne())): (!(isZero())) );
289  return (!(*this==rhs));
290  }
292 
294  bool_type isZero() const { return m_dd.isZero(); }
295 
297  bool_type isOne() const { return m_dd.isOne(); }
298 
300  bool_type isConstant() const { return m_dd.isConstant(); }
301 
303  bool_type hasConstantPart() const { return m_dd.ownsOne(); }
304 
306  bool_type firstReducibleBy(const self&) const;
307 
309  monom_type lead() const;
310 
312  monom_type lexLead() const;
313 
315 
318  monom_type boundedLead(deg_type bound) const;
319 
321  exp_type leadExp() const;
322 
325  exp_type boundedLeadExp(deg_type bound) const;
326 
328  set_type leadDivisors() const { return leadFirst().firstDivisors(); };
329 
331  hash_type hash() const { return m_dd.hash(); }
332 
334  hash_type stableHash() const { return m_dd.stableHash(); }
335 
337  hash_type leadStableHash() const;
338 
340  deg_type deg() const;
341 
343  deg_type leadDeg() const;
344 
346  deg_type lexLeadDeg() const;
347 
349  deg_type totalDeg() const;
350 
352  deg_type leadTotalDeg() const;
353 
355  self gradedPart(deg_type deg) const;
356 
358  size_type nNodes() const;
359 
361  size_type nUsedVariables() const;
362 
364  monom_type usedVariables() const;
365 
367  exp_type usedVariablesExp() const;
368 
370  size_type length() const;
371 
373  ostream_type& print(ostream_type&) const;
374 
376  const_iterator begin() const;
377 
379  const_iterator end() const;
380 
382  exp_iterator expBegin() const;
383 
385  exp_iterator expEnd() const;
386 
388  first_iterator firstBegin() const;
389 
391  first_iterator firstEnd() const;
392 
394  monom_type firstTerm() const;
395 
397  deg_iterator degBegin() const;
398 
400  deg_iterator degEnd() const;
401 
403  ordered_iterator orderedBegin() const;
404 
406  ordered_iterator orderedEnd() const;
407 
409  ordered_exp_iterator orderedExpBegin() const;
410 
412  ordered_exp_iterator orderedExpEnd() const;
413 
415 
416  lex_iterator genericBegin(lex_tag) const;
417  lex_iterator genericEnd(lex_tag) const;
418  dlex_iterator genericBegin(dlex_tag) const;
419  dlex_iterator genericEnd(dlex_tag) const;
420  dp_asc_iterator genericBegin(dp_asc_tag) const;
421  dp_asc_iterator genericEnd(dp_asc_tag) const;
422  block_dlex_iterator genericBegin(block_dlex_tag) const;
423  block_dlex_iterator genericEnd(block_dlex_tag) const;
424  block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
425  block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;
426 
427 
428  lex_exp_iterator genericExpBegin(lex_tag) const;
429  lex_exp_iterator genericExpEnd(lex_tag) const;
430  dlex_exp_iterator genericExpBegin(dlex_tag) const;
431  dlex_exp_iterator genericExpEnd(dlex_tag) const;
432  dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
433  dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
434  block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
435  block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
436  block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
437  block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;
439 
441  navigator navigation() const { return m_dd.navigation(); }
442 
444  navigator endOfNavigation() const { return navigator(); }
445 
447  dd_type copyDiagram(){ return diagram(); }
448 
450  operator set_type() const { return set(); };
451 
452  size_type eliminationLength() const;
453  size_type eliminationLengthWithDegBound(deg_type garantied_deg_bound) const;
455  void fetchTerms(termlist_type&) const;
456 
458  termlist_type terms() const;
459 
461  const dd_type& diagram() const { return m_dd; }
462 
464  set_type set() const { return m_dd; }
465 
467  bool_type isSingleton() const { return dd_is_singleton(navigation()); }
468 
471  return dd_is_singleton_or_pair(navigation());
472  }
473 
475  bool_type isPair() const { return dd_is_pair(navigation()); }
476 
478  const ring_type& ring() const { return m_dd.ring(); }
479 
481  comp_type compare(const self&) const;
482 
484  bool_type inSingleBlock() const;
485 
486 protected:
488  dd_type& internalDiagram() { return m_dd; }
489 
491  self leadFirst() const;
492 
494  set_type firstDivisors() const;
495 
496 private:
498  dd_type m_dd;
499 };
500 
501 
503 inline BoolePolynomial
504 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
505 
506  return BoolePolynomial(lhs) += rhs;
507 }
509 inline BoolePolynomial
511  return BoolePolynomial(lhs) += (rhs);
512  //return BoolePolynomial(lhs) += BoolePolynomial(rhs);
513 }
514 
516 inline BoolePolynomial
518 
519  return BoolePolynomial(rhs) += (lhs);
520 }
521 
522 
524 template <class RHSType>
525 inline BoolePolynomial
526 operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
527 
528  return BoolePolynomial(lhs) -= rhs;
529 }
531 inline BoolePolynomial
532 operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
533 
534  return -(BoolePolynomial(rhs) -= lhs);
535 }
536 
537 
539 #define PBORI_RHS_MULT(type) inline BoolePolynomial \
540 operator*(const BoolePolynomial& lhs, const type& rhs) { \
541  return BoolePolynomial(lhs) *= rhs; }
542 
547 
548 
549 #undef PBORI_RHS_MULT
550 
552 #define PBORI_LHS_MULT(type) inline BoolePolynomial \
553 operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
554 
558 
559 #undef PBORI_LHS_MULT
560 
561 
563 template <class RHSType>
564 inline BoolePolynomial
565 operator/(const BoolePolynomial& lhs, const RHSType& rhs){
566  return BoolePolynomial(lhs) /= rhs;
567 }
568 
570 template <class RHSType>
571 inline BoolePolynomial
572 operator%(const BoolePolynomial& lhs, const RHSType& rhs){
573 
574  return BoolePolynomial(lhs) %= rhs;
575 }
576 
578 inline BoolePolynomial::bool_type
580 
581  return (rhs == lhs);
582 }
583 
585 inline BoolePolynomial::bool_type
587 
588  return (rhs != lhs);
589 }
590 
592 BoolePolynomial::ostream_type&
593 operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);
594 
595 // tests whether polynomial can be reduced by rhs
596 inline BoolePolynomial::bool_type
597 BoolePolynomial::firstReducibleBy(const self& rhs) const {
598 
599  if( rhs.isOne() )
600  return true;
601 
602  if( isZero() )
603  return rhs.isZero();
604 
605  return std::includes(firstBegin(), firstEnd(),
606  rhs.firstBegin(), rhs.firstEnd());
607 
608 }
609 
610 
612 
613 #endif // of polybori_BoolePolynomial_h_