pbori_routines_order.h
Go to the documentation of this file.
// -*- c++ -*-
//*****************************************************************************
//*****************************************************************************
#ifndef polybori_routines_pbori_routines_order_h_
#define polybori_routines_pbori_routines_order_h_
// include basic definitions
#include <polybori/pbori_defs.h>
#include "pbori_algo.h"
#include <polybori/common/traits.h>
BEGIN_NAMESPACE_PBORI
template <class FirstIterator, class SecondIterator, class BinaryPredicate>
CTypes::comp_type
lex_compare_3way(FirstIterator start, FirstIterator finish,
SecondIterator rhs_start, SecondIterator rhs_finish,
BinaryPredicate idx_comp) {
while ( (start != finish) && (rhs_start != rhs_finish) &&
(*start == *rhs_start) ) {
++start; ++rhs_start;
}
if (start == finish) {
if (rhs_start == rhs_finish)
return CTypes::equality;
return CTypes::less_than;
}
if (rhs_start == rhs_finish)
return CTypes::greater_than;
return (idx_comp(*start, *rhs_start)?
CTypes::greater_than: CTypes::less_than);
}
template <class LhsType, class RhsType, class BinaryPredicate>
CTypes::comp_type
lex_compare(const LhsType& lhs, const RhsType& rhs,
BinaryPredicate idx_comp, valid_tag has_easy_equality_test) {
if (lhs == rhs)
return CTypes::equality;
return lex_compare_3way(lhs.begin(), lhs.end(),
rhs.begin(), rhs.end(), idx_comp);
//typedef lex_compare_predicate<LhsType, RhsType, BinaryPredicate> comp_type;
//return generic_compare_3way(lhs, rhs, comp_type(idx_comp));
}
template <class LhsType, class RhsType, class BinaryPredicate>
CTypes::comp_type
lex_compare(const LhsType& lhs, const RhsType& rhs,
BinaryPredicate idx_comp, invalid_tag has_no_easy_equality_test) {
return lex_compare_3way(lhs.begin(), lhs.end(),
rhs.begin(), rhs.end(), idx_comp);
}
template <class LhsType, class RhsType, class BinaryPredicate>
CTypes::comp_type
lex_compare(const LhsType& lhs, const RhsType& rhs, BinaryPredicate idx_comp) {
typedef typename pbori_binary_traits<LhsType, RhsType>::easy_equality_property
equality_property;
return lex_compare(lhs, rhs, idx_comp, equality_property());
}
template<class LhsType, class RhsType, class BinaryPredicate>
CTypes::comp_type
deg_lex_compare(const LhsType& lhs, const RhsType& rhs,
BinaryPredicate idx_comp) {
typedef typename LhsType::size_type size_type;
CTypes::comp_type result = generic_compare_3way( lhs.size(), rhs.size(),
std::greater<size_type>() );
return (result == CTypes::equality? lex_compare(lhs, rhs, idx_comp): result);
}
template <class OrderType, class Iterator>
class generic_iteration;
template<class DummyType>
class dummy_data_type {
public:
dummy_data_type(const DummyType&) {}
dummy_data_type(DummyType&) {}
dummy_data_type() {}
};
template <class StackType, class Iterator>
void dummy_append(StackType& stack, Iterator start, Iterator finish) {
while (start != finish) {
stack.push(*start);
++start;
}
}
template<class NaviType, class DescendingProperty = valid_tag>
class bounded_restricted_term {
public:
typedef NaviType navigator;
typedef DescendingProperty descending_property;
typedef bounded_restricted_term<navigator, descending_property> self;
typedef std::vector<navigator> stack_type;
typedef unsigned size_type;
typedef unsigned idx_type;
bounded_restricted_term ():
m_stack(), m_max_idx(0), m_upperbound(0), m_next() {}
is_same_type<descending_property, valid_tag> descendingVariables;
bounded_restricted_term (navigator navi, size_type upperbound,
idx_type max_idx):
m_stack(), m_upperbound(upperbound), m_max_idx(max_idx), m_next(navi) {
m_stack.reserve(upperbound);
followThen();
while (!is_path_end() && !empty() )
increment();
}
size_type operator*() const {
return m_stack.size();
}
const navigator& next() const {
return m_next;
}
typename stack_type::const_iterator begin() const {
return m_stack.begin();
}
typename stack_type::const_iterator end() const {
return m_stack.end();
}
self& operator++() {
PBORI_ASSERT(!empty());
// if upperbound was already found we're done
// (should be optimized away for ascending variables)
if (descendingVariables() && (m_stack.size() == m_upperbound) )
return *this = self();
do {
increment();
} while (!empty() && !is_path_end());
return *this;
}
void print() const {
typename stack_type::const_iterator start(m_stack.begin()),
finish(m_stack.end());
std::cout <<'(';
while (start != finish) {
std::cout << *(*start) << ", " ;
++start;
}
std::cout <<')';
}
bool operator==(const self& rhs) const {
if (rhs.empty())
return empty();
if (empty())
return rhs.empty();
else (m_stack == rhs.m_stack);
}
bool operator!=(const self& rhs) const {
return !(*this == rhs);
}
protected:
void followThen() {
while (within_degree() && !at_end())
nextThen();
}
void increment() {
PBORI_ASSERT(!empty());
m_next = top();
m_next.incrementElse();
m_stack.pop_back();
followThen();
}
bool empty() const{
return m_stack.empty();
}
navigator top() const{
return m_stack.back();
}
bool is_path_end() {
path_end();
return (!m_next.isConstant() && (*m_next >= m_max_idx)) ||
m_next.terminalValue();
}
void path_end() {
while (!at_end()) {
m_next.incrementElse();
}
}
void nextThen() {
PBORI_ASSERT(!m_next.isConstant());
m_stack.push_back(m_next);
m_next.incrementThen();
}
bool within_degree() const {
return (*(*this) < m_upperbound);
}
bool at_end() const {
return m_next.isConstant() || (*m_next >= m_max_idx);
}
private:
stack_type m_stack;
idx_type m_max_idx;
size_type m_upperbound;
navigator m_next;
};
template <class DegreeCacher, class NaviType, class IdxType>
typename NaviType::deg_type
dd_cached_block_degree(const DegreeCacher& cache, NaviType navi,
IdxType nextBlock) {
typedef typename NaviType::deg_type deg_type;
if( navi.isConstant() || (*navi >= nextBlock) ) // end of block reached
return 0;
// Look whether result was cached before
typename DegreeCacher::node_type result = cache.find(navi, nextBlock);
if (result.isValid())
return *result;
// Get degree of then branch (contains at least one valid path)...
deg_type deg = dd_cached_block_degree(cache, navi.thenBranch(), nextBlock) + 1;
// ... combine with degree of else branch
deg = std::max(deg, dd_cached_block_degree(cache, navi.elseBranch(), nextBlock) );
// Write result to cache
cache.insert(navi, nextBlock, deg);
return deg;
}
template<class DegCacheMgr, class NaviType, class IdxType, class SizeType>
bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi,
IdxType next_block,
SizeType degree, valid_tag is_descending) {
navi.incrementThen();
return ((dd_cached_block_degree(deg_mgr, navi, next_block/*,degree - 1*/) + 1) == degree);
}
template<class DegCacheMgr, class NaviType, class IdxType, class SizeType>
bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi,
IdxType next_block,
SizeType degree, invalid_tag non_descending) {
navi.incrementElse();
return (dd_cached_block_degree(deg_mgr, navi, next_block/*, degree*/) != degree);
}
// with degree bound
template <class CacheType, class DegCacheMgr, class NaviType,
class TermType, class Iterator, class SizeType, class DescendingProperty>
TermType
dd_block_degree_lead(const CacheType& cache_mgr,
const DegCacheMgr& deg_mgr,
NaviType navi, Iterator block_iter,
TermType init, SizeType degree,
DescendingProperty prop) {
if (navi.isConstant())
return cache_mgr.generate(navi);
while( (*navi >= *block_iter) && (*block_iter != CUDD_MAXINDEX)) {
++block_iter;
degree = dd_cached_block_degree(deg_mgr, navi, *block_iter);
}
// Check cache for previous results - Wrong in general, bounds may have changed!
// NaviType cached = cache_mgr.find(navi);
// if (cached.isValid())
// return cache_mgr.generate(cached);
// Go to next branch
if ( max_block_degree_on_then(deg_mgr, navi, *block_iter, degree, prop) ) {
init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.thenBranch(),
block_iter,
init, degree - 1, prop).change(*navi);
}
else {
init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.elseBranch(),
block_iter,
init, degree, prop);
}
NaviType resultNavi(init.navigation());
// cache_mgr.insert(navi, resultNavi);
deg_mgr.insert(resultNavi, *block_iter, degree);
return init;
}
template <class CacheType, class DegCacheMgr, class NaviType, class Iterator,
class TermType, class DescendingProperty>
TermType
dd_block_degree_lead(const CacheType& cache_mgr, const DegCacheMgr& deg_mgr,
NaviType navi, Iterator block_iter, TermType init,
DescendingProperty prop){
if (navi.isConstant())
return cache_mgr.generate(navi);
return dd_block_degree_lead(cache_mgr, deg_mgr, navi,block_iter, init,
dd_cached_block_degree(deg_mgr, navi,
*block_iter), prop);
}
template <class FirstIterator, class SecondIterator, class IdxType,
class BinaryPredicate>
CTypes::comp_type
restricted_lex_compare_3way(FirstIterator start, FirstIterator finish,
SecondIterator rhs_start, SecondIterator rhs_finish,
IdxType max_index,
BinaryPredicate idx_comp) {
while ( (start != finish) && (*start < max_index) && (rhs_start != rhs_finish)
&& (*rhs_start < max_index) && (*start == *rhs_start) ) {
++start; ++rhs_start;
}
if ( (start == finish) || (*start >= max_index) ) {
if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
return CTypes::equality;
return CTypes::less_than;
}
if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
return CTypes::greater_than;
return (idx_comp(*start, *rhs_start)?
CTypes::greater_than: CTypes::less_than);
}
template<class LhsIterator, class RhsIterator, class Iterator,
class BinaryPredicate>
CTypes::comp_type
block_dlex_compare(LhsIterator lhsStart, LhsIterator lhsFinish,
RhsIterator rhsStart, RhsIterator rhsFinish,
Iterator start, Iterator finish,
BinaryPredicate idx_comp) {
// unsigned lhsdeg = 0, rhsdeg = 0;
CTypes::comp_type result = CTypes::equality;
while ( (start != finish) && (result == CTypes::equality) ) {
CTypes::deg_type lhsdeg = 0, rhsdeg = 0;
LhsIterator oldLhs(lhsStart); // maybe one can save this and do both
RhsIterator oldRhs(rhsStart); // comparisons at once.
// maybe one can save
while( (lhsStart != lhsFinish) && (*lhsStart < *start) ) {
++lhsStart; ++lhsdeg;
}
while( (rhsStart != rhsFinish) && (*rhsStart < *start) ) {
++rhsStart; ++rhsdeg;
}
result = generic_compare_3way(lhsdeg, rhsdeg,
std::greater<unsigned>() );
if (result == CTypes::equality) {
result = restricted_lex_compare_3way(oldLhs, lhsFinish,
oldRhs, rhsFinish, *start, idx_comp);
}
++start;
}
return result;
}
template <class IdxType, class Iterator, class BinaryPredicate>
CTypes::comp_type
block_deg_lex_idx_compare(IdxType lhs, IdxType rhs,
Iterator start, Iterator finish,
BinaryPredicate idx_comp) {
if (lhs == rhs)
return CTypes::equality;
Iterator lhsend = std::find_if(start, finish,
std::bind2nd(std::greater<IdxType>(), lhs));
Iterator rhsend = std::find_if(start, finish,
std::bind2nd(std::greater<IdxType>(), rhs));
CTypes::comp_type result = CTypes::equality;
if PBORI_UNLIKELY( (rhsend == finish) && (lhsend != finish) )
result = CTypes::less_than;
else if PBORI_UNLIKELY(lhsend == finish)
result = CTypes::greater_than;
else {
PBORI_ASSERT((lhsend != finish) && (rhsend != finish));
result = generic_compare_3way( *lhsend, *rhsend, std::less<IdxType>() );
}
return ( result == CTypes::equality?
generic_compare_3way(lhs, rhs, idx_comp): result );
}
END_NAMESPACE_PBORI
#endif
polybori::invalid_tag
This class shows, whether a property of an order is invalid.
Definition: tags.h:27
polybori::block_dlex_compare
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
polybori::dummy_data_type::dummy_data_type
dummy_data_type(const DummyType &)
Definition: pbori_routines_order.h:110
polybori::bounded_restricted_term::top
navigator top() const
Definition: pbori_routines_order.h:230
polybori::bounded_restricted_term::operator!=
bool operator!=(const self &rhs) const
Definition: pbori_routines_order.h:205
polybori::bounded_restricted_term::begin
stack_type::const_iterator begin() const
Definition: pbori_routines_order.h:160
END_NAMESPACE_PBORI
#define END_NAMESPACE_PBORI
Finish project's namespace.
Definition: pbori_defs.h:77
polybori::dd_block_degree_lead
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
polybori::deg_lex_compare
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
polybori::bounded_restricted_term::operator==
bool operator==(const self &rhs) const
Definition: pbori_routines_order.h:197
BEGIN_NAMESPACE_PBORI
#define BEGIN_NAMESPACE_PBORI
Start project's namespace.
Definition: pbori_defs.h:74
polybori::dummy_data_type
Definition: pbori_routines_order.h:108
polybori::bounded_restricted_term::descending_property
DescendingProperty descending_property
Definition: pbori_routines_order.h:129
polybori::bounded_restricted_term::end
stack_type::const_iterator end() const
Definition: pbori_routines_order.h:164
polybori::CAuxTypes::deg_type
int deg_type
Type for polynomial degrees (ranges from -1 to maxint)
Definition: pbori_defs.h:222
polybori::is_same_type
This class tests whether two types equal.
Definition: pbori_func.h:571
polybori::groebner::deg_type
int deg_type
Definition: groebner_defs.h:42
polybori::generic_compare_3way
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
polybori::lex_compare_3way
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
polybori::CAuxTypes::comp_type
short int comp_type
Type for comparisons.
Definition: pbori_defs.h:237
polybori::bounded_restricted_term::navigator
NaviType navigator
Definition: pbori_routines_order.h:128
polybori::equality_property
Definition: tags.h:66
polybori::dummy_append
void dummy_append(StackType &stack, Iterator start, Iterator finish)
Definition: pbori_routines_order.h:117
traits.h
polybori::bounded_restricted_term::operator*
size_type operator*() const
Definition: pbori_routines_order.h:152
change
Accessing .change()
polybori::bounded_restricted_term::next
const navigator & next() const
Definition: pbori_routines_order.h:156
polybori::dd_cached_block_degree
NaviType::deg_type dd_cached_block_degree(const DegreeCacher &cache, NaviType navi, IdxType nextBlock)
Definition: pbori_routines_order.h:278
polybori::bounded_restricted_term::bounded_restricted_term
bounded_restricted_term(navigator navi, size_type upperbound, idx_type max_idx)
Definition: pbori_routines_order.h:140
polybori::bounded_restricted_term::within_degree
bool within_degree() const
Definition: pbori_routines_order.h:255
pbori_defs.h
polybori::bounded_restricted_term::stack_type
std::vector< navigator > stack_type
Definition: pbori_routines_order.h:131
PBORI_ASSERT
#define PBORI_ASSERT(arg)
Definition: pbori_defs.h:118
polybori::block_deg_lex_idx_compare
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
polybori::bounded_restricted_term::nextThen
void nextThen()
Definition: pbori_routines_order.h:247
polybori::bounded_restricted_term::descendingVariables
is_same_type< descending_property, valid_tag > descendingVariables
Definition: pbori_routines_order.h:138
polybori::max_block_degree_on_then
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
polybori::bounded_restricted_term
Definition: pbori_routines_order.h:126
polybori::bounded_restricted_term::at_end
bool at_end() const
Definition: pbori_routines_order.h:260
polybori::bounded_restricted_term::size_type
unsigned size_type
Definition: pbori_routines_order.h:132
polybori::generic_iteration
Definition: pbori_routines_order.h:105
polybori::dummy_data_type::dummy_data_type
dummy_data_type(DummyType &)
Definition: pbori_routines_order.h:111
polybori::bounded_restricted_term::operator++
self & operator++()
Definition: pbori_routines_order.h:168
polybori::bounded_restricted_term::increment
void increment()
Definition: pbori_routines_order.h:215
polybori::dummy_data_type::dummy_data_type
dummy_data_type()
Definition: pbori_routines_order.h:112
polybori::bounded_restricted_term::bounded_restricted_term
bounded_restricted_term()
Definition: pbori_routines_order.h:135
polybori::restricted_lex_compare_3way
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
polybori::bounded_restricted_term::print
void print() const
Definition: pbori_routines_order.h:183
pbori_algo.h
polybori::bounded_restricted_term::is_path_end
bool is_path_end()
Definition: pbori_routines_order.h:234
polybori::bounded_restricted_term::empty
bool empty() const
Definition: pbori_routines_order.h:226
polybori::bounded_restricted_term::idx_type
unsigned idx_type
Definition: pbori_routines_order.h:133
polybori::lex_compare
CTypes::comp_type lex_compare(const LhsType &lhs, const RhsType &rhs, BinaryPredicate idx_comp)
defines lexicographic comparison
Definition: pbori_routines_order.h:82
polybori::bounded_restricted_term::path_end
void path_end()
Definition: pbori_routines_order.h:241
PBORI_UNLIKELY
#define PBORI_UNLIKELY(expression)
Definition: pbori_defs.h:59
polybori::valid_tag
This class shows, whether a property of an order is valid.
Definition: tags.h:32
polybori::bounded_restricted_term::followThen
void followThen()
Definition: pbori_routines_order.h:210