16 #ifndef polybori_routines_pbori_routines_order_h_
17 #define polybori_routines_pbori_routines_order_h_
27 template <
class FirstIterator,
class SecondIterator,
class BinaryPredicate>
30 SecondIterator rhs_start, SecondIterator rhs_finish,
31 BinaryPredicate idx_comp) {
33 while ( (start != finish) && (rhs_start != rhs_finish) &&
34 (*start == *rhs_start) ) {
38 if (start == finish) {
39 if (rhs_start == rhs_finish)
40 return CTypes::equality;
42 return CTypes::less_than;
45 if (rhs_start == rhs_finish)
46 return CTypes::greater_than;
48 return (idx_comp(*start, *rhs_start)?
49 CTypes::greater_than: CTypes::less_than);
54 template <
class LhsType,
class RhsType,
class BinaryPredicate>
57 BinaryPredicate idx_comp,
valid_tag has_easy_equality_test) {
60 return CTypes::equality;
63 rhs.begin(), rhs.end(), idx_comp);
70 template <
class LhsType,
class RhsType,
class BinaryPredicate>
73 BinaryPredicate idx_comp,
invalid_tag has_no_easy_equality_test) {
76 rhs.begin(), rhs.end(), idx_comp);
80 template <
class LhsType,
class RhsType,
class BinaryPredicate>
82 lex_compare(
const LhsType& lhs,
const RhsType& rhs, BinaryPredicate idx_comp) {
87 return lex_compare(lhs, rhs, idx_comp, equality_property());
91 template<
class LhsType,
class RhsType,
class BinaryPredicate>
94 BinaryPredicate idx_comp) {
96 typedef typename LhsType::size_type size_type;
98 std::greater<size_type>() );
100 return (result == CTypes::equality?
lex_compare(lhs, rhs, idx_comp): result);
104 template <
class OrderType,
class Iterator>
107 template<
class DummyType>
116 template <
class StackType,
class Iterator>
119 while (start != finish) {
125 template<
class NaviType,
class DescendingProperty = val
id_tag>
136 m_stack(), m_max_idx(0), m_upperbound(0), m_next() {}
142 m_stack(), m_upperbound(upperbound), m_max_idx(max_idx), m_next(navi) {
144 m_stack.reserve(upperbound);
148 while (!is_path_end() && !empty() )
153 return m_stack.size();
156 const navigator&
next()
const {
160 typename stack_type::const_iterator
begin()
const {
161 return m_stack.begin();
164 typename stack_type::const_iterator
end()
const {
165 return m_stack.end();
173 if (descendingVariables() && (m_stack.size() == m_upperbound) )
174 return *
this =
self();
178 }
while (!empty() && !is_path_end());
185 typename stack_type::const_iterator start(m_stack.begin()),
186 finish(m_stack.end());
189 while (start != finish) {
190 std::cout << *(*start) <<
", " ;
203 else (m_stack == rhs.m_stack);
206 return !(*
this == rhs);
211 while (within_degree() && !at_end())
219 m_next.incrementElse();
227 return m_stack.empty();
231 return m_stack.back();
237 return (!m_next.isConstant() && (*m_next >= m_max_idx)) ||
238 m_next.terminalValue();
243 m_next.incrementElse();
249 m_stack.push_back(m_next);
250 m_next.incrementThen();
257 return (*(*
this) < m_upperbound);
262 return m_next.isConstant() || (*m_next >= m_max_idx);
268 size_type m_upperbound;
276 template <
class DegreeCacher,
class NaviType,
class IdxType>
283 if( navi.isConstant() || (*navi >= nextBlock) )
287 typename DegreeCacher::node_type result = cache.find(navi, nextBlock);
288 if (result.isValid())
298 cache.insert(navi, nextBlock, deg);
304 template<
class DegCacheMgr,
class NaviType,
class IdxType,
class SizeType>
307 SizeType degree,
valid_tag is_descending) {
308 navi.incrementThen();
312 template<
class DegCacheMgr,
class NaviType,
class IdxType,
class SizeType>
316 navi.incrementElse();
322 template <
class CacheType,
class DegCacheMgr,
class NaviType,
323 class TermType,
class Iterator,
class SizeType,
class DescendingProperty>
326 const DegCacheMgr& deg_mgr,
327 NaviType navi, Iterator block_iter,
328 TermType init, SizeType degree,
329 DescendingProperty prop) {
331 if (navi.isConstant())
332 return cache_mgr.generate(navi);
334 while( (*navi >= *block_iter) && (*block_iter != CUDD_MAXINDEX)) {
349 init, degree - 1, prop).
change(*navi);
357 NaviType resultNavi(init.navigation());
359 deg_mgr.insert(resultNavi, *block_iter, degree);
365 template <
class CacheType,
class DegCacheMgr,
class NaviType,
class Iterator,
366 class TermType,
class DescendingProperty>
369 NaviType navi, Iterator block_iter, TermType init,
370 DescendingProperty prop){
372 if (navi.isConstant())
373 return cache_mgr.generate(navi);
381 template <
class FirstIterator,
class SecondIterator,
class IdxType,
382 class BinaryPredicate>
385 SecondIterator rhs_start, SecondIterator rhs_finish,
387 BinaryPredicate idx_comp) {
389 while ( (start != finish) && (*start < max_index) && (rhs_start != rhs_finish)
390 && (*rhs_start < max_index) && (*start == *rhs_start) ) {
391 ++start; ++rhs_start;
394 if ( (start == finish) || (*start >= max_index) ) {
395 if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
396 return CTypes::equality;
398 return CTypes::less_than;
401 if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
402 return CTypes::greater_than;
404 return (idx_comp(*start, *rhs_start)?
405 CTypes::greater_than: CTypes::less_than);
411 template<
class LhsIterator,
class RhsIterator,
class Iterator,
412 class BinaryPredicate>
415 RhsIterator rhsStart, RhsIterator rhsFinish,
416 Iterator start, Iterator finish,
417 BinaryPredicate idx_comp) {
424 while ( (start != finish) && (result == CTypes::equality) ) {
426 LhsIterator oldLhs(lhsStart);
427 RhsIterator oldRhs(rhsStart);
430 while( (lhsStart != lhsFinish) && (*lhsStart < *start) ) {
431 ++lhsStart; ++lhsdeg;
433 while( (rhsStart != rhsFinish) && (*rhsStart < *start) ) {
434 ++rhsStart; ++rhsdeg;
437 std::greater<unsigned>() );
439 if (result == CTypes::equality) {
441 oldRhs, rhsFinish, *start, idx_comp);
452 template <
class IdxType,
class Iterator,
class BinaryPredicate>
455 Iterator start, Iterator finish,
456 BinaryPredicate idx_comp) {
459 return CTypes::equality;
461 Iterator lhsend = std::find_if(start, finish,
462 std::bind2nd(std::greater<IdxType>(), lhs));
465 Iterator rhsend = std::find_if(start, finish,
466 std::bind2nd(std::greater<IdxType>(), rhs));
471 result = CTypes::less_than;
473 result = CTypes::greater_than;
479 return ( result == CTypes::equality?
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 °_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
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
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 °_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