BoolePolynomial.h
Go to the documentation of this file.
// -*- c++ -*-
//*****************************************************************************
//*****************************************************************************
#ifndef polybori_BoolePolynomial_h_
#define polybori_BoolePolynomial_h_
// include standard definitions
#include <vector>
// get standard map functionality
#include <map>
// get standard algorithmic functionalites
#include <algorithm>
#include <polybori/BoolePolyRing.h>
// include definition of sets of Boolean variables
#include <polybori/routines/pbori_func.h>
#include <polybori/common/tags.h>
#include <polybori/BooleSet.h>
#include <polybori/iterators/CTermIter.h>
#include <polybori/iterators/CGenericIter.h>
#include <polybori/iterators/CBidirectTermIter.h>
#include <polybori/BooleConstant.h>
BEGIN_NAMESPACE_PBORI
// forward declarations
class LexOrder;
class DegLexOrder;
class DegRevLexAscOrder;
class BlockDegLexOrder;
class BlockDegRevLexAscOrder;
class BooleMonomial;
class BooleVariable;
class BooleExponent;
template <class IteratorType, class MonomType>
class CIndirectIter;
template <class IteratorType, class MonomType>
class COrderedIter;
//template<class, class, class, class> class CGenericIter;
template<class, class, class, class> class CDelayedTermIter;
template<class OrderType, class NavigatorType, class MonomType>
class CGenericIter;
template<class NavigatorType, class ExpType>
class CExpIter;
class BoolePolynomial;
BoolePolynomial
operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);
class BoolePolynomial:
public CAuxTypes{
public:
friend class BooleMonomial;
//-------------------------------------------------------------------------
// types definitions
//-------------------------------------------------------------------------
typedef BoolePolynomial self;
typedef BooleSet dd_type;
typedef CTypes::ostream_type ostream_type;
typedef dd_type::first_iterator first_iterator;
typedef dd_type::navigator navigator;
typedef BooleMonomial monom_type;
typedef BooleVariable var_type;
typedef BooleExponent exp_type;
typedef BooleConstant constant_type;
typedef BoolePolyRing ring_type;
typedef CTypes::comp_type comp_type;
typedef
binary_composition< std::plus<size_type>,
project_ith<1>, integral_constant<size_type, 1> >
increment_type;
typedef
binary_composition< std::minus<size_type>,
project_ith<1>, integral_constant<size_type, 1> >
decrement_type;
// typedef COrderedIter<exp_type> ordered_exp_iterator;
typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
// typedef COrderedIter<monom_type> ordered_iterator;
typedef COrderedIter<navigator, monom_type> ordered_iterator;
typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
typedef CGenericIter<DegLexOrder, navigator, monom_type> dlex_iterator;
typedef CGenericIter<DegRevLexAscOrder, navigator, monom_type>
dp_asc_iterator;
typedef CGenericIter<BlockDegLexOrder, navigator, monom_type>
block_dlex_iterator;
typedef CGenericIter<BlockDegRevLexAscOrder, navigator, monom_type>
block_dp_asc_iterator;
typedef CGenericIter<LexOrder, navigator, exp_type> lex_exp_iterator;
typedef CGenericIter<DegLexOrder, navigator, exp_type> dlex_exp_iterator;
typedef CGenericIter<DegRevLexAscOrder, navigator, exp_type>
dp_asc_exp_iterator;
typedef CGenericIter<BlockDegLexOrder, navigator, exp_type>
block_dlex_exp_iterator;
typedef CGenericIter<BlockDegRevLexAscOrder, navigator, exp_type>
block_dp_asc_exp_iterator;
typedef lex_iterator const_iterator;
typedef CExpIter<navigator, exp_type> exp_iterator;
typedef CGenericIter<LexOrder, navigator, deg_type> deg_iterator;
typedef std::vector<monom_type> termlist_type;
typedef dd_type::easy_equality_property easy_equality_property;
typedef BooleSet set_type;
typedef std::map<self, idx_type, symmetric_composition<
std::less<navigator>, navigates<self> > > idx_map_type;
typedef std::map<self, std::vector<self>, symmetric_composition<
std::less<navigator>, navigates<self> > > poly_vec_map_type;
//-------------------------------------------------------------------------
// constructors and destructor
//-------------------------------------------------------------------------
// BoolePolynomial();
// explicit BoolePolynomial(constant_type);
BoolePolynomial(const ring_type& ring):
m_dd(ring.zero() ) { }
BoolePolynomial(constant_type isOne, const ring_type& ring):
m_dd(isOne? ring.one(): ring.zero() ) { }
BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}
// BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}
BoolePolynomial(const exp_type&, const ring_type&);
BoolePolynomial(const navigator& rhs, const ring_type& ring):
m_dd(ring, rhs) {
PBORI_ASSERT(rhs.isValid());
}
~BoolePolynomial() {}
//-------------------------------------------------------------------------
// operators and member functions
//-------------------------------------------------------------------------
// self& operator=(const self& rhs) {
// return m_dd = rhs.m_dd;
// }
self& operator=(constant_type rhs) {
return (*this) = self(rhs, ring());
}
const self& operator-() const { return *this; }
self& operator+=(const self&);
self& operator+=(constant_type rhs) {
//return *this = (self(*this) + (rhs).generate(*this));
if (rhs) (*this) = (*this + ring().one());
return *this;
}
template <class RHSType>
self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
self& operator*=(const monom_type&);
self& operator*=(const exp_type&);
self& operator*=(const self&);
self& operator*=(constant_type rhs) {
if (!rhs) *this = ring().zero();
return *this;
}
self& operator/=(const var_type&);
self& operator/=(const monom_type&);
self& operator/=(const exp_type&);
self& operator/=(const self& rhs);
self& operator/=(constant_type rhs);
self& operator%=(const var_type&);
self& operator%=(const monom_type&);
self& operator%=(const self& rhs) {
return (*this) -= (self(rhs) *= (self(*this) /= rhs));
}
self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }
bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
bool_type operator==(constant_type rhs) const {
return ( rhs? isOne(): isZero() );
}
bool_type operator!=(constant_type rhs) const {
//return ( rhs? (!(isOne())): (!(isZero())) );
return (!(*this==rhs));
}
bool_type isZero() const { return m_dd.isZero(); }
bool_type isOne() const { return m_dd.isOne(); }
bool_type isConstant() const { return m_dd.isConstant(); }
bool_type hasConstantPart() const { return m_dd.ownsOne(); }
bool_type firstReducibleBy(const self&) const;
monom_type lead() const;
monom_type lexLead() const;
monom_type boundedLead(deg_type bound) const;
exp_type leadExp() const;
exp_type boundedLeadExp(deg_type bound) const;
set_type leadDivisors() const { return leadFirst().firstDivisors(); };
hash_type hash() const { return m_dd.hash(); }
hash_type stableHash() const { return m_dd.stableHash(); }
hash_type leadStableHash() const;
deg_type deg() const;
deg_type leadDeg() const;
deg_type lexLeadDeg() const;
deg_type totalDeg() const;
deg_type leadTotalDeg() const;
self gradedPart(deg_type deg) const;
size_type nNodes() const;
size_type nUsedVariables() const;
monom_type usedVariables() const;
exp_type usedVariablesExp() const;
size_type length() const;
ostream_type& print(ostream_type&) const;
const_iterator begin() const;
const_iterator end() const;
exp_iterator expBegin() const;
exp_iterator expEnd() const;
first_iterator firstBegin() const;
first_iterator firstEnd() const;
monom_type firstTerm() const;
deg_iterator degBegin() const;
deg_iterator degEnd() const;
ordered_iterator orderedBegin() const;
ordered_iterator orderedEnd() const;
ordered_exp_iterator orderedExpBegin() const;
ordered_exp_iterator orderedExpEnd() const;
lex_iterator genericBegin(lex_tag) const;
lex_iterator genericEnd(lex_tag) const;
dlex_iterator genericBegin(dlex_tag) const;
dlex_iterator genericEnd(dlex_tag) const;
dp_asc_iterator genericBegin(dp_asc_tag) const;
dp_asc_iterator genericEnd(dp_asc_tag) const;
block_dlex_iterator genericBegin(block_dlex_tag) const;
block_dlex_iterator genericEnd(block_dlex_tag) const;
block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;
lex_exp_iterator genericExpBegin(lex_tag) const;
lex_exp_iterator genericExpEnd(lex_tag) const;
dlex_exp_iterator genericExpBegin(dlex_tag) const;
dlex_exp_iterator genericExpEnd(dlex_tag) const;
dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;
navigator navigation() const { return m_dd.navigation(); }
navigator endOfNavigation() const { return navigator(); }
dd_type copyDiagram(){ return diagram(); }
operator set_type() const { return set(); };
size_type eliminationLength() const;
size_type eliminationLengthWithDegBound(deg_type garantied_deg_bound) const;
void fetchTerms(termlist_type&) const;
termlist_type terms() const;
const dd_type& diagram() const { return m_dd; }
set_type set() const { return m_dd; }
bool_type isSingleton() const { return dd_is_singleton(navigation()); }
bool_type isSingletonOrPair() const {
return dd_is_singleton_or_pair(navigation());
}
bool_type isPair() const { return dd_is_pair(navigation()); }
const ring_type& ring() const { return m_dd.ring(); }
comp_type compare(const self&) const;
bool_type inSingleBlock() const;
protected:
dd_type& internalDiagram() { return m_dd; }
self leadFirst() const;
set_type firstDivisors() const;
private:
dd_type m_dd;
};
inline BoolePolynomial
operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {
return BoolePolynomial(lhs) += rhs;
}
inline BoolePolynomial
operator+(const BoolePolynomial& lhs, BooleConstant rhs) {
return BoolePolynomial(lhs) += (rhs);
//return BoolePolynomial(lhs) += BoolePolynomial(rhs);
}
inline BoolePolynomial
operator+(BooleConstant lhs, const BoolePolynomial& rhs) {
return BoolePolynomial(rhs) += (lhs);
}
template <class RHSType>
inline BoolePolynomial
operator-(const BoolePolynomial& lhs, const RHSType& rhs) {
return BoolePolynomial(lhs) -= rhs;
}
inline BoolePolynomial
operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {
return -(BoolePolynomial(rhs) -= lhs);
}
#define PBORI_RHS_MULT(type) inline BoolePolynomial \
operator*(const BoolePolynomial& lhs, const type& rhs) { \
return BoolePolynomial(lhs) *= rhs; }
PBORI_RHS_MULT(BoolePolynomial)
PBORI_RHS_MULT(BooleMonomial)
PBORI_RHS_MULT(BooleExponent)
PBORI_RHS_MULT(BooleConstant)
#undef PBORI_RHS_MULT
#define PBORI_LHS_MULT(type) inline BoolePolynomial \
operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }
PBORI_LHS_MULT(BooleMonomial)
PBORI_LHS_MULT(BooleExponent)
PBORI_LHS_MULT(BooleConstant)
#undef PBORI_LHS_MULT
template <class RHSType>
inline BoolePolynomial
operator/(const BoolePolynomial& lhs, const RHSType& rhs){
return BoolePolynomial(lhs) /= rhs;
}
template <class RHSType>
inline BoolePolynomial
operator%(const BoolePolynomial& lhs, const RHSType& rhs){
return BoolePolynomial(lhs) %= rhs;
}
inline BoolePolynomial::bool_type
operator==(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
return (rhs == lhs);
}
inline BoolePolynomial::bool_type
operator!=(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {
return (rhs != lhs);
}
BoolePolynomial::ostream_type&
operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);
// tests whether polynomial can be reduced by rhs
inline BoolePolynomial::bool_type
BoolePolynomial::firstReducibleBy(const self& rhs) const {
if( rhs.isOne() )
return true;
if( isZero() )
return rhs.isZero();
return std::includes(firstBegin(), firstEnd(),
rhs.firstBegin(), rhs.firstEnd());
}
END_NAMESPACE_PBORI
#endif // of polybori_BoolePolynomial_h_