PolyBoRi
OrderedManager.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
114 //*****************************************************************************
115 
116 // include basic definitions
117 #include "pbori_defs.h"
118 
119 // get decision diagram manager interface
120 #include "CDDManager.h"
121 
122 #include "BoolePolynomial.h"
123 
124 #include "BooleMonomial.h"
125 
126 #include "BooleExponent.h"
127 
128 #include "COrderProperties.h"
129 #include "CVariableNames.h"
130 
131 #include "CGenericIter.h"
132 
133  //#include "CIndirectIter.h"
134 
135 
136 
137 
138 #include <vector>
139 #ifndef OrderedManager_h_
140 #define OrderedManager_h_
141 #include "COrderedIter.h"
143 
144 template <class IdxType, class OrderType>
145 bool
146 lie_in_same_block(IdxType, IdxType, const OrderType&,
147  invalid_tag) { // not a block order
148  return true;
149 }
150 
151 
152 template <class IdxType, class OrderType>
153 bool
154 lie_in_same_block(IdxType first, IdxType second, const OrderType& order,
155  valid_tag) { // is block order
156  if (second < first)
157  std::swap(first, second);
158 
159  typename OrderType::block_iterator upper(order.blockBegin());
160  while (first >= *upper) // Note: convention, last element is max_idx
161  ++upper;
162  return (second < *upper);
163 }
164 
170 // template <class ManType>
171 // class CNamedManager:
172 // public CDDManager<ManType> {
173 
174 // public:
175 
176 // /// Variable manager type
177 // typedef ManType manager_type;
178 
179 // /// Variable manager interface (base type)
180 // typedef CDDManager<manager_type> base;
181 
182 // /// Type of *this
183 // typedef CNamedManager<manager_type> self;
184 
185 // /// @name adopt global type definitions
186 // //@{
187 // typedef CTypes::bool_type bool_type;
188 // typedef CTypes::dd_type dd_type;
189 // typedef CTypes::size_type size_type;
190 // typedef CTypes::idx_type idx_type;
191 // typedef CTypes::comp_type comp_type;
192 // typedef CTypes::ordercode_type ordercode_type;
193 // typedef BooleMonomial monom_type;
194 // typedef BoolePolynomial poly_type;
195 // typedef BoolePolynomial::navigator navigator;
196 // typedef BooleExponent exp_type;
197 // //@}
198 
199 // /// Define type for storing names of variables
200 // typedef CVariableNames variable_names_type;
201 
202 // /// Define type for getting names of variables
203 // typedef variable_names_type::const_reference const_varname_reference;
204 
205 // /// Construct new decision diagramm manager
206 // CNamedManager(size_type nvars = 0):
207 // base(nvars) { }
208 
209 // /// Construct old decision diagramm manager
210 // CNamedManager(const base& rhs):
211 // base(rhs) { }
212 
213 
214 // /// Construct new decision diagramm manager
215 // CNamedManager(const self& rhs):
216 // base(rhs) { }
217 
218 // // Destructor
219 // ~CNamedManager() { }
220 
221 // /// Set name of variable with index idx
222 // void setVariableName(idx_type idx, const_varname_reference varname) {
223 // base::manager().names().set(idx, varname);
224 // }
225 
226 // /// Get name of variable with index idx
227 // const_varname_reference getVariableName(idx_type idx) const {
228 // return base::manager().names()[idx];
229 // }
230 
231 // private:
232 // /// Stores names of variables
233 // //variable_names_type m_names;
234 // };
235 
236 
243 class CDynamicOrderBase {
244 
245 public:
246 
248  typedef CDynamicOrderBase self;
249 
251 
252  typedef CTypes::bool_type bool_type;
253  typedef CTypes::size_type size_type;
254  typedef CTypes::idx_type idx_type;
255  typedef CTypes::comp_type comp_type;
256  typedef CTypes::ordercode_type ordercode_type;
257  typedef BoolePolynomial poly_type;
258  typedef poly_type::monom_type monom_type;
259  typedef poly_type::navigator navigator;
260  typedef poly_type::exp_type exp_type;
261 
262 
263  typedef COrderedIter<navigator, monom_type> ordered_iterator;
264  typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
266 
268  typedef std::vector<idx_type> block_idx_type;
269 
271  typedef block_idx_type::const_iterator block_iterator;
272 
273 
275  CDynamicOrderBase() { }
276 
277  // Destructor
278  virtual ~CDynamicOrderBase() { }
279 
281  virtual comp_type compare(idx_type, idx_type) const = 0;
282 
283  virtual comp_type compare(const monom_type&, const monom_type&) const = 0;
284 
285  virtual comp_type compare(const exp_type&, const exp_type&) const = 0;
286 
288  virtual monom_type lead(const poly_type&) const = 0;
289 
291  virtual monom_type lead(const poly_type&, size_type) const = 0;
292 
294  virtual exp_type leadExp(const poly_type&) const = 0;
295 
297  virtual exp_type leadExp(const poly_type&, size_type) const = 0;
298 
300  virtual poly_type leadFirst(const poly_type&) const = 0;
301 
303  virtual bool_type isLexicographical() const = 0;
304 
306  virtual bool_type orderedStandardIteration() const = 0;
307 
309  virtual bool_type isSymmetric() const = 0;
310 
312  virtual bool_type isDegreeOrder() const = 0;
313 
315  virtual bool_type isBlockOrder() const = 0;
316 
318  virtual bool_type isTotalDegreeOrder() const = 0;
319 
321  virtual bool_type ascendingVariables() const = 0;
322 
324  virtual bool_type descendingVariables() const = 0;
325 
327  virtual bool_type isDegreeReverseLexicograpical() const = 0;
328 
330  virtual ordered_iterator leadIteratorBegin(const poly_type&) const = 0;
331 
332  virtual ordered_iterator leadIteratorEnd() const = 0;
333  virtual ordered_exp_iterator leadExpIteratorBegin(const poly_type&) const = 0;
334 
335  virtual ordered_exp_iterator leadExpIteratorEnd() const = 0;
336 
338  virtual ordercode_type getOrderCode() const = 0;
339 
341  virtual ordercode_type getBaseOrderCode() const = 0 ;
342 
344 
345  virtual block_iterator blockBegin() const = 0;
346  virtual block_iterator blockEnd() const = 0;
347  virtual void appendBlock(idx_type) = 0;
348  virtual void clearBlocks() = 0;
350 
353  virtual bool_type lieInSameBlock(idx_type, idx_type) const = 0;
354 
355 };
356 
363 template <class OrderType>
364 class CDynamicOrder:
365  public CDynamicOrderBase {
366 
367 public:
368 
369 
371  typedef OrderType order_type;
372 
374  typedef CDynamicOrderBase base;
375 
377  typedef CDynamicOrder<order_type> self;
378 
380  typedef COrderProperties<order_type> properties_type;
381 
383 
384  typedef typename base::bool_type bool_type;
385  typedef typename base::size_type size_type;
386  typedef typename base::idx_type idx_type;
387  typedef typename base::comp_type comp_type;
388  typedef typename base::monom_type monom_type;
389  typedef typename base::poly_type poly_type;
390  typedef typename base::exp_type exp_type;
391  typedef typename base::ordered_iterator ordered_iterator;
392  typedef typename base::ordered_exp_iterator ordered_exp_iterator;
393  typedef typename base::ordercode_type ordercode_type;
394  typedef typename base::block_iterator block_iterator;
396 
398  CDynamicOrder( const order_type& theOrder = order_type() ):
399  ordering(theOrder) { }
400 
402  CDynamicOrder(const self& rhs):
403  ordering(rhs.ordering) { }
404 
405  // Destructor
406  ~CDynamicOrder() { }
407 
409  comp_type compare(idx_type lhs, idx_type rhs) const {
410  return ordering.compare(lhs, rhs);
411  }
412 
414  comp_type compare(const monom_type& lhs, const monom_type& rhs) const {
415  return ordering.compare(lhs, rhs);
416  }
417 
418  comp_type compare(const exp_type& lhs, const exp_type& rhs) const {
419  return ordering.compare(lhs, rhs);
420  }
421 
423  monom_type lead(const poly_type& rhs) const {
424 
425  return ordering.lead(rhs);
426  }
428  monom_type lead(const poly_type& rhs, size_type bound) const {
429 
430  return ordering.lead(rhs, bound);
431  }
432 
434  exp_type leadExp(const poly_type& rhs) const {
435 
436  return ordering.leadExp(rhs);
437  }
438 
440  exp_type leadExp(const poly_type& rhs, size_type bound) const {
441 
442  return ordering.leadExp(rhs, bound);
443  }
444 
446  poly_type leadFirst(const poly_type& poly) const {
447 
448  if(orderedStandardIteration())
449  return poly;
450  else
451  return lead(poly);
452  }
453 
455  bool_type isLexicographical() const {
456  return properties_type().isLexicographical();
457  }
458 
460  bool_type orderedStandardIteration() const {
461  return properties_type().orderedStandardIteration();
462  }
463 
465  bool_type isSymmetric() const {
466  return properties_type().isSymmetric();
467  }
468 
470  bool_type isDegreeOrder() const {
471  return properties_type().isDegreeOrder();
472  }
473 
475  bool_type isBlockOrder() const {
476  return properties_type().isBlockOrder();
477  }
478 
480  bool_type isTotalDegreeOrder() const {
481  return properties_type().isTotalDegreeOrder();
482  }
483 
485  bool_type isDegreeReverseLexicograpical() const {
486  return properties_type().isDegreeReverseLexicograpical();
487  }
488 
490  bool_type ascendingVariables() const {
491  return properties_type().ascendingVariables();
492  }
493 
495  bool_type descendingVariables() const {
496  return properties_type().descendingVariables();
497  }
498 
500  // iterator leadIterator(const poly_type& poly) const {
501  // return ordering.leadIterator(poly);
502  // }
504  ordered_iterator leadIteratorBegin(const poly_type& poly) const {
505  return ordering.leadIteratorBegin(poly);
506  }
507 
508  ordered_iterator leadIteratorEnd() const {
509  return ordering.leadIteratorEnd();
510  }
512  ordered_exp_iterator leadExpIteratorBegin(const poly_type& poly) const {
513  return ordering.leadExpIteratorBegin(poly);
514  }
515 
516  ordered_exp_iterator leadExpIteratorEnd() const {
517  return ordering.leadExpIteratorEnd();
518  }
519 
521  ordercode_type getOrderCode() const {
522  return order_type::order_code;
523  }
524 
526  ordercode_type getBaseOrderCode() const {
527  return order_type::baseorder_code;
528  }
529 
531 
532  block_iterator blockBegin() const { return ordering.blockBegin(); }
533  block_iterator blockEnd() const { return ordering.blockEnd(); }
534  void appendBlock(idx_type idx) { ordering.appendBlock(idx); }
535  void clearBlocks() { ordering.clearBlocks(); }
537 
540  bool_type lieInSameBlock(idx_type first, idx_type second) const {
541  return lie_in_same_block(first, second, *this,
542  typename properties_type::blockorder_property());
543  }
544 
545 protected:
546  order_type ordering;
547 };
548 
550 
551 #endif