PolyBoRi
Public Types | Public Member Functions | Protected Member Functions | Friends
polybori::BoolePolynomial Class Reference

This class wraps the underlying decicion diagram type and defines the necessary operations. More...

#include <BoolePolynomial.h>

Inheritance diagram for polybori::BoolePolynomial:
polybori::CAuxTypes

List of all members.

Public Types

typedef BoolePolynomial self
 Generic access to current type.
typedef dd_type::first_iterator first_iterator
 Iterator type for iterating over indices of the leading term.
typedef dd_type::navigator navigator
 Iterator-like type for navigating through diagram structure.
typedef BooleMonomial monom_type
 Fix type for treatment of monomials.
typedef BooleVariable var_type
 Fix type for treatment of monomials.
typedef BooleExponent exp_type
 Fix type for treatment of exponent vectors.
typedef BooleConstant constant_type
 Type for wrapping integer and bool values.
typedef BoolePolyRing ring_type
 Type for Boolean polynomial rings (without ordering)
typedef CTypes::comp_type comp_type
 Type for result of polynomial comparisons.
typedef binary_composition
< std::plus< size_type >
, project_ith
< 1 >, integral_constant
< size_type, 1 > > 
increment_type
 Incrementation functional type.
typedef binary_composition
< std::minus< size_type >
, project_ith
< 1 >, integral_constant
< size_type, 1 > > 
decrement_type
 Decrementation functional type.
typedef COrderedIter
< navigator, exp_type
ordered_exp_iterator
 Iterator type for iterating over all exponents in ordering order.
typedef COrderedIter
< navigator, monom_type
ordered_iterator
 Iterator type for iterating over all monomials in ordering order.
typedef lex_iterator const_iterator
 Iterator type for iterating over all monomials.
typedef CExpIter< navigator,
exp_type
exp_iterator
 Iterator type for iterating all exponent vectors.
typedef CGenericIter< LexOrder,
navigator, deg_type
deg_iterator
 Iterator type for iterating all monomials (dereferencing to degree)
typedef std::vector< monom_typetermlist_type
 Type for lists of terms.
typedef
dd_type::easy_equality_property 
easy_equality_property
 The property whether the equality check is easy is inherited from dd_type.
typedef BooleSet set_type
 Type for sets of Boolean variables.
typedef std::map< self,
idx_type,
symmetric_composition
< std::less< navigator >
, navigates< self > > > 
idx_map_type
 Type for index maps.
typedef std::map< self,
std::vector< self >
, symmetric_composition
< std::less< navigator >
, navigates< self > > > 
poly_vec_map_type
Adopt global type definitions
typedef BooleSet dd_type
typedef CTypes::ostream_type ostream_type
 Type for out-stream.
Generic iterators for various orderings
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

Public Member Functions

 BoolePolynomial ()
 Default constructor.
 BoolePolynomial (constant_type)
 Construct polynomial from a constant value 0 or 1.
 BoolePolynomial (constant_type isOne, const ring_type &ring)
 Construct polynomial from a constant value 0 or 1.
 BoolePolynomial (const dd_type &rhs)
 Construct polynomial from decision diagram.
 BoolePolynomial (const exp_type &, const ring_type &)
 Construct polynomial from a subset of the powerset over all variables.
 BoolePolynomial (const navigator &rhs, const ring_type &ring)
 Construct polynomial from navigator.
 ~BoolePolynomial ()
 Destructor.
selfoperator= (constant_type rhs)
bool_type isZero () const
 Check whether polynomial is constant zero.
bool_type isOne () const
 Check whether polynomial is constant one.
bool_type isConstant () const
 Check whether polynomial is zero or one.
bool_type hasConstantPart () const
 Check whether polynomial has term one.
bool_type firstReducibleBy (const self &) const
 Tests whether polynomial can be reduced by right-hand side.
monom_type lead () const
 Get leading term.
monom_type lexLead () const
 Get leading term w.r.t. lexicographical order.
monom_type boundedLead (deg_type bound) const
 Get leading term (using upper bound of the polynomial degree)
exp_type leadExp () const
 Get leading term.
exp_type boundedLeadExp (deg_type bound) const
set_type leadDivisors () const
 Get all divisors of the leading term.
hash_type hash () const
 Get unique hash value (may change from run to run)
hash_type stableHash () const
 Get hash value, which is reproducible.
hash_type leadStableHash () const
 Hash value of the leading term.
deg_type deg () const
 Maximal degree of the polynomial.
deg_type leadDeg () const
 Degree of the leading term.
deg_type lexLeadDeg () const
 Degree of the leading term w.r.t. lexicographical ordering.
deg_type totalDeg () const
 Total maximal degree of the polynomial.
deg_type leadTotalDeg () const
 Total degree of the leading term.
self gradedPart (deg_type deg) const
 Get part of given degree.
size_type nNodes () const
 Number of nodes in the decision diagram.
size_type nUsedVariables () const
 Number of variables of the polynomial.
monom_type usedVariables () const
 Set of variables of the polynomial.
exp_type usedVariablesExp () const
 Exponent vector of all of variables of the polynomial.
size_type length () const
 Returns number of terms.
ostream_typeprint (ostream_type &) const
 Print current polynomial to output stream.
const_iterator begin () const
 Start of iteration over monomials.
const_iterator end () const
 Finish of iteration over monomials.
exp_iterator expBegin () const
 Start of iteration over exponent vectors.
exp_iterator expEnd () const
 Finish of iteration over exponent vectors.
first_iterator firstBegin () const
 Start of first term.
first_iterator firstEnd () const
 Finish of first term.
monom_type firstTerm () const
 Get of first lexicographic term.
deg_iterator degBegin () const
 Start of degrees.
deg_iterator degEnd () const
 Finish of degrees.
ordered_iterator orderedBegin () const
 Start of ordering respecting iterator.
ordered_iterator orderedEnd () const
 Finish of ordering respecting iterator.
ordered_exp_iterator orderedExpBegin () const
 Start of ordering respecting exponent iterator.
ordered_exp_iterator orderedExpEnd () const
 Finish of ordering respecting exponent iterator.
navigator navigation () const
 Navigate through structure.
navigator endOfNavigation () const
 End of navigation marker.
dd_type copyDiagram ()
 gives a copy of the diagram
 operator set_type () const
 Casting operator to Boolean set.
size_type eliminationLength () const
size_type eliminationLengthWithDegBound (deg_type garantied_deg_bound) const
void fetchTerms (termlist_type &) const
 Get list of all terms.
termlist_type terms () const
 Return of all terms.
const dd_typediagram () const
 Read-only access to internal decision diagramm structure.
set_type set () const
 Get corresponding subset of of the powerset over all variables.
bool_type isSingleton () const
 Test, whether we have one term only.
bool_type isSingletonOrPair () const
 Test, whether we have one or two terms only.
bool_type isPair () const
 Test, whether we have two terms only.
const ring_typering () const
 Access ring, where this belongs to.
comp_type compare (const self &) const
 Compare with right-hand side and return comparision code.
Arithmetical operations
const selfoperator- () const
selfoperator+= (const self &)
selfoperator+= (constant_type rhs)
template<class RHSType >
selfoperator-= (const RHSType &rhs)
selfoperator*= (const monom_type &)
selfoperator*= (const exp_type &)
selfoperator*= (const self &)
selfoperator*= (constant_type rhs)
selfoperator/= (const var_type &)
selfoperator/= (const monom_type &)
selfoperator/= (const exp_type &)
selfoperator/= (const self &rhs)
selfoperator/= (constant_type rhs)
selfoperator%= (const var_type &)
selfoperator%= (const monom_type &)
selfoperator%= (const self &rhs)
selfoperator%= (constant_type rhs)
Logical operations
bool_type operator== (const self &rhs) const
bool_type operator!= (const self &rhs) const
bool_type operator== (constant_type rhs) const
bool_type operator!= (constant_type rhs) const
Compile-time access to generic iterators
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

Protected Member Functions

dd_typeinternalDiagram ()
 Access to internal decision diagramm structure.
self leadFirst () const
 Generate a polynomial, whose first term is the leading term.
set_type firstDivisors () const
 Get all divisors of the first term.

Friends

class BooleMonomial
 Let BooleMonomial access protected and private members.

Detailed Description

This class wraps the underlying decicion diagram type and defines the necessary operations.


Member Typedef Documentation

Type for result of polynomial comparisons.

Reimplemented from polybori::CAuxTypes.

Iterator type for iterating over all monomials.

Type for wrapping integer and bool values.

typedef binary_composition< std::minus<size_type>, project_ith<1>, integral_constant<size_type, 1> > polybori::BoolePolynomial::decrement_type

Decrementation functional type.

Iterator type for iterating all monomials (dereferencing to degree)

typedef dd_type::easy_equality_property polybori::BoolePolynomial::easy_equality_property

The property whether the equality check is easy is inherited from dd_type.

Iterator type for iterating all exponent vectors.

Fix type for treatment of exponent vectors.

typedef dd_type::first_iterator polybori::BoolePolynomial::first_iterator

Iterator type for iterating over indices of the leading term.

typedef std::map<self, idx_type, symmetric_composition< std::less<navigator>, navigates<self> > > polybori::BoolePolynomial::idx_map_type

Type for index maps.

typedef binary_composition< std::plus<size_type>, project_ith<1>, integral_constant<size_type, 1> > polybori::BoolePolynomial::increment_type

Incrementation functional type.

Fix type for treatment of monomials.

Todo:
A more sophisticated treatment for monomials is needed.
typedef dd_type::navigator polybori::BoolePolynomial::navigator

Iterator-like type for navigating through diagram structure.

Iterator type for iterating over all exponents in ordering order.

Iterator type for iterating over all monomials in ordering order.

Type for out-stream.

Reimplemented from polybori::CAuxTypes.

typedef std::map<self, std::vector<self>, symmetric_composition< std::less<navigator>, navigates<self> > > polybori::BoolePolynomial::poly_vec_map_type
typedef BoolePolyRing polybori::BoolePolynomial::ring_type

Type for Boolean polynomial rings (without ordering)

Generic access to current type.

Type for sets of Boolean variables.

Type for lists of terms.

Fix type for treatment of monomials.


Constructor & Destructor Documentation

Default constructor.

References PBORI_TRACE_FUNC.

Construct polynomial from a constant value 0 or 1.

References PBORI_TRACE_FUNC.

polybori::BoolePolynomial::BoolePolynomial ( constant_type  isOne,
const ring_type ring 
) [inline]

Construct polynomial from a constant value 0 or 1.

Construct polynomial from decision diagram.

polybori::BoolePolynomial::BoolePolynomial ( const exp_type rhs,
const ring_type ring 
)

Construct polynomial from a subset of the powerset over all variables.

Construct polynomial from exponent vector

References PBORI_TRACE_FUNC, polybori::BooleExponent::rbegin(), and polybori::BooleExponent::rend().

polybori::BoolePolynomial::BoolePolynomial ( const navigator rhs,
const ring_type ring 
) [inline]

Construct polynomial from navigator.

Destructor.


Member Function Documentation

Get leading term (using upper bound of the polynomial degree)

Note:
Implementation note: for degree orderings (dlex, dp_asc) returns the lead of the sub-polynomial of degree 'bound', falls back to lead for all other orderings (lp, block_*)

References PBORI_TRACE_FUNC, and ring().

Referenced by polybori::groebner::nf3_degree_order(), and polybori::groebner::PolynomialSugar::PolynomialSugar().

Get leading term (using upper bound of the polynomial degree)

Note:
See implementation notes of boundedLead

References PBORI_TRACE_FUNC, and ring().

Compare with right-hand side and return comparision code.

References polybori::BooleMonomial::compare(), isZero(), lead(), and PBORI_TRACE_FUNC.

gives a copy of the diagram

Start of degrees.

References navigation(), PBORI_TRACE_FUNC, and ring().

Referenced by deg(), and eliminationLength().

Finish of degrees.

References PBORI_TRACE_FUNC.

Referenced by deg(), and eliminationLength().

const dd_type& polybori::BoolePolynomial::diagram ( ) const [inline]

End of navigation marker.

Start of iteration over exponent vectors.

References navigation(), and PBORI_TRACE_FUNC.

Referenced by polybori::groebner::FGLMStrategy::main(), and polybori::groebner::p2code().

Finish of iteration over exponent vectors.

References PBORI_TRACE_FUNC.

Referenced by polybori::groebner::p2code().

void polybori::BoolePolynomial::fetchTerms ( termlist_type theOutputList) const

Get list of all terms.

References begin(), end(), length(), and PBORI_TRACE_FUNC.

Referenced by terms().

Start of first term.

References PBORI_TRACE_FUNC.

Referenced by firstDivisors(), and lexLeadDeg().

Get all divisors of the first term.

References firstBegin(), firstEnd(), leadDeg(), PBORI_TRACE_FUNC, polybori::reversed_inter_copy(), and terms().

Finish of first term.

References PBORI_TRACE_FUNC.

Referenced by firstDivisors(), and lexLeadDeg().

Tests whether polynomial can be reduced by right-hand side.

Referenced by polybori::BooleMonomial::reducibleBy().

Get of first lexicographic term.

References polybori::LexOrder::lead(), and PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

References PBORI_TRACE_FUNC.

Get part of given degree.

References polybori::dd_graded_part(), navigation(), PBORI_TRACE_FUNC, and ring().

Referenced by polybori::groebner::nf3_degree_order().

Get unique hash value (may change from run to run)

Access to internal decision diagramm structure.

Referenced by polybori::BooleMonomial::operator*=().

Test, whether we have two terms only.

References polybori::dd_is_pair().

Test, whether we have one term only.

References polybori::dd_is_singleton().

Test, whether we have one or two terms only.

References polybori::dd_is_singleton_or_pair().

Get all divisors of the leading term.

Generate a polynomial, whose first term is the leading term.

References PBORI_TRACE_FUNC, and ring().

Referenced by leadDeg(), and leadStableHash().

Hash value of the leading term.

References leadFirst(), PBORI_TRACE_FUNC, and polybori::stable_first_hash_range().

Total degree of the leading term.

References leadDeg(), and PBORI_TRACE_FUNC.

Get leading term w.r.t. lexicographical order.

References polybori::LexOrder::lead(), and PBORI_TRACE_FUNC.

Degree of the leading term w.r.t. lexicographical ordering.

References firstBegin(), firstEnd(), isZero(), and PBORI_TRACE_FUNC.

Number of nodes in the decision diagram.

References PBORI_TRACE_FUNC.

Number of variables of the polynomial.

References PBORI_TRACE_FUNC.

polybori::BoolePolynomial::operator set_type ( ) const [inline]

Casting operator to Boolean set.

bool_type polybori::BoolePolynomial::operator!= ( const self rhs) const [inline]
bool_type polybori::BoolePolynomial::operator!= ( constant_type  rhs) const [inline]
BoolePolynomial & polybori::BoolePolynomial::operator%= ( const var_type rhs)

References PBORI_TRACE_FUNC.

BoolePolynomial & polybori::BoolePolynomial::operator%= ( const monom_type rhs)
self& polybori::BoolePolynomial::operator%= ( const self rhs) [inline]
self& polybori::BoolePolynomial::operator%= ( constant_type  rhs) [inline]
BoolePolynomial & polybori::BoolePolynomial::operator*= ( const monom_type rhs)
BoolePolynomial & polybori::BoolePolynomial::operator*= ( const exp_type rhs)
BoolePolynomial & polybori::BoolePolynomial::operator*= ( const self rhs)
self& polybori::BoolePolynomial::operator*= ( constant_type  rhs) [inline]
BoolePolynomial & polybori::BoolePolynomial::operator+= ( const self rhs)

References PBORI_TRACE_FUNC.

self& polybori::BoolePolynomial::operator+= ( constant_type  rhs) [inline]
const self& polybori::BoolePolynomial::operator- ( ) const [inline]
template<class RHSType >
self& polybori::BoolePolynomial::operator-= ( const RHSType &  rhs) [inline]
BoolePolynomial & polybori::BoolePolynomial::operator/= ( const var_type rhs)

References PBORI_TRACE_FUNC.

Referenced by operator/=().

BoolePolynomial & polybori::BoolePolynomial::operator/= ( const monom_type rhs)
BoolePolynomial & polybori::BoolePolynomial::operator/= ( const exp_type rhs)
BoolePolynomial & polybori::BoolePolynomial::operator/= ( const self rhs)

References operator/=(), and PBORI_TRACE_FUNC.

BoolePolynomial & polybori::BoolePolynomial::operator/= ( constant_type  rhs)

References PBORI_TRACE_FUNC.

self& polybori::BoolePolynomial::operator= ( constant_type  rhs) [inline]
bool_type polybori::BoolePolynomial::operator== ( const self rhs) const [inline]
bool_type polybori::BoolePolynomial::operator== ( constant_type  rhs) const [inline]

Start of ordering respecting exponent iterator.

References PBORI_TRACE_FUNC, and ring().

Referenced by print().

Finish of ordering respecting exponent iterator.

References PBORI_TRACE_FUNC, and ring().

Referenced by print().

Print current polynomial to output stream.

References polybori::dd_print_terms(), isOne(), isZero(), orderedExpBegin(), orderedExpEnd(), PBORI_TRACE_FUNC, and ring().

Referenced by polybori::operator<<().

const ring_type& polybori::BoolePolynomial::ring ( ) const [inline]

Get corresponding subset of of the powerset over all variables.

Get hash value, which is reproducible.

Return of all terms.

References fetchTerms(), and PBORI_TRACE_FUNC.

Referenced by firstDivisors().

Total maximal degree of the polynomial.

References deg(), and PBORI_TRACE_FUNC.

Set of variables of the polynomial.

References diagram(), PBORI_TRACE_FUNC, and ring().

Referenced by polybori::groebner::polynomial_in_one_block().


Friends And Related Function Documentation

friend class BooleMonomial [friend]

Let BooleMonomial access protected and private members.


The documentation for this class was generated from the following files: