PolyBoRi
BooleMonomial.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
16 //*****************************************************************************
17 
18 #ifndef polybori_BooleMonomial_h_
19 #define polybori_BooleMonomial_h_
20 
21 // include basic definitions
22 #include <polybori/pbori_defs.h>
23 
24 // get definition of BoolePolynomial and BooleVariable
26 #include <polybori/BooleVariable.h>
27 // get standard map functionality
28 #include <map>
29 
30 // get variable iterator
32 
33 // get variable iterator
35 
37 
38 class BooleVariable;
39 class BooleExponent;
40 template <class DDType, class MonomType> class CDDOperations;
41 
51  public CAuxTypes {
52 
54  typedef BooleMonomial self;
55 
56 public:
57  template <class, class> friend class CDDOperations;
58  friend class COrderingBase;
59  template <class> friend class CTermGeneratorBase;
60  template <class, class> friend class CTermGeneratorBase__;
61 
64 
66 
71 
74 
77 
80 
83 
86 
89 
92 
94  // typedef generate_index_map<self>::type idx_map_type;
95 
96  typedef std::map<self, idx_type, symmetric_composition<
97  std::less<poly_type::navigator>,
99 
102 
104  BooleMonomial(const self& rhs):
105  m_poly(rhs.m_poly) {}
106 
108  BooleMonomial(const var_type& rhs); // not inlined to avoid dependency loop
109  // (both depend on poly_type)
110 
112  BooleMonomial(const exp_type& rhs, const ring_type& ring):
113  m_poly(rhs, ring) { }
114 
116  BooleMonomial(const ring_type& ring):
117  m_poly(ring.one()) {}
118 
121 
123  operator const BoolePolynomial&() const { return m_poly; }
124 
126  exp_type exp() const;
127 
128 
130  const_iterator begin() const { return m_poly.firstBegin(); }
131 
133  const_iterator end() const { return m_poly.firstEnd(); }
134 
136  variable_iterator variableBegin() const {
137  return variable_iterator(begin(), ring());
138  }
139 
141  variable_iterator variableEnd() const {
142  return variable_iterator(end(), ring());
143  }
144 
146  deg_type deg() const {
147  return std::distance(m_poly.firstBegin(),m_poly.firstEnd());
148  }
149 
151  size_type size() const { return (size_type)deg(); } // always nonnegative
152 
154  set_type divisors() const { return m_poly.leadDivisors(); }
155 
157  set_type multiples(const self&) const;
158 
161  return stable_first_hash_range(m_poly.navigation());
162  }
163 
165  hash_type hash() const { return m_poly.hash(); }
166 
168  self change(idx_type) const;
169 
170 
172 
173  self& operator*=(const self&);
174  self& operator/=(const self&);
175  self& operator*=(const var_type&);
176  self& operator/=(const var_type&);
178 
180 
181  bool_type operator==(const self& rhs) const { return m_poly == rhs.m_poly; }
182  bool_type operator!=(const self& rhs) const { return m_poly != rhs.m_poly; }
183  bool_type operator==(constant_type rhs) const { return m_poly == rhs; }
184  bool_type operator!=(constant_type rhs) const { return m_poly != rhs; }
185  bool_type isOne() const { return m_poly.isOne(); }
186  bool_type isConstant() const { return m_poly.isConstant(); }
188 
190  bool_type reducibleBy(const self& rhs) const {
191  return m_poly.firstReducibleBy(rhs); }
192  bool_type reducibleBy(const var_type& rhs) const;
193 
195  comp_type compare(const self&) const;
196 
198  deg_type LCMDeg(const self&) const;
199 
201  self& LCMAssign(const self&);
202 
204  self LCM(const self&) const;
205 
207  self& GCDAssign(const self&);
208 
210  self GCD(const self&) const;
211 
213  const dd_type& diagram() const { return m_poly.diagram(); }
214 
216  set_type set() const { return m_poly.set(); }
217 
219  self& popFirst() {
220  PBORI_ASSERT(!m_poly.isConstant());
221  return *this = set_type( dd_type(m_poly.ring(),
222  m_poly.navigation().thenBranch()) );
223  }
224 
226  var_type firstVariable() const;
227 
230  idx_type firstIndex() const {
231  return *m_poly.navigation();
232  }
233 
235  const ring_type& ring() const { return m_poly.ring(); }
236 
237 protected:
239  dd_type& internalDiagram() { return m_poly.internalDiagram(); }
240 
242  BooleMonomial(const set_type& rhs): m_poly(rhs.diagram()) {
243  PBORI_ASSERT(!m_poly.isZero());
244  }
245 
246 private:
247  BoolePolynomial m_poly;
248 };
249 
251 inline BooleMonomial
252 operator*(const BooleMonomial& lhs, const BooleMonomial& rhs) {
253  return BooleMonomial(lhs) *= rhs;
254 }
256 inline BooleMonomial
257 operator*(const BooleMonomial& lhs, const BooleVariable& rhs) {
258  return BooleMonomial(lhs) *= rhs;
259 }
261 inline BoolePolynomial
263  return BoolePolynomial(lhs) *= rhs;
264 }
265 
267 inline BoolePolynomial
269  return rhs * lhs;
270 }
271 
273 inline BooleMonomial
274 operator/(const BooleMonomial& lhs, const BooleMonomial& rhs) {
275  return BooleMonomial(lhs) /= rhs;
276 }
277 
279 inline BooleMonomial
280 operator/(const BooleMonomial& lhs, const BooleVariable& rhs) {
281  return lhs / BooleMonomial(rhs);
282 }
283 
285 inline BooleMonomial::bool_type
286 operator<(const BooleMonomial& lhs, const BooleMonomial& rhs) {
287 
288  return (lhs.compare(rhs) == CTypes::less_than);
289 }
290 
292 inline BooleMonomial::bool_type
293 operator>(const BooleMonomial& lhs, const BooleMonomial& rhs) {
294 
295  return (lhs.compare(rhs) == CTypes::greater_than);
296 }
297 
299 inline BooleMonomial::bool_type
300 operator<=(const BooleMonomial& lhs, const BooleMonomial& rhs) {
301 
302  return (lhs.compare(rhs) <= CTypes::less_or_equal_max);
303 }
304 
306 inline BooleMonomial::bool_type
307 operator>=(const BooleMonomial& lhs, const BooleMonomial& rhs) {
308 
309  return (lhs.compare(rhs) >= CTypes::greater_or_equal_min);
310 }
311 
312 
314 inline BooleMonomial
315 GCD(const BooleMonomial& lhs, const BooleMonomial& rhs ){
316 
317  return lhs.GCD(rhs);
318 }
319 
321 inline BooleMonomial
322 LCM(const BooleMonomial& lhs, const BooleMonomial& rhs ){
323 
324  return lhs.LCM(rhs);
325 }
326 
327 // Anyone need this?
330 // BooleMonomial::bool_type
331 // greater_variable(BooleMonomial::idx_type lhs, BooleMonomial::idx_type rhs);
332 
333 
335 inline BoolePolynomial
336 operator*(const BooleVariable& lhs, const BooleConstant& rhs){
337 
338  return BooleMonomial(lhs) * rhs;
339 }
340 
342 inline BoolePolynomial
343 operator*(const BooleConstant& lhs, const BooleVariable& rhs){
344 
345  return rhs * lhs;
346 }
347 
349 inline BoolePolynomial
351  const BoolePolynomial& rhs){
352 
353  return BoolePolynomial(rhs) *= BooleMonomial(lhs);
354 }
355 
357 inline BooleMonomial
359  const BooleMonomial& rhs){
360 
361  return BooleMonomial(lhs) * rhs;
362 }
363 
365 inline BoolePolynomial&
367  const BooleVariable& rhs){
368 
369  return lhs *= BooleMonomial(rhs);
370 }
371 
373 inline BooleMonomial
375  const BooleVariable& rhs){
376 
377  return BooleMonomial(lhs) *= BooleMonomial(rhs);
378 }
379 
381 inline BoolePolynomial
383  const BooleVariable& rhs){
384 
385  return BoolePolynomial(lhs) *= BooleMonomial(rhs);
386 }
387 
389 inline BoolePolynomial
391  const BooleVariable& rhs){
392 
393  return lhs / BooleMonomial(rhs);
394 }
395 
396 
398 inline BoolePolynomial
400  const BooleVariable& rhs){
401 
402  return lhs % BooleMonomial(rhs);
403 }
404 
405 
407 
408 
409 #endif // of polybori_BooleMonomial_h_
deg_type deg() const
Degree of the monomial.
Definition: BooleMonomial.h:146
This class is just a wrapper for using variables for storing indices as interim data structure for Bo...
Definition: BooleExponent.h:34
#define END_NAMESPACE_PBORI
Finish project's namespace.
Definition: pbori_defs.h:77
BoolePolynomial operator/(const BoolePolynomial &lhs, const BooleVariable &rhs)
Division of a polynomial by a variable (forcing monomial variant)
Definition: BooleMonomial.h:390
poly_type::var_type var_type
Type of Boolean variables.
Definition: BooleMonomial.h:73
bool_type reducibleBy(const self &rhs) const
Test for reducibility.
Definition: BooleMonomial.h:190
poly_type::ring_type ring_type
Type for Boolean polynomial rings (without ordering)
Definition: BooleMonomial.h:85
self GCD(const self &) const
Compute the greatest common divisor.
Definition: BooleMonomial.cc:169
BooleMonomial(const set_type &rhs)
Construct from decision diagram.
Definition: BooleMonomial.h:242
#define BEGIN_NAMESPACE_PBORI
Start project's namespace.
Definition: pbori_defs.h:74
std::map< self, idx_type, symmetric_composition< std::less< poly_type::navigator >, navigates< poly_type > > > idx_map_type
Type for index maps.
Definition: BooleMonomial.h:98
void stable_first_hash_range(HashType &seed, NaviType navi)
Definition: pbori_routines_hash.h:60
set_type set() const
Get corresponding subset of of the powerset over all variables.
Definition: BooleMonomial.h:216
const self & diagram() const
Access internal decision diagram.
Definition: BooleSet.h:231
self LCM(const self &) const
Compute the least common multiple.
Definition: BooleMonomial.cc:219
int deg_type
Type for polynomial degrees (ranges from -1 to maxint)
Definition: pbori_defs.h:222
int deg_type
Definition: groebner_defs.h:42
const_iterator begin() const
Start iteration over indices.
Definition: BooleMonomial.h:130
self & popFirst()
Removes the first variables from monomial.
Definition: BooleMonomial.h:219
dd_type & internalDiagram()
Access to internal decision diagramm structure.
Definition: BooleMonomial.h:239
BoolePolynomial operator%(const BoolePolynomial &lhs, const BooleVariable &rhs)
Remainder of division of a polynomial by a variable.
Definition: BooleMonomial.h:399
BooleMonomial(const exp_type &rhs, const ring_type &ring)
Construct from exponent vector.
Definition: BooleMonomial.h:112
Definition: COrderingBase.h:43
poly_type::ostream_type ostream_type
Definition: BooleMonomial.h:69
variable_iterator variableBegin() const
Start iteration over variables.
Definition: BooleMonomial.h:136
comp_type compare(const self &) const
Compare with rhs monomial and return comparision code.
Definition: BooleMonomial.cc:115
bool_type operator==(constant_type rhs) const
Definition: BooleMonomial.h:183
poly_type::dd_type dd_type
Definition: BooleMonomial.h:67
This class reinterprets decicion diagram managers as Boolean polynomial rings, adds an ordering and v...
Definition: BoolePolyRing.h:40
const_iterator end() const
Finish iteration over indices.
Definition: BooleMonomial.h:133
CVariableIter< const_iterator, var_type > variable_iterator
Access to iterator over variables.
Definition: BooleMonomial.h:91
idx_type firstIndex() const
Definition: BooleMonomial.h:230
Definition: pbori_func.h:722
Accessing .change()
This struct contains auxiliary type definitions.
Definition: pbori_defs.h:210
Definition: BooleMonomial.h:40
BooleMonomial::bool_type operator>=(const BooleMonomial &lhs, const BooleMonomial &rhs)
Greater or equal than comparision.
Definition: BooleMonomial.h:307
poly_type::first_iterator const_iterator
Access to iterator over indices.
Definition: BooleMonomial.h:88
BoolePolynomial poly_type
Type of Boolean polynomials.
Definition: BooleMonomial.h:63
int integer_type
Type for integer numbers.
Definition: pbori_defs.h:225
This class wraps the underlying decicion diagram type and defines the necessary operations.
Definition: BoolePolynomial.h:85
BooleMonomial GCD(const BooleMonomial &lhs, const BooleMonomial &rhs)
Compute the greatest common divisor of two monomials.
Definition: BooleMonomial.h:315
std::size_t hash_type
Type for hashing.
Definition: pbori_defs.h:231
hash_type stableHash() const
Hash value of the monomial.
Definition: BooleMonomial.h:160
This template class defines an iterator for monomial types.
Definition: CVariableIter.h:32
poly_type::exp_type exp_type
Type of exponent vector.
Definition: BooleMonomial.h:82
set_type divisors() const
Divisors of the monomial.
Definition: BooleMonomial.h:154
bool_type operator==(const self &rhs) const
Definition: BooleMonomial.h:181
BooleMonomial::bool_type operator<=(const BooleMonomial &lhs, const BooleMonomial &rhs)
Less or equal than comparision.
Definition: BooleMonomial.h:300
CTypes::ostream_type ostream_type
Definition: BoolePolynomial.h:103
BooleMonomial LCM(const BooleMonomial &lhs, const BooleMonomial &rhs)
Compute the greatest common divisor of two monomials.
Definition: BooleMonomial.h:322
~BooleMonomial()
Destructor.
Definition: BooleMonomial.h:120
Definition: CTermGenerator.h:151
BooleMonomial::bool_type operator>(const BooleMonomial &lhs, const BooleMonomial &rhs)
Greater than comparision.
Definition: BooleMonomial.h:293
Definition: CTermGenerator.h:34
dd_type::easy_equality_property easy_equality_property
The property whether the equality check is easy is inherited from dd_type.
Definition: BooleMonomial.h:101
poly_type::integer_type integer_type
Definition: BooleMonomial.h:68
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
Compose a binary function with a default constructable unary function for both arguments.
Definition: pbori_func.h:325
BooleMonomial(const self &rhs)
Copy constructor.
Definition: BooleMonomial.h:104
const ring_type & ring() const
Access ring, where this belongs to.
Definition: BooleMonomial.h:235
BooleMonomial(const ring_type &ring)
Construct from given ring.
Definition: BooleMonomial.h:116
bool_type operator!=(constant_type rhs) const
Definition: BooleMonomial.h:184
poly_type::set_type set_type
Type of sets of Boolean variables.
Definition: BooleMonomial.h:79
This class defines an iterator over the first minimal term of a given ZDD node.
Definition: CCuddFirstIter.h:35
BooleMonomial::bool_type operator<(const BooleMonomial &lhs, const BooleMonomial &rhs)
Less than comparision.
Definition: BooleMonomial.h:286
const dd_type & diagram() const
Read-only access to internal decision diagramm structure.
Definition: BooleMonomial.h:213
BoolePolynomial & operator*=(BoolePolynomial &lhs, const BooleVariable &rhs)
Multiplication of a polynomial by a variable with assignment.
Definition: BooleMonomial.h:366
bool_type isOne() const
Definition: BooleMonomial.h:185
size_type size() const
Size of the exponents.
Definition: BooleMonomial.h:151
variable_iterator variableEnd() const
Finish iteration over variables.
Definition: BooleMonomial.h:141
bool_type isConstant() const
Definition: BooleMonomial.h:186
polybori::CTypes::idx_type idx_type
Definition: groebner_defs.h:44
BoolePolynomial operator*(const BoolePolynomial &lhs, const BooleVariable &rhs)
Multiplication of a polynomial by a variable.
Definition: BooleMonomial.h:382
std::size_t size_type
Type for lengths, dimensions, etc.
Definition: pbori_defs.h:219
poly_type::constant_type constant_type
Type of Boolean constants.
Definition: BooleMonomial.h:76
Definition: BooleSet.h:57
This class wraps a bool value, which was not converted to a boolean polynomial or monomial yet...
Definition: BooleConstant.h:40
This class is just a wrapper for using variables from cudd's decicion diagram.
Definition: BooleMonomial.h:50
bool bool_type
Type for standard true/false statements.
Definition: pbori_defs.h:216
hash_type hash() const
Get unique hash value (valid only per runtime)
Definition: BooleMonomial.h:165
This class is just a wrapper for using variables from cudd's decicion diagram.
Definition: BooleVariable.h:39
This class shows, whether a property of an order is valid.
Definition: tags.h:32
bool_type operator!=(const self &rhs) const
Definition: BooleMonomial.h:182