The general-purpose monomials. More...

#include <Monomial.h>

Inheritance diagram for carl::Monomial:

Collaboration diagram for carl::Monomial:

[legend]

Public Types
using	Arg = std::shared_ptr< const Monomial >

using	Content = std::vector< std::pair< Variable, std::size_t > >

Public Member Functions
	~Monomial ()

	Monomial ()=delete
	Default constructor. More...

	Monomial (const Monomial &rhs)=delete

	Monomial (Monomial &&rhs)=delete

exponents_it	begin ()
	Returns iterator on first pair of variable and exponent. More...

exponents_cIt	begin () const
	Returns constant iterator on first pair of variable and exponent. More...

exponents_it	end ()
	Returns past-the-end iterator. More...

exponents_cIt	end () const
	Returns past-the-end iterator. More...

std::size_t	hash () const
	Returns the hash of this monomial. More...

std::size_t	id () const
	Return the id of this monomial. More...

exponent	tdeg () const
	Gives the total degree, i.e. More...

const Content &	exponents () const

bool	is_constant () const
	Checks whether the monomial is a constant. More...

bool	integer_valued () const

bool	is_linear () const
	Checks whether the monomial has exactly degree one. More...

bool	isAtMostLinear () const
	Checks whether the monomial has at most degree one. More...

bool	is_square () const
	Checks whether the monomial is a square, i.e. More...

std::size_t	num_variables () const
	Returns the number of variables that occur in the monomial. More...

Variable	single_variable () const
	Retrieves the single variable of the monomial. More...

bool	has_no_other_variable (Variable v) const
	Checks that there is no other variable than the given one. More...

const std::pair< Variable, std::size_t > &	operator[] (std::size_t index) const
	Retrieves the given VarExpPair. More...

exponent	exponent_of_variable (Variable v) const
	Retrieves the exponent of the given variable. More...

bool	has (Variable v) const
	TODO: write code if binary search is preferred. More...

Monomial::Arg	drop_variable (Variable v) const
	For a monomial m = Prod( x_i^{e_i} ) * v^e, divides m by v^e. More...

bool	divide (Variable v, Monomial::Arg &res) const
	Divides the monomial by a variable v. More...

bool	divisible (const Monomial::Arg &m) const
	Checks if this monomial is divisible by the given monomial m. More...

bool	divide (const Monomial::Arg &m, Monomial::Arg &res) const
	Returns a new monomial that is this monomial divided by m. More...

Monomial::Arg	sqrt () const
	Calculates and returns the square root of this monomial, iff the monomial is a square as checked by is_square(). More...

bool	is_consistent () const
	Checks if the monomial is consistent. More...

Static Public Member Functions
static CompareResult	compareLexical (const Monomial::Arg &lhs, const Monomial::Arg &rhs)

static CompareResult	compareLexical (const Monomial::Arg &lhs, Variable rhs)

static CompareResult	compareGradedLexical (const Monomial::Arg &lhs, const Monomial::Arg &rhs)

static CompareResult	compareGradedLexical (const Monomial::Arg &lhs, Variable rhs)

static Monomial::Arg	lcm (const Monomial::Arg &lhs, const Monomial::Arg &rhs)
	Calculates the least common multiple of two monomial pointers. More...

static Monomial::Arg	calcLcmAndDivideBy (const Monomial::Arg &lhs, const Monomial::Arg &rhs)
	Returns lcm(lhs, rhs) / rhs. More...

static CompareResult	lexicalCompare (const Monomial &lhs, const Monomial &rhs)
	This method performs a lexical comparison as defined in [3], page 47. More...

static std::size_t	hashContent (const Monomial::Content &c)
	Calculate the hash of a monomial based on its content. More...

Private Types
using	exponents_it = Content::iterator

using	exponents_cIt = Content::const_iterator

Private Member Functions
void	calc_hash ()
	Calculates the hash and stores it to mHash. More...

void	calc_total_degree ()
	Calculates the total degree and stores it to mTotalDegree. More...

	Monomial (Content &&content, std::size_t totalDegree=0)
	Generate a monomial from a vector of variable-exponent pairs and a total degree. More...

	Monomial (const Content &content, std::size_t totalDegree=0)
	Generate a monomial from a vector of variable-exponent pairs and a total degree. More...

Private Attributes
Content	mExponents
	A vector of variable exponent pairs (v_i^e_i) with nonzero exponents. More...

std::size_t	mTotalDegree = 0
	Some applications performance depends on getting the degree of monomials very fast. More...

std::size_t	mId = 0
	Monomial id. More...

std::size_t	mHash = 0
	Cached hash. More...

std::weak_ptr< const Monomial >	mWeakPtr

Friends
class	MonomialPool

Detailed Description

The general-purpose monomials.

Notice that we aim to keep this object as small as possbible, while also limiting the use of expensive language features such as RTTI, exceptions and even polymorphism.

Although a Monomial can conceptually be seen as a map from variables to exponents, this implementation uses a vector of pairs of variables and exponents. Due to the fact that monomials usually contain only a small number of variables, the overhead introduced by std::map makes up for the asymptotically slower std::find on the std::vector that is used.

Besides, many operations like multiplication, division or substitution do not rely on finding some variable, but must iterate over all entries anyway.

Definition at line 58 of file Monomial.h.

Member Typedef Documentation

◆ Arg

using carl::Monomial::Arg = std::shared_ptr<const Monomial>

Definition at line 62 of file Monomial.h.

◆ Content

using carl::Monomial::Content = std::vector<std::pair<Variable, std::size_t> >

Definition at line 63 of file Monomial.h.

◆ exponents_cIt

using carl::Monomial::exponents_cIt = Content::const_iterator

private

Definition at line 83 of file Monomial.h.

◆ exponents_it

using carl::Monomial::exponents_it = Content::iterator

private

Definition at line 82 of file Monomial.h.

Constructor & Destructor Documentation

◆ ~Monomial()

carl::Monomial::~Monomial ( )

Definition at line 13 of file Monomial.cpp.

Here is the call graph for this function:

◆ Monomial() [1/5]

carl::Monomial::Monomial ( )

delete

Default constructor.

◆ Monomial() [2/5]

carl::Monomial::Monomial ( const Monomial & rhs )

delete

◆ Monomial() [3/5]

carl::Monomial::Monomial ( Monomial && rhs )

delete

◆ Monomial() [4/5]

carl::Monomial::Monomial	(	Content &&	content,
		std::size_t	totalDegree = `0`
	)

inlineprivate

Generate a monomial from a vector of variable-exponent pairs and a total degree.

If the totalDegree is zero, it is recalculated. The content is not expected to be sorted.

Parameters

content	The variables and their exponents.
totalDegree	The total degree of the monomial to generate, or zero.

Definition at line 110 of file Monomial.h.

Here is the call graph for this function:

◆ Monomial() [5/5]

carl::Monomial::Monomial	(	const Content &	content,
		std::size_t	totalDegree = `0`
	)

inlineprivate

Generate a monomial from a vector of variable-exponent pairs and a total degree.

If the totalDegree is zero, it is recalculated. The content is not expected to be sorted.

Parameters

content	The variables and their exponents
totalDegree	The total degree of the monomial to generate, or zero.

Definition at line 131 of file Monomial.h.

Member Function Documentation

◆ begin() [1/2]

exponents_it carl::Monomial::begin ( )

inline

Returns iterator on first pair of variable and exponent.

Returns: Iterator on begin.

Definition at line 140 of file Monomial.h.

◆ begin() [2/2]

exponents_cIt carl::Monomial::begin ( ) const

inline

Returns constant iterator on first pair of variable and exponent.

Returns: Iterator on begin.

Definition at line 147 of file Monomial.h.

◆ calc_hash()

void carl::Monomial::calc_hash ( )

inlineprivate

Calculates the hash and stores it to mHash.

Definition at line 90 of file Monomial.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calc_total_degree()

void carl::Monomial::calc_total_degree ( )

inlineprivate

Calculates the total degree and stores it to mTotalDegree.

Definition at line 96 of file Monomial.h.

Here is the caller graph for this function:

◆ calcLcmAndDivideBy()

static Monomial::Arg carl::Monomial::calcLcmAndDivideBy	(	const Monomial::Arg &	lhs,
		const Monomial::Arg &	rhs
	)

inlinestatic

Returns lcm(lhs, rhs) / rhs.

Definition at line 444 of file Monomial.h.

Here is the call graph for this function:

◆ compareGradedLexical() [1/2]

static CompareResult carl::Monomial::compareGradedLexical	(	const Monomial::Arg &	lhs,
		const Monomial::Arg &	rhs
	)

inlinestatic

Definition at line 406 of file Monomial.h.

Here is the call graph for this function:

◆ compareGradedLexical() [2/2]

static CompareResult carl::Monomial::compareGradedLexical	(	const Monomial::Arg &	lhs,
		Variable	rhs
	)

inlinestatic

Definition at line 419 of file Monomial.h.

◆ compareLexical() [1/2]

static CompareResult carl::Monomial::compareLexical	(	const Monomial::Arg &	lhs,
		const Monomial::Arg &	rhs
	)

inlinestatic

Definition at line 385 of file Monomial.h.

Here is the call graph for this function:

◆ compareLexical() [2/2]

static CompareResult carl::Monomial::compareLexical	(	const Monomial::Arg &	lhs,
		Variable	rhs
	)

inlinestatic

Definition at line 396 of file Monomial.h.

◆ divide() [1/2]

bool carl::Monomial::divide	(	const Monomial::Arg &	m,
		Monomial::Arg &	res
	)		const

Returns a new monomial that is this monomial divided by m.

Returns a pair of a monomial pointer and a bool. The bool indicates if the division was possible. The monomial pointer holds the result of the division. If the division resulted in an empty monomial (i.e. the two monomials were equal), the pointer is nullptr.

Parameters

m	Monomial.
res	Resulting monomial.

Returns: this divided by m.

Definition at line 68 of file Monomial.cpp.

Here is the call graph for this function:

◆ divide() [2/2]

bool carl::Monomial::divide	(	Variable	v,
		Monomial::Arg &	res
	)		const

Divides the monomial by a variable v.

If the division is impossible (because v does not occur in the monomial), nullptr is returned.

Parameters

v	Variable
res	Resulting monomial

Returns: This divided by v.

Definition at line 37 of file Monomial.cpp.

Here is the call graph for this function:

◆ divisible()

bool carl::Monomial::divisible ( const Monomial::Arg & m ) const

inline

Checks if this monomial is divisible by the given monomial m.

Parameters

m Monomial.

Returns: If this is divisible by m.

Definition at line 324 of file Monomial.h.

Here is the call graph for this function:

◆ drop_variable()

Monomial::Arg carl::Monomial::drop_variable ( Variable v ) const

For a monomial m = Prod( x_i^{e_i} ) * v^e, divides m by v^e.

Returns: nullptr if result is 1, otherwise m/v^e.

Todo:: this should work on the shared_ptr directly. Then we could directly return this shared_ptr instead of the ugly copying.

Definition at line 17 of file Monomial.cpp.

Here is the call graph for this function:

◆ end() [1/2]

exponents_it carl::Monomial::end ( )

inline

Returns past-the-end iterator.

Returns: Iterator on end.

Definition at line 154 of file Monomial.h.

Here is the caller graph for this function:

◆ end() [2/2]

exponents_cIt carl::Monomial::end ( ) const

inline

Returns past-the-end iterator.

Returns: Iterator on end.

Definition at line 161 of file Monomial.h.

◆ exponent_of_variable()

exponent carl::Monomial::exponent_of_variable ( Variable v ) const

inline

Retrieves the exponent of the given variable.

Parameters

v Variable.

Returns: Exponent of v.

Definition at line 285 of file Monomial.h.

◆ exponents()

const Content& carl::Monomial::exponents ( ) const

inline

Definition at line 189 of file Monomial.h.

Here is the caller graph for this function:

◆ has()

bool carl::Monomial::has ( Variable v ) const

inline

TODO: write code if binary search is preferred.

Parameters

v	The variable to check for its occurrence.

Returns: true, if the variable occurs in this term.

Definition at line 299 of file Monomial.h.

◆ has_no_other_variable()

bool carl::Monomial::has_no_other_variable ( Variable v ) const

inline

Checks that there is no other variable than the given one.

Parameters

v Variable.

Returns: If there is only v.

Definition at line 264 of file Monomial.h.

◆ hash()

std::size_t carl::Monomial::hash ( ) const

inline

Returns the hash of this monomial.

Returns: Hash.

Definition at line 169 of file Monomial.h.

Here is the caller graph for this function:

◆ hashContent()

static std::size_t carl::Monomial::hashContent ( const Monomial::Content & c )

inlinestatic

Calculate the hash of a monomial based on its content.

Parameters

c	Content of a monomial.

Returns: Hash of the monomial.

Definition at line 466 of file Monomial.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ id()

std::size_t carl::Monomial::id ( ) const

inline

Return the id of this monomial.

Returns: Id.

Definition at line 177 of file Monomial.h.

Here is the caller graph for this function:

◆ integer_valued()

bool carl::Monomial::integer_valued ( ) const

inline

Returns: true, if the image of this monomial is integer-valued.

Definition at line 204 of file Monomial.h.

◆ is_consistent()

bool carl::Monomial::is_consistent ( ) const

Checks if the monomial is consistent.

Returns: If this is consistent.

Definition at line 207 of file Monomial.cpp.

Here is the caller graph for this function:

◆ is_constant()

bool carl::Monomial::is_constant ( ) const

inline

Checks whether the monomial is a constant.

Returns: If monomial is constant.

Definition at line 197 of file Monomial.h.

◆ is_linear()

bool carl::Monomial::is_linear ( ) const

inline

Checks whether the monomial has exactly degree one.

Returns: If monomial is linear.

Definition at line 216 of file Monomial.h.

◆ is_square()

bool carl::Monomial::is_square ( ) const

inline

Checks whether the monomial is a square, i.e.

whether all exponents are even.

Returns: If monomial is a square.

Definition at line 232 of file Monomial.h.

◆ isAtMostLinear()

bool carl::Monomial::isAtMostLinear ( ) const

inline

Checks whether the monomial has at most degree one.

Returns: If monomial is linear or constant.

Definition at line 224 of file Monomial.h.

◆ lcm()

Monomial::Arg carl::Monomial::lcm	(	const Monomial::Arg &	lhs,
		const Monomial::Arg &	rhs
	)

static

Calculates the least common multiple of two monomial pointers.

If both are valid objects, the lcm of both is calculated. If only one is a valid object, this one is returned. If both are invalid objects, an empty monomial is returned.

Parameters

lhs	First monomial.
rhs	Second monomial.

Returns: lcm of lhs and rhs.

Definition at line 151 of file Monomial.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lexicalCompare()

CompareResult carl::Monomial::lexicalCompare	(	const Monomial &	lhs,
		const Monomial &	rhs
	)

static

This method performs a lexical comparison as defined in [3], page 47.

We define the exponent vectors to be in decreasing order, i.e. the exponents of the larger variables first.

Parameters

lhs	First monomial.
rhs	Second monomial.

Returns: Comparison result.

See also: [3], page 47.

Definition at line 231 of file Monomial.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ num_variables()

std::size_t carl::Monomial::num_variables ( ) const

inline

Returns the number of variables that occur in the monomial.

Returns: Number of variables.

Definition at line 245 of file Monomial.h.

Here is the caller graph for this function:

◆ operator[]()

const std::pair<Variable, std::size_t>& carl::Monomial::operator[] ( std::size_t index ) const

inline

Retrieves the given VarExpPair.

Parameters

index Index.

Returns: VarExpPair.

Definition at line 276 of file Monomial.h.

◆ single_variable()

Variable carl::Monomial::single_variable ( ) const

inline

Retrieves the single variable of the monomial.

Asserts that there is in fact only a single variable.

Returns: Variable.

Definition at line 254 of file Monomial.h.

◆ sqrt()

Monomial::Arg carl::Monomial::sqrt ( ) const

Calculates and returns the square root of this monomial, iff the monomial is a square as checked by is_square().

Otherwise, nullptr is returned.

Returns: The square root of this monomial, iff the monomial is a square as checked by is_square().

Definition at line 141 of file Monomial.cpp.

Here is the call graph for this function:

◆ tdeg()

exponent carl::Monomial::tdeg ( ) const

inline

Gives the total degree, i.e.

the sum of all exponents.

Returns: Total degree.

Definition at line 185 of file Monomial.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ MonomialPool

friend class MonomialPool

friend

Definition at line 60 of file Monomial.h.

Field Documentation

◆ mExponents

Content carl::Monomial::mExponents

private

A vector of variable exponent pairs (v_i^e_i) with nonzero exponents.

Definition at line 74 of file Monomial.h.

◆ mHash

std::size_t carl::Monomial::mHash = 0

mutableprivate

Cached hash.

Definition at line 80 of file Monomial.h.

◆ mId

std::size_t carl::Monomial::mId = 0

mutableprivate

Monomial id.

Definition at line 78 of file Monomial.h.

◆ mTotalDegree

std::size_t carl::Monomial::mTotalDegree = 0

private

Some applications performance depends on getting the degree of monomials very fast.

Definition at line 76 of file Monomial.h.

◆ mWeakPtr

std::weak_ptr<const Monomial> carl::Monomial::mWeakPtr

mutableprivate

Definition at line 85 of file Monomial.h.

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

carl-arith/poly/umvpoly/Monomial.h
carl-arith/poly/umvpoly/Monomial.cpp

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Arg

◆ Content

◆ exponents_cIt

◆ exponents_it

Constructor & Destructor Documentation

◆ ~Monomial()

◆ Monomial() [1/5]

◆ Monomial() [2/5]

◆ Monomial() [3/5]

◆ Monomial() [4/5]

◆ Monomial() [5/5]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ calc_hash()

◆ calc_total_degree()

◆ calcLcmAndDivideBy()

◆ compareGradedLexical() [1/2]

◆ compareGradedLexical() [2/2]

◆ compareLexical() [1/2]

◆ compareLexical() [2/2]

◆ divide() [1/2]

◆ divide() [2/2]

◆ divisible()

◆ drop_variable()

◆ end() [1/2]

◆ end() [2/2]

◆ exponent_of_variable()

◆ exponents()

◆ has()

◆ has_no_other_variable()

◆ hash()

◆ hashContent()

◆ id()

◆ integer_valued()

◆ is_consistent()

◆ is_constant()

◆ is_linear()

◆ is_square()

◆ isAtMostLinear()

◆ lcm()

◆ lexicalCompare()

◆ num_variables()

◆ operator[]()

◆ single_variable()

◆ sqrt()

◆ tdeg()

Friends And Related Function Documentation

◆ MonomialPool

Field Documentation

◆ mExponents

◆ mHash

◆ mId

◆ mTotalDegree

◆ mWeakPtr