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();
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?