1 // -*- c++ -*-
2 //*****************************************************************************
3 /** @file BoolePolynomial.h
4 *
5 * @author Alexander Dreyer
6 * @date 2006-03-10
7 *
8 * This file carries the definition of class @c BoolePolynomial, which can be
9 * used to access the boolean polynomials with respect to the polynomial ring,
10 * which was active on initialization time.
11 *
12 * @par Copyright:
13 * (c) 2006-2010 by The PolyBoRi Team
14 *
15 **/
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
34 #include <polybori/routines/pbori_func.h>
35 #include <polybori/common/tags.h>
36 #include <polybori/BooleSet.h>
37
38 #include <polybori/iterators/CTermIter.h>
39 #include <polybori/iterators/CGenericIter.h>
40 #include <polybori/iterators/CBidirectTermIter.h>
41
42 #include <polybori/BooleConstant.h>
43
44 BEGIN_NAMESPACE_PBORI
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>
60 class CIndirectIter;
61
62 template <class IteratorType, class MonomType>
63 class COrderedIter;
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>
70 class CGenericIter;
71
72 template<class NavigatorType, class ExpType>
73 class CExpIter;
74
75
76 /** @class BoolePolynomial
77 * @brief This class wraps the underlying decicion diagram type and defines the
78 * necessary operations.
79 *
80 **/
81 class BoolePolynomial;
82 BoolePolynomial
83 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);
84
85 class BoolePolynomial:
86 public CAuxTypes{
87
88 public:
89
90 /// Let BooleMonomial access protected and private members
91 friend class BooleMonomial;
92
93 //-------------------------------------------------------------------------
94 // types definitions
95 //-------------------------------------------------------------------------
96
97 /// Generic access to current type
98 typedef BoolePolynomial self;
99
100 /// @name Adopt global type definitions
101 //@{
102 typedef BooleSet dd_type;
103 typedef CTypes::ostream_type ostream_type;
104 //@}
105
106 /// Iterator type for iterating over indices of the leading term
107 typedef dd_type::first_iterator first_iterator;
108
109 /// Iterator-like type for navigating through diagram structure
110 typedef dd_type::navigator navigator;
111
112 /// @todo A more sophisticated treatment for monomials is needed.
113
114 /// Fix type for treatment of monomials
115 typedef BooleMonomial monom_type;
116
117 /// Fix type for treatment of monomials
118 typedef BooleVariable var_type;
119
120 /// Fix type for treatment of exponent vectors
121 typedef BooleExponent exp_type;
122
123 /// Type for wrapping integer and bool values
124 typedef BooleConstant constant_type;
125
126 /// Type for Boolean polynomial rings (without ordering)
127 typedef BoolePolyRing ring_type;
128
129 /// Type for result of polynomial comparisons
130 typedef CTypes::comp_type comp_type;
131
132 /// Incrementation functional type
133 typedef
134 binary_composition< std::plus<size_type>,
135 project_ith<1>, integral_constant<size_type, 1> >
136 increment_type;
137
138 /// Decrementation functional type
139 typedef
140 binary_composition< std::minus<size_type>,
141 project_ith<1>, integral_constant<size_type, 1> >
142 decrement_type;
143
144
145
146 /// Iterator type for iterating over all exponents in ordering order
147 // typedef COrderedIter<exp_type> ordered_exp_iterator;
148 typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
149
150 /// Iterator type for iterating over all monomials in ordering order
151 // typedef COrderedIter<monom_type> ordered_iterator;
152 typedef COrderedIter<navigator, monom_type> ordered_iterator;
153
154 /// @name Generic iterators for various orderings
155 //@{
156 typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
157 //// typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
158 typedef CGenericIter<DegLexOrder, navigator, monom_type> dlex_iterator;
159 typedef CGenericIter<DegRevLexAscOrder, navigator, monom_type>
160 dp_asc_iterator;
161
162 typedef CGenericIter<BlockDegLexOrder, navigator, monom_type>
163 block_dlex_iterator;
164 typedef CGenericIter<BlockDegRevLexAscOrder, navigator, monom_type>
165 block_dp_asc_iterator;
166
167 typedef CGenericIter<LexOrder, navigator, exp_type> lex_exp_iterator;
168 typedef CGenericIter<DegLexOrder, navigator, exp_type> dlex_exp_iterator;
169 typedef CGenericIter<DegRevLexAscOrder, navigator, exp_type>
170 dp_asc_exp_iterator;
171 typedef CGenericIter<BlockDegLexOrder, navigator, exp_type>
172 block_dlex_exp_iterator;
173 typedef CGenericIter<BlockDegRevLexAscOrder, navigator, exp_type>
174 block_dp_asc_exp_iterator;
175 //@}
176
177 /// Iterator type for iterating over all monomials
178 typedef lex_iterator const_iterator;
179
180 /// Iterator type for iterating all exponent vectors
181 typedef CExpIter<navigator, exp_type> exp_iterator;
182
183 /// Iterator type for iterating all monomials (dereferencing to degree)
184 typedef CGenericIter<LexOrder, navigator, deg_type> deg_iterator;
185
186 /// Type for lists of terms
187 typedef std::vector<monom_type> termlist_type;
188
189 /// The property whether the equality check is easy is inherited from dd_type
190 typedef dd_type::easy_equality_property easy_equality_property;
191
192 /// Type for sets of Boolean variables
193 typedef BooleSet set_type;
194
195 /// Type for index maps
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
205 /// Default constructor
206 // BoolePolynomial();
207
208 /// Construct polynomial from a constant value 0 or 1
209 // explicit BoolePolynomial(constant_type);
210
211 /// Construct zero polynomial
BoolePolynomial(const ring_type & ring)212 BoolePolynomial(const ring_type& ring):
213 m_dd(ring.zero() ) { }
214
215 /// Construct polynomial in given @c ring from a constant value 0 or 1
BoolePolynomial(constant_type isOne,const ring_type & ring)216 BoolePolynomial(constant_type isOne, const ring_type& ring):
217 m_dd(isOne? ring.one(): ring.zero() ) { }
218
219 /// Construct polynomial from decision diagram
BoolePolynomial(const dd_type & rhs)220 BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
221
222 /// Construct polynomial from a subset of the powerset over all variables
223 // BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
224
225 /// Construct polynomial from exponent vector
226 BoolePolynomial(const exp_type&, const ring_type&);
227
228 /// Construct polynomial from navigator
BoolePolynomial(const navigator & rhs,const ring_type & ring)229 BoolePolynomial(const navigator& rhs, const ring_type& ring):
230 m_dd(ring, rhs) {
231 PBORI_ASSERT(rhs.isValid());
232 }
233
234 /// Destructor
~BoolePolynomial()235 ~BoolePolynomial() {}
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 }
248 /// @name Arithmetical operations
249 //@{
250 const self& operator-() const { return *this; }
251 self& operator+=(const self&);
252 self& operator+=(constant_type rhs) {
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&);
263 self& operator*=(constant_type rhs) {
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); }
278 //@}
279
280 /// @name Logical operations
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); }
284 bool_type operator==(constant_type rhs) const {
285 return ( rhs? isOne(): isZero() );
286 }
287 bool_type operator!=(constant_type rhs) const {
288 //return ( rhs? (!(isOne())): (!(isZero())) );
289 return (!(*this==rhs));
290 }
291 //@}
292
293 /// Check whether polynomial is constant zero
isZero()294 bool_type isZero() const { return m_dd.isZero(); }
295
296 /// Check whether polynomial is constant one
isOne()297 bool_type isOne() const { return m_dd.isOne(); }
298
299 /// Check whether polynomial is zero or one
isConstant()300 bool_type isConstant() const { return m_dd.isConstant(); }
301
302 /// Check whether polynomial has term one
hasConstantPart()303 bool_type hasConstantPart() const { return m_dd.ownsOne(); }
304
305 /// Tests whether polynomial can be reduced by right-hand side
306 bool_type firstReducibleBy(const self&) const;
307
308 /// Get leading term
309 monom_type lead() const;
310
311 /// Get leading term w.r.t. lexicographical order
312 monom_type lexLead() const;
313
314 /// Get leading term (using upper bound of the polynomial degree)
315 /** @note Implementation note: for degree orderings (dlex, dp_asc)
316 * returns the lead of the sub-polynomial of degree 'bound',
317 * falls back to @c lead for all other orderings (lp, block_*) */
318 monom_type boundedLead(deg_type bound) const;
319
320 /// Get leading term
321 exp_type leadExp() const;
322
323 /// Get leading term (using upper bound of the polynomial degree)
324 /// @note See implementation notes of @c boundedLead
325 exp_type boundedLeadExp(deg_type bound) const;
326
327 /// Get all divisors of the leading term
leadDivisors()328 set_type leadDivisors() const { return leadFirst().firstDivisors(); };
329
330 /// Get unique hash value (may change from run to run)
hash()331 hash_type hash() const { return m_dd.hash(); }
332
333 /// Get hash value, which is reproducible
stableHash()334 hash_type stableHash() const { return m_dd.stableHash(); }
335
336 /// Hash value of the leading term
337 hash_type leadStableHash() const;
338
339 /// Maximal degree of the polynomial
340 deg_type deg() const;
341
342 /// Degree of the leading term
343 deg_type leadDeg() const;
344
345 /// Degree of the leading term w.r.t. lexicographical ordering
346 deg_type lexLeadDeg() const;
347
348 /// Total maximal degree of the polynomial
349 deg_type totalDeg() const;
350
351 /// Total degree of the leading term
352 deg_type leadTotalDeg() const;
353
354 /// Get part of given degree
355 self gradedPart(deg_type deg) const;
356
357 /// Number of nodes in the decision diagram
358 size_type nNodes() const;
359
360 /// Number of variables of the polynomial
361 size_type nUsedVariables() const;
362
363 /// Set of variables of the polynomial
364 monom_type usedVariables() const;
365
366 /// Exponent vector of all of variables of the polynomial
367 exp_type usedVariablesExp() const;
368
369 /// Returns number of terms
370 size_type length() const;
371
372 /// Print current polynomial to output stream
373 ostream_type& print(ostream_type&) const;
374
375 /// Start of iteration over monomials
376 const_iterator begin() const;
377
378 /// Finish of iteration over monomials
379 const_iterator end() const;
380
381 /// Start of iteration over exponent vectors
382 exp_iterator expBegin() const;
383
384 /// Finish of iteration over exponent vectors
385 exp_iterator expEnd() const;
386
387 /// Start of first term
388 first_iterator firstBegin() const;
389
390 /// Finish of first term
391 first_iterator firstEnd() const;
392
393 /// Get of first lexicographic term
394 monom_type firstTerm() const;
395
396 /// Start of degrees
397 deg_iterator degBegin() const;
398
399 /// Finish of degrees
400 deg_iterator degEnd() const;
401
402 /// Start of ordering respecting iterator
403 ordered_iterator orderedBegin() const;
404
405 /// Finish of ordering respecting iterator
406 ordered_iterator orderedEnd() const;
407
408 /// Start of ordering respecting exponent iterator
409 ordered_exp_iterator orderedExpBegin() const;
410
411 /// Finish of ordering respecting exponent iterator
412 ordered_exp_iterator orderedExpEnd() const;
413
414 /// @name Compile-time access to generic iterators
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;
438 //@}
439
440 /// Navigate through structure
navigation()441 navigator navigation() const { return m_dd.navigation(); }
442
443 /// End of navigation marker
endOfNavigation()444 navigator endOfNavigation() const { return navigator(); }
445
446 /// gives a copy of the diagram
copyDiagram()447 dd_type copyDiagram(){ return diagram(); }
448
449 /// Casting operator to Boolean set
set_type()450 operator set_type() const { return set(); };
451
452 size_type eliminationLength() const;
453 size_type eliminationLengthWithDegBound(deg_type garantied_deg_bound) const;
454 /// Get list of all terms
455 void fetchTerms(termlist_type&) const;
456
457 /// Return of all terms
458 termlist_type terms() const;
459
460 /// Read-only access to internal decision diagramm structure
diagram()461 const dd_type& diagram() const { return m_dd; }
462
463 /// Get corresponding subset of of the powerset over all variables
set()464 set_type set() const { return m_dd; }
465
466 /// Test, whether we have one term only
isSingleton()467 bool_type isSingleton() const { return dd_is_singleton(navigation()); }
468
469 /// Test, whether we have one or two terms only
isSingletonOrPair()470 bool_type isSingletonOrPair() const {
471 return dd_is_singleton_or_pair(navigation());
472 }
473
474 /// Test, whether we have two terms only
isPair()475 bool_type isPair() const { return dd_is_pair(navigation()); }
476
477 /// Access ring, where this belongs to
ring()478 const ring_type& ring() const { return m_dd.ring(); }
479
480 /// Compare with right-hand side and return comparision code
481 comp_type compare(const self&) const;
482
483 /// Check whether all variables are in one variable block
484 bool_type inSingleBlock() const;
485
486 protected:
487 /// Access to internal decision diagramm structure
internalDiagram()488 dd_type& internalDiagram() { return m_dd; }
489
490 /// Generate a polynomial, whose first term is the leading term
491 self leadFirst() const;
492
493 /// Get all divisors of the first term
494 set_type firstDivisors() const;
495
496 private:
497 /// The actual decision diagramm
498 dd_type m_dd;
499 };
500
501
502 /// Addition operation
503 inline BoolePolynomial
504 operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
505
506 return BoolePolynomial(lhs) += rhs;
507 }
508 /// Addition operation
509 inline BoolePolynomial
510 operator+(const BoolePolynomial& lhs, BooleConstant rhs) {
511 return BoolePolynomial(lhs) += (rhs);
512 //return BoolePolynomial(lhs) += BoolePolynomial(rhs);
513 }
514
515 /// Addition operation
516 inline BoolePolynomial
517 operator+(BooleConstant lhs, const BoolePolynomial& rhs) {
518
519 return BoolePolynomial(rhs) += (lhs);
520 }
521
522
523 /// Subtraction operation
524 template <class RHSType>
525 inline BoolePolynomial
526 operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
527
528 return BoolePolynomial(lhs) -= rhs;
529 }
530 /// Subtraction operation with constant right-hand-side
531 inline BoolePolynomial
532 operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
533
534 return -(BoolePolynomial(rhs) -= lhs);
535 }
536
537
538 /// Multiplication with other left-hand side type
539 #define PBORI_RHS_MULT(type) inline BoolePolynomial \
540 operator*(const BoolePolynomial& lhs, const type& rhs) { \
541 return BoolePolynomial(lhs) *= rhs; }
542
543 PBORI_RHS_MULT(BoolePolynomial)
544 PBORI_RHS_MULT(BooleMonomial)
545 PBORI_RHS_MULT(BooleExponent)
546 PBORI_RHS_MULT(BooleConstant)
547
548
549 #undef PBORI_RHS_MULT
550
551 /// Multiplication with other left-hand side type
552 #define PBORI_LHS_MULT(type) inline BoolePolynomial \
553 operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
554
555 PBORI_LHS_MULT(BooleMonomial)
556 PBORI_LHS_MULT(BooleExponent)
557 PBORI_LHS_MULT(BooleConstant)
558
559 #undef PBORI_LHS_MULT
560
561
562 /// Division by monomial (skipping remainder)
563 template <class RHSType>
564 inline BoolePolynomial
565 operator/(const BoolePolynomial& lhs, const RHSType& rhs){
566 return BoolePolynomial(lhs) /= rhs;
567 }
568
569 /// Modulus monomial (division remainder)
570 template <class RHSType>
571 inline BoolePolynomial
572 operator%(const BoolePolynomial& lhs, const RHSType& rhs){
573
574 return BoolePolynomial(lhs) %= rhs;
575 }
576
577 /// Equality check (with constant lhs)
578 inline BoolePolynomial::bool_type
579 operator==(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
580
581 return (rhs == lhs);
582 }
583
584 /// Nonquality check (with constant lhs)
585 inline BoolePolynomial::bool_type
586 operator!=(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
587
588 return (rhs != lhs);
589 }
590
591 /// Stream output operator
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
firstReducibleBy(const self & rhs)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
611 END_NAMESPACE_PBORI
612
613 #endif // of polybori_BoolePolynomial_h_
614