PolyBoRi
pbori_routines_order.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
14 //*****************************************************************************
15 
16 #ifndef polybori_routines_pbori_routines_order_h_
17 #define polybori_routines_pbori_routines_order_h_
18 
19 // include basic definitions
20 #include <polybori/pbori_defs.h>
21 #include "pbori_algo.h"
22 #include <polybori/common/traits.h>
23 
24 
26 
27 template <class FirstIterator, class SecondIterator, class BinaryPredicate>
28 CTypes::comp_type
29 lex_compare_3way(FirstIterator start, FirstIterator finish,
30  SecondIterator rhs_start, SecondIterator rhs_finish,
31  BinaryPredicate idx_comp) {
32 
33  while ( (start != finish) && (rhs_start != rhs_finish) &&
34  (*start == *rhs_start) ) {
35  ++start; ++rhs_start;
36  }
37 
38  if (start == finish) {
39  if (rhs_start == rhs_finish)
40  return CTypes::equality;
41 
42  return CTypes::less_than;
43  }
44 
45  if (rhs_start == rhs_finish)
46  return CTypes::greater_than;
47 
48  return (idx_comp(*start, *rhs_start)?
49  CTypes::greater_than: CTypes::less_than);
50 }
51 
52 
54 template <class LhsType, class RhsType, class BinaryPredicate>
55 CTypes::comp_type
56 lex_compare(const LhsType& lhs, const RhsType& rhs,
57  BinaryPredicate idx_comp, valid_tag has_easy_equality_test) {
58 
59  if (lhs == rhs)
60  return CTypes::equality;
61 
62  return lex_compare_3way(lhs.begin(), lhs.end(),
63  rhs.begin(), rhs.end(), idx_comp);
64  //typedef lex_compare_predicate<LhsType, RhsType, BinaryPredicate> comp_type;
65  //return generic_compare_3way(lhs, rhs, comp_type(idx_comp));
66 }
67 
68 
70 template <class LhsType, class RhsType, class BinaryPredicate>
71 CTypes::comp_type
72 lex_compare(const LhsType& lhs, const RhsType& rhs,
73  BinaryPredicate idx_comp, invalid_tag has_no_easy_equality_test) {
74 
75  return lex_compare_3way(lhs.begin(), lhs.end(),
76  rhs.begin(), rhs.end(), idx_comp);
77 }
78 
80 template <class LhsType, class RhsType, class BinaryPredicate>
81 CTypes::comp_type
82 lex_compare(const LhsType& lhs, const RhsType& rhs, BinaryPredicate idx_comp) {
83 
86 
87  return lex_compare(lhs, rhs, idx_comp, equality_property());
88 }
89 
91 template<class LhsType, class RhsType, class BinaryPredicate>
92 CTypes::comp_type
93 deg_lex_compare(const LhsType& lhs, const RhsType& rhs,
94  BinaryPredicate idx_comp) {
95 
96  typedef typename LhsType::size_type size_type;
97  CTypes::comp_type result = generic_compare_3way( lhs.size(), rhs.size(),
98  std::greater<size_type>() );
99 
100  return (result == CTypes::equality? lex_compare(lhs, rhs, idx_comp): result);
101 }
102 
103 
104 template <class OrderType, class Iterator>
106 
107 template<class DummyType>
109 public:
110  dummy_data_type(const DummyType&) {}
111  dummy_data_type(DummyType&) {}
113 };
114 
116 template <class StackType, class Iterator>
117 void dummy_append(StackType& stack, Iterator start, Iterator finish) {
118 
119  while (start != finish) {
120  stack.push(*start);
121  ++start;
122  }
123 }
124 
125 template<class NaviType, class DescendingProperty = valid_tag>
127 public:
128  typedef NaviType navigator;
129  typedef DescendingProperty descending_property;
131  typedef std::vector<navigator> stack_type;
132  typedef unsigned size_type;
133  typedef unsigned idx_type;
134 
136  m_stack(), m_max_idx(0), m_upperbound(0), m_next() {}
137 
139 
140  bounded_restricted_term (navigator navi, size_type upperbound,
141  idx_type max_idx):
142  m_stack(), m_upperbound(upperbound), m_max_idx(max_idx), m_next(navi) {
143 
144  m_stack.reserve(upperbound);
145 
146  followThen();
147 
148  while (!is_path_end() && !empty() )
149  increment();
150  }
151 
152  size_type operator*() const {
153  return m_stack.size();
154  }
155 
156  const navigator& next() const {
157  return m_next;
158  }
159 
160  typename stack_type::const_iterator begin() const {
161  return m_stack.begin();
162  }
163 
164  typename stack_type::const_iterator end() const {
165  return m_stack.end();
166  }
167 
168  self& operator++() {
169  PBORI_ASSERT(!empty());
170 
171  // if upperbound was already found we're done
172  // (should be optimized away for ascending variables)
173  if (descendingVariables() && (m_stack.size() == m_upperbound) )
174  return *this = self();
175 
176  do {
177  increment();
178  } while (!empty() && !is_path_end());
179 
180  return *this;
181  }
182 
183  void print() const {
184 
185  typename stack_type::const_iterator start(m_stack.begin()),
186  finish(m_stack.end());
187 
188  std::cout <<'(';
189  while (start != finish) {
190  std::cout << *(*start) << ", " ;
191  ++start;
192  }
193  std::cout <<')';
194 
195  }
196 
197  bool operator==(const self& rhs) const {
198  if (rhs.empty())
199  return empty();
200  if (empty())
201  return rhs.empty();
202 
203  else (m_stack == rhs.m_stack);
204  }
205  bool operator!=(const self& rhs) const {
206  return !(*this == rhs);
207  }
208 protected:
209 
210  void followThen() {
211  while (within_degree() && !at_end())
212  nextThen();
213  }
214 
215  void increment() {
216  PBORI_ASSERT(!empty());
217 
218  m_next = top();
219  m_next.incrementElse();
220  m_stack.pop_back();
221 
222  followThen();
223 
224  }
225 
226  bool empty() const{
227  return m_stack.empty();
228  }
229 
230  navigator top() const{
231  return m_stack.back();
232  }
233 
234  bool is_path_end() {
235 
236  path_end();
237  return (!m_next.isConstant() && (*m_next >= m_max_idx)) ||
238  m_next.terminalValue();
239  }
240 
241  void path_end() {
242  while (!at_end()) {
243  m_next.incrementElse();
244  }
245  }
246 
247  void nextThen() {
248  PBORI_ASSERT(!m_next.isConstant());
249  m_stack.push_back(m_next);
250  m_next.incrementThen();
251  }
252 
253 
254 
255  bool within_degree() const {
256 
257  return (*(*this) < m_upperbound);
258  }
259 
260  bool at_end() const {
261 
262  return m_next.isConstant() || (*m_next >= m_max_idx);
263  }
264 
265 private:
266  stack_type m_stack;
267  idx_type m_max_idx;
268  size_type m_upperbound;
269  navigator m_next;
270 };
271 
272 
273 
276 template <class DegreeCacher, class NaviType, class IdxType>
277 typename NaviType::deg_type
278 dd_cached_block_degree(const DegreeCacher& cache, NaviType navi,
279  IdxType nextBlock) {
280 
281  typedef typename NaviType::deg_type deg_type;
282 
283  if( navi.isConstant() || (*navi >= nextBlock) ) // end of block reached
284  return 0;
285 
286  // Look whether result was cached before
287  typename DegreeCacher::node_type result = cache.find(navi, nextBlock);
288  if (result.isValid())
289  return *result;
290 
291  // Get degree of then branch (contains at least one valid path)...
292  deg_type deg = dd_cached_block_degree(cache, navi.thenBranch(), nextBlock) + 1;
293 
294  // ... combine with degree of else branch
295  deg = std::max(deg, dd_cached_block_degree(cache, navi.elseBranch(), nextBlock) );
296 
297  // Write result to cache
298  cache.insert(navi, nextBlock, deg);
299 
300  return deg;
301 }
302 
303 
304 template<class DegCacheMgr, class NaviType, class IdxType, class SizeType>
305 bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi,
306  IdxType next_block,
307  SizeType degree, valid_tag is_descending) {
308  navi.incrementThen();
309  return ((dd_cached_block_degree(deg_mgr, navi, next_block/*,degree - 1*/) + 1) == degree);
310 }
311 
312 template<class DegCacheMgr, class NaviType, class IdxType, class SizeType>
313 bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi,
314  IdxType next_block,
315  SizeType degree, invalid_tag non_descending) {
316  navi.incrementElse();
317  return (dd_cached_block_degree(deg_mgr, navi, next_block/*, degree*/) != degree);
318 }
319 
320 
321 // with degree bound
322 template <class CacheType, class DegCacheMgr, class NaviType,
323  class TermType, class Iterator, class SizeType, class DescendingProperty>
324 TermType
325 dd_block_degree_lead(const CacheType& cache_mgr,
326  const DegCacheMgr& deg_mgr,
327  NaviType navi, Iterator block_iter,
328  TermType init, SizeType degree,
329  DescendingProperty prop) {
330 
331  if (navi.isConstant())
332  return cache_mgr.generate(navi);
333 
334  while( (*navi >= *block_iter) && (*block_iter != CUDD_MAXINDEX)) {
335  ++block_iter;
336  degree = dd_cached_block_degree(deg_mgr, navi, *block_iter);
337  }
338 
339 
340  // Check cache for previous results - Wrong in general, bounds may have changed!
341 // NaviType cached = cache_mgr.find(navi);
342 // if (cached.isValid())
343 // return cache_mgr.generate(cached);
344 
345  // Go to next branch
346  if ( max_block_degree_on_then(deg_mgr, navi, *block_iter, degree, prop) ) {
347  init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.thenBranch(),
348  block_iter,
349  init, degree - 1, prop).change(*navi);
350  }
351  else {
352  init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.elseBranch(),
353  block_iter,
354  init, degree, prop);
355  }
356 
357  NaviType resultNavi(init.navigation());
358  // cache_mgr.insert(navi, resultNavi);
359  deg_mgr.insert(resultNavi, *block_iter, degree);
360 
361  return init;
362 }
363 
364 
365 template <class CacheType, class DegCacheMgr, class NaviType, class Iterator,
366  class TermType, class DescendingProperty>
367 TermType
368 dd_block_degree_lead(const CacheType& cache_mgr, const DegCacheMgr& deg_mgr,
369  NaviType navi, Iterator block_iter, TermType init,
370  DescendingProperty prop){
371 
372  if (navi.isConstant())
373  return cache_mgr.generate(navi);
374 
375  return dd_block_degree_lead(cache_mgr, deg_mgr, navi,block_iter, init,
376  dd_cached_block_degree(deg_mgr, navi,
377  *block_iter), prop);
378 }
379 
380 
381 template <class FirstIterator, class SecondIterator, class IdxType,
382  class BinaryPredicate>
383 CTypes::comp_type
384 restricted_lex_compare_3way(FirstIterator start, FirstIterator finish,
385  SecondIterator rhs_start, SecondIterator rhs_finish,
386  IdxType max_index,
387  BinaryPredicate idx_comp) {
388 
389  while ( (start != finish) && (*start < max_index) && (rhs_start != rhs_finish)
390  && (*rhs_start < max_index) && (*start == *rhs_start) ) {
391  ++start; ++rhs_start;
392  }
393 
394  if ( (start == finish) || (*start >= max_index) ) {
395  if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
396  return CTypes::equality;
397 
398  return CTypes::less_than;
399  }
400 
401  if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
402  return CTypes::greater_than;
403 
404  return (idx_comp(*start, *rhs_start)?
405  CTypes::greater_than: CTypes::less_than);
406 }
407 
408 
409 
410 
411 template<class LhsIterator, class RhsIterator, class Iterator,
412  class BinaryPredicate>
413 CTypes::comp_type
414 block_dlex_compare(LhsIterator lhsStart, LhsIterator lhsFinish,
415  RhsIterator rhsStart, RhsIterator rhsFinish,
416  Iterator start, Iterator finish,
417  BinaryPredicate idx_comp) {
418 
419  // unsigned lhsdeg = 0, rhsdeg = 0;
420 
421 
422  CTypes::comp_type result = CTypes::equality;
423 
424  while ( (start != finish) && (result == CTypes::equality) ) {
425  CTypes::deg_type lhsdeg = 0, rhsdeg = 0;
426  LhsIterator oldLhs(lhsStart); // maybe one can save this and do both
427  RhsIterator oldRhs(rhsStart); // comparisons at once.
428 
429  // maybe one can save
430  while( (lhsStart != lhsFinish) && (*lhsStart < *start) ) {
431  ++lhsStart; ++lhsdeg;
432  }
433  while( (rhsStart != rhsFinish) && (*rhsStart < *start) ) {
434  ++rhsStart; ++rhsdeg;
435  }
436  result = generic_compare_3way(lhsdeg, rhsdeg,
437  std::greater<unsigned>() );
438 
439  if (result == CTypes::equality) {
440  result = restricted_lex_compare_3way(oldLhs, lhsFinish,
441  oldRhs, rhsFinish, *start, idx_comp);
442  }
443 
444  ++start;
445  }
446 
447  return result;
448 }
449 
450 
452 template <class IdxType, class Iterator, class BinaryPredicate>
453 CTypes::comp_type
454 block_deg_lex_idx_compare(IdxType lhs, IdxType rhs,
455  Iterator start, Iterator finish,
456  BinaryPredicate idx_comp) {
457 
458  if (lhs == rhs)
459  return CTypes::equality;
460 
461  Iterator lhsend = std::find_if(start, finish,
462  std::bind2nd(std::greater<IdxType>(), lhs));
463 
464 
465  Iterator rhsend = std::find_if(start, finish,
466  std::bind2nd(std::greater<IdxType>(), rhs));
467 
468  CTypes::comp_type result = CTypes::equality;
469 
470  if PBORI_UNLIKELY( (rhsend == finish) && (lhsend != finish) )
471  result = CTypes::less_than;
472  else if PBORI_UNLIKELY(lhsend == finish)
473  result = CTypes::greater_than;
474  else {
475  PBORI_ASSERT((lhsend != finish) && (rhsend != finish));
476  result = generic_compare_3way( *lhsend, *rhsend, std::less<IdxType>() );
477  }
478 
479  return ( result == CTypes::equality?
480  generic_compare_3way(lhs, rhs, idx_comp): result );
481 }
482 
484 
485 #endif
This class shows, whether a property of an order is invalid.
Definition: tags.h:27
CTypes::comp_type block_dlex_compare(LhsIterator lhsStart, LhsIterator lhsFinish, RhsIterator rhsStart, RhsIterator rhsFinish, Iterator start, Iterator finish, BinaryPredicate idx_comp)
Definition: pbori_routines_order.h:414
dummy_data_type(const DummyType &)
Definition: pbori_routines_order.h:110
navigator top() const
Definition: pbori_routines_order.h:230
bool operator!=(const self &rhs) const
Definition: pbori_routines_order.h:205
stack_type::const_iterator begin() const
Definition: pbori_routines_order.h:160
#define END_NAMESPACE_PBORI
Finish project's namespace.
Definition: pbori_defs.h:77
TermType dd_block_degree_lead(const CacheType &cache_mgr, const DegCacheMgr &deg_mgr, NaviType navi, Iterator block_iter, TermType init, DescendingProperty prop)
Definition: pbori_routines_order.h:368
CTypes::comp_type deg_lex_compare(const LhsType &lhs, const RhsType &rhs, BinaryPredicate idx_comp)
defines degree-lexicographic comparison
Definition: pbori_routines_order.h:93
bool operator==(const self &rhs) const
Definition: pbori_routines_order.h:197
#define BEGIN_NAMESPACE_PBORI
Start project's namespace.
Definition: pbori_defs.h:74
Definition: pbori_routines_order.h:108
DescendingProperty descending_property
Definition: pbori_routines_order.h:129
stack_type::const_iterator end() const
Definition: pbori_routines_order.h:164
int deg_type
Type for polynomial degrees (ranges from -1 to maxint)
Definition: pbori_defs.h:222
This class tests whether two types equal.
Definition: pbori_func.h:571
int deg_type
Definition: groebner_defs.h:42
CTypes::comp_type generic_compare_3way(const LhsType &lhs, const RhsType &rhs, BinaryPredicate comp)
defines lexicographic comparison for variable indices
Definition: pbori_algo.h:633
CTypes::comp_type lex_compare_3way(FirstIterator start, FirstIterator finish, SecondIterator rhs_start, SecondIterator rhs_finish, BinaryPredicate idx_comp)
Definition: pbori_routines_order.h:29
short int comp_type
Type for comparisons.
Definition: pbori_defs.h:237
NaviType navigator
Definition: pbori_routines_order.h:128
Definition: tags.h:66
void dummy_append(StackType &stack, Iterator start, Iterator finish)
Definition: pbori_routines_order.h:117
size_type operator*() const
Definition: pbori_routines_order.h:152
Accessing .change()
const navigator & next() const
Definition: pbori_routines_order.h:156
NaviType::deg_type dd_cached_block_degree(const DegreeCacher &cache, NaviType navi, IdxType nextBlock)
Definition: pbori_routines_order.h:278
bounded_restricted_term(navigator navi, size_type upperbound, idx_type max_idx)
Definition: pbori_routines_order.h:140
bool within_degree() const
Definition: pbori_routines_order.h:255
std::vector< navigator > stack_type
Definition: pbori_routines_order.h:131
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
CTypes::comp_type block_deg_lex_idx_compare(IdxType lhs, IdxType rhs, Iterator start, Iterator finish, BinaryPredicate idx_comp)
Definition: pbori_routines_order.h:454
void nextThen()
Definition: pbori_routines_order.h:247
is_same_type< descending_property, valid_tag > descendingVariables
Definition: pbori_routines_order.h:138
bool max_block_degree_on_then(const DegCacheMgr &deg_mgr, NaviType navi, IdxType next_block, SizeType degree, invalid_tag non_descending)
Definition: pbori_routines_order.h:313
Definition: pbori_routines_order.h:126
bool at_end() const
Definition: pbori_routines_order.h:260
unsigned size_type
Definition: pbori_routines_order.h:132
Definition: pbori_routines_order.h:105
dummy_data_type(DummyType &)
Definition: pbori_routines_order.h:111
self & operator++()
Definition: pbori_routines_order.h:168
void increment()
Definition: pbori_routines_order.h:215
dummy_data_type()
Definition: pbori_routines_order.h:112
bounded_restricted_term()
Definition: pbori_routines_order.h:135
CTypes::comp_type restricted_lex_compare_3way(FirstIterator start, FirstIterator finish, SecondIterator rhs_start, SecondIterator rhs_finish, IdxType max_index, BinaryPredicate idx_comp)
Definition: pbori_routines_order.h:384
void print() const
Definition: pbori_routines_order.h:183
bool is_path_end()
Definition: pbori_routines_order.h:234
bool empty() const
Definition: pbori_routines_order.h:226
unsigned idx_type
Definition: pbori_routines_order.h:133
CTypes::comp_type lex_compare(const LhsType &lhs, const RhsType &rhs, BinaryPredicate idx_comp)
defines lexicographic comparison
Definition: pbori_routines_order.h:82
void path_end()
Definition: pbori_routines_order.h:241
#define PBORI_UNLIKELY(expression)
Definition: pbori_defs.h:59
This class shows, whether a property of an order is valid.
Definition: tags.h:32
void followThen()
Definition: pbori_routines_order.h:210