A bit packed square free ideal placed in a pre-allocated buffer. More...

#include <RawSquareFreeIdeal.h>

Classes
class	const_iterator
	const_iterator doesn't have all it needs to be a proper STL iterator. More...

class	iterator
	iterator doesn't have all it needs to be a proper STL iterator. More...

Public Member Functions
RawSquareFreeIdeal &	operator= (const RawSquareFreeIdeal &ideal)
	Resets this object to be a copy of ideal. More...

void	setToTransposeOf (const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
	Resets this object to the transpose of ideal. More...

void	transpose (Word *eraseVars=0)
	Equivalent to setToTransposeOf(this, eraseVars). More...

void	compact (const Word *remove)
	Removes the variables that divide remove. More...

void	print (FILE *file) const
	Print a debug-suitable representation of this object to file. More...

void	print (ostream &out) const
	Print a debug-suitable representation of this object to out. More...

size_t	insert (const Ideal &ideal)
	Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all generators have been inserted. More...

size_t	insert (const BigIdeal &ideal)

void	insert (const RawSquareFreeIdeal &ideal)
	Inserts all the generators of ideal. More...

void	insert (const Word *term)

void	insertIdentity ()

bool	insert (const std::vector< std::string > &term)
	Returns false if the strings in term are not all "", "1" or "0". More...

void	minimize ()

void	colon (const Word *by)

void	colon (size_t var)

void	colonReminimize (const Word *colon)
	Performs a colon and minimize. More...

void	colonReminimize (size_t var)
	Performs a colon by var and minimize. More...

void	swap01Exponents ()
	Change 0 exponents into 1 and vice versa. More...

void	getLcm (Word *lcm) const
	Puts the least common multiple of the generators of the ideal into lcm. More...

size_t	getGeneratorCount () const

size_t	getVarCount () const

size_t	getWordsPerTerm () const

Word *	getGenerator (size_t index)
	Returns the generator at index. More...

const Word *	getGenerator (size_t index) const
	Returns the generator at index. More...

Word *	getGeneratorUnsafe (size_t index)
	Returns a pointer to the memory where a generator at index would be, even if index is equal to or greater than getGeneratorCount(). More...

const Word *	getGeneratorUnsafe (size_t index) const
	Returns a pointer to the memory where a generator at index would be, even if index is equal to or greater than getGeneratorCount(). More...

void	getLcmOfNonMultiples (Word *lcm, size_t var) const
	Sets lcm to be the least common multple of those generators that var does not divide. More...

void	getGcdOfMultiples (Word *gcd, size_t var) const
	Sets gcd to be the greatest common denominator of those generators that are divisible by var. More...

void	getGcdOfMultiples (Word gcd, const Word div) const
	Sets gcd to be the greatest common denominator of those generators that are divisible by div. More...

void	getVarDividesCounts (vector< size_t > &counts) const
	Sets counts[var] to the number of generators that var divides. More...

size_t	getMultiple (size_t var) const
	Returns the index of the first generator that var divides or getGeneratorCount() if no such generator exists. More...

size_t	getNonMultiple (size_t var) const
	Returns the index of the first generator that var does not divide or getGeneratorCount() if no such generator exists. More...

size_t	getMaxSupportGen () const
	Returns the index of a generator with maximum support. More...

size_t	getMinSupportGen () const
	Returns the index of a generator with minimum support. More...

void	removeGenerator (size_t index)
	Removes the generator at index. More...

void	insertNonMultiples (const Word *term, const RawSquareFreeIdeal &ideal)
	Insert those generators of ideal that are not multiples of term. More...

void	insertNonMultiples (size_t var, const RawSquareFreeIdeal &ideal)
	Insert those generators of ideal that are not multiples of var. More...

size_t	getNotRelativelyPrime (const Word *term)
	Returns the index of the first generator that is not relatively prime with term. More...

size_t	getExclusiveVarGenerator ()
	Returns the index of a generator that is the only one to be divisible by some variable. More...

bool	hasFullSupport (const Word *ignore) const
	Returns true if for every variable it either divides ignore or it divides some (not necessarily minimal) generator. More...

bool	isMinimallyGenerated () const
	Returns true if no generator divides another. More...

void	swap (size_t a, size_t b)

bool	operator== (const RawSquareFreeIdeal &ideal) const
	Returns true if *this equals ideal. More...

bool	operator!= (const RawSquareFreeIdeal &ideal) const

Word *	back ()

const Word *	back () const

void	sortLexAscending ()
	Sorts the generators in ascending lex order. More...

iterator	begin ()

const_iterator	begin () const

iterator	end ()

const_iterator	end () const

bool	isValid () const
	Returns true if the internal invariants of ideal are satisfied. More...

Static Public Member Functions
static RawSquareFreeIdeal *	construct (void *buffer, size_t varCount=0)

static RawSquareFreeIdeal *	construct (void *buffer, const Ideal &ideal)

static RawSquareFreeIdeal *	construct (void *buffer, const RawSquareFreeIdeal &ideal)

static size_t	getBytesOfMemoryFor (size_t varCount, size_t generatorCount)
	Returns the number of bytes of memory necessary to contain an ideal with the given parameters. More...

Private Member Functions
	RawSquareFreeIdeal ()

	RawSquareFreeIdeal (const RawSquareFreeIdeal &)

Private Attributes
size_t	_varCount

size_t	_wordsPerTerm

size_t	_genCount

Word *	_memoryEnd

Word	_memory [1]

Detailed Description

A bit packed square free ideal placed in a pre-allocated buffer.

Use SquareFreeIdeal for a more pleasant interface.

This class allocates none of its own memory. It must be initialized using the member function construct() in a buffer of sufficient size. What is sufficient memory for a given ideal can be determined by getBytesOfMemoryFor(). The buffer must be correctly aligned to support the data members that this class has.

Definition at line 37 of file RawSquareFreeIdeal.h.

Constructor & Destructor Documentation

◆ RawSquareFreeIdeal() [1/2]

RawSquareFreeIdeal::RawSquareFreeIdeal ( )

private

◆ RawSquareFreeIdeal() [2/2]

RawSquareFreeIdeal::RawSquareFreeIdeal ( const RawSquareFreeIdeal & )

private

Member Function Documentation

◆ back() [1/2]

Word* RawSquareFreeIdeal::back ( )

inline

Definition at line 211 of file RawSquareFreeIdeal.h.

◆ back() [2/2]

const Word* RawSquareFreeIdeal::back ( ) const

inline

Definition at line 212 of file RawSquareFreeIdeal.h.

◆ begin() [1/2]

iterator RawSquareFreeIdeal::begin ( )

inline

Definition at line 300 of file RawSquareFreeIdeal.h.

◆ begin() [2/2]

const_iterator RawSquareFreeIdeal::begin ( ) const

inline

Definition at line 302 of file RawSquareFreeIdeal.h.

◆ colon() [1/2]

void RSFIdeal::colon ( const Word * by )

Definition at line 249 of file RawSquareFreeIdeal.cpp.

◆ colon() [2/2]

void RSFIdeal::colon ( size_t var )

Definition at line 257 of file RawSquareFreeIdeal.cpp.

◆ colonReminimize() [1/2]

void RSFIdeal::colonReminimize ( const Word * colon )

Performs a colon and minimize.

Object must be already minimized.

Definition at line 675 of file RawSquareFreeIdeal.cpp.

◆ colonReminimize() [2/2]

void RSFIdeal::colonReminimize ( size_t var )

Performs a colon by var and minimize.

Object must be already minimized.

Definition at line 723 of file RawSquareFreeIdeal.cpp.

◆ compact()

void RSFIdeal::compact ( const Word * remove )

Removes the variables that divide remove.

Unless remove is the identity this will decrease varCount. The operation is much like colon, except that the exponents are remove entirely instead of just set to zero. The relative order of the remaining variables is preserved.

Definition at line 264 of file RawSquareFreeIdeal.cpp.

◆ construct() [1/3]

RSFIdeal * RSFIdeal::construct	(	void *	buffer,
		const Ideal &	ideal
	)

static

Definition at line 96 of file RawSquareFreeIdeal.cpp.

◆ construct() [2/3]

RSFIdeal * RSFIdeal::construct	(	void *	buffer,
		const RawSquareFreeIdeal &	ideal
	)

static

Definition at line 103 of file RawSquareFreeIdeal.cpp.

◆ construct() [3/3]

RSFIdeal * RSFIdeal::construct	(	void *	buffer,
		size_t	varCount = `0`
	)

static

Definition at line 86 of file RawSquareFreeIdeal.cpp.

◆ end() [1/2]

iterator RawSquareFreeIdeal::end ( )

inline

Definition at line 305 of file RawSquareFreeIdeal.h.

◆ end() [2/2]

const_iterator RawSquareFreeIdeal::end ( ) const

inline

Definition at line 307 of file RawSquareFreeIdeal.h.

◆ getBytesOfMemoryFor()

size_t RSFIdeal::getBytesOfMemoryFor	(	size_t	varCount,
		size_t	generatorCount
	)

static

Returns the number of bytes of memory necessary to contain an ideal with the given parameters.

This size is padded to ensure proper alignment if ideals are placed one after the other.

This function return zero if the number of bytes cannot be represented in a size_t, or nearly cannot be represented in a size_t. The returned value is otherwise positive.

Definition at line 110 of file RawSquareFreeIdeal.cpp.

◆ getExclusiveVarGenerator()

size_t RSFIdeal::getExclusiveVarGenerator ( )

Returns the index of a generator that is the only one to be divisible by some variable.

Returns getGeneratorCount() if there is no such generator.

Definition at line 521 of file RawSquareFreeIdeal.cpp.

◆ getGcdOfMultiples() [1/2]

void RSFIdeal::getGcdOfMultiples	(	Word *	gcd,
		const Word *	div
	)		const

Sets gcd to be the greatest common denominator of those generators that are divisible by div.

Definition at line 467 of file RawSquareFreeIdeal.cpp.

◆ getGcdOfMultiples() [2/2]

void RSFIdeal::getGcdOfMultiples	(	Word *	gcd,
		size_t	var
	)		const

Sets gcd to be the greatest common denominator of those generators that are divisible by var.

Definition at line 455 of file RawSquareFreeIdeal.cpp.

◆ getGenerator() [1/2]

Word * RawSquareFreeIdeal::getGenerator ( size_t index )

inline

Returns the generator at index.

Definition at line 350 of file RawSquareFreeIdeal.h.

◆ getGenerator() [2/2]

const Word * RawSquareFreeIdeal::getGenerator ( size_t index ) const

inline

Returns the generator at index.

Definition at line 355 of file RawSquareFreeIdeal.h.

◆ getGeneratorCount()

size_t RawSquareFreeIdeal::getGeneratorCount ( ) const

inline

Definition at line 124 of file RawSquareFreeIdeal.h.

◆ getGeneratorUnsafe() [1/2]

Word * RawSquareFreeIdeal::getGeneratorUnsafe ( size_t index )

inline

Returns a pointer to the memory where a generator at index would be, even if index is equal to or greater than getGeneratorCount().

Definition at line 360 of file RawSquareFreeIdeal.h.

◆ getGeneratorUnsafe() [2/2]

const Word * RawSquareFreeIdeal::getGeneratorUnsafe ( size_t index ) const

inline

Returns a pointer to the memory where a generator at index would be, even if index is equal to or greater than getGeneratorCount().

Definition at line 366 of file RawSquareFreeIdeal.h.

◆ getLcm()

void RSFIdeal::getLcm ( Word * lcm ) const

Puts the least common multiple of the generators of the ideal into lcm.

Definition at line 765 of file RawSquareFreeIdeal.cpp.

◆ getLcmOfNonMultiples()

void RSFIdeal::getLcmOfNonMultiples	(	Word *	lcm,
		size_t	var
	)		const

Sets lcm to be the least common multple of those generators that var does not divide.

Definition at line 304 of file RawSquareFreeIdeal.cpp.

◆ getMaxSupportGen()

size_t RSFIdeal::getMaxSupportGen ( ) const

Returns the index of a generator with maximum support.

Returns 0 if there are no generators.

Definition at line 415 of file RawSquareFreeIdeal.cpp.

◆ getMinSupportGen()

size_t RSFIdeal::getMinSupportGen ( ) const

Returns the index of a generator with minimum support.

Returns 0 if there are no generators.

Definition at line 435 of file RawSquareFreeIdeal.cpp.

◆ getMultiple()

size_t RSFIdeal::getMultiple ( size_t var ) const

Returns the index of the first generator that var divides or getGeneratorCount() if no such generator exists.

Definition at line 393 of file RawSquareFreeIdeal.cpp.

◆ getNonMultiple()

size_t RSFIdeal::getNonMultiple ( size_t var ) const

Returns the index of the first generator that var does not divide or getGeneratorCount() if no such generator exists.

Definition at line 404 of file RawSquareFreeIdeal.cpp.

◆ getNotRelativelyPrime()

size_t RSFIdeal::getNotRelativelyPrime ( const Word * term )

Returns the index of the first generator that is not relatively prime with term.

Returns getGeneratorCount() if no such generator exists.

Definition at line 513 of file RawSquareFreeIdeal.cpp.

◆ getVarCount()

size_t RawSquareFreeIdeal::getVarCount ( ) const

inline

Definition at line 125 of file RawSquareFreeIdeal.h.

◆ getVarDividesCounts()

void RSFIdeal::getVarDividesCounts ( vector< size_t > & counts ) const

Sets counts[var] to the number of generators that var divides.

Definition at line 366 of file RawSquareFreeIdeal.cpp.

◆ getWordsPerTerm()

size_t RawSquareFreeIdeal::getWordsPerTerm ( ) const

inline

Definition at line 126 of file RawSquareFreeIdeal.h.

◆ hasFullSupport()

bool RSFIdeal::hasFullSupport ( const Word * ignore ) const

Returns true if for every variable it either divides ignore or it divides some (not necessarily minimal) generator.

Definition at line 545 of file RawSquareFreeIdeal.cpp.

◆ insert() [1/5]

size_t RSFIdeal::insert ( const BigIdeal & ideal )

Definition at line 210 of file RawSquareFreeIdeal.cpp.

◆ insert() [2/5]

size_t RSFIdeal::insert ( const Ideal & ideal )

Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all generators have been inserted.

Returns the number of generators that has been inserted. There must be enough capacity for all the generators even if not all are actually inserted.

Definition at line 196 of file RawSquareFreeIdeal.cpp.

◆ insert() [3/5]

void RSFIdeal::insert ( const RawSquareFreeIdeal & ideal )

Inserts all the generators of ideal.

Definition at line 224 of file RawSquareFreeIdeal.cpp.

◆ insert() [4/5]

bool RSFIdeal::insert ( const std::vector< std::string > & term )

Returns false if the strings in term are not all "", "1" or "0".

Definition at line 231 of file RawSquareFreeIdeal.cpp.

◆ insert() [5/5]

void RSFIdeal::insert ( const Word * term )

Definition at line 644 of file RawSquareFreeIdeal.cpp.

◆ insertIdentity()

void RSFIdeal::insertIdentity ( )

Definition at line 658 of file RawSquareFreeIdeal.cpp.

◆ insertNonMultiples() [1/2]

void RSFIdeal::insertNonMultiples	(	const Word *	term,
		const RawSquareFreeIdeal &	ideal
	)

Insert those generators of ideal that are not multiples of term.

Definition at line 490 of file RawSquareFreeIdeal.cpp.

◆ insertNonMultiples() [2/2]

void RSFIdeal::insertNonMultiples	(	size_t	var,
		const RawSquareFreeIdeal &	ideal
	)

Insert those generators of ideal that are not multiples of var.

Definition at line 502 of file RawSquareFreeIdeal.cpp.

◆ isMinimallyGenerated()

bool RSFIdeal::isMinimallyGenerated ( ) const

Returns true if no generator divides another.

Definition at line 579 of file RawSquareFreeIdeal.cpp.

◆ isValid()

bool RSFIdeal::isValid ( ) const

Returns true if the internal invariants of ideal are satisfied.

Useful for debugging and tests.

Definition at line 774 of file RawSquareFreeIdeal.cpp.

◆ minimize()

void RSFIdeal::minimize ( )

Definition at line 242 of file RawSquareFreeIdeal.cpp.

◆ operator!=()

bool RawSquareFreeIdeal::operator!= ( const RawSquareFreeIdeal & ideal ) const

inline

Definition at line 207 of file RawSquareFreeIdeal.h.

◆ operator=()

RawSquareFreeIdeal& RawSquareFreeIdeal::operator= ( const RawSquareFreeIdeal & ideal )

inline

Resets this object to be a copy of ideal.

Definition at line 55 of file RawSquareFreeIdeal.h.

◆ operator==()

bool RSFIdeal::operator== ( const RawSquareFreeIdeal & ideal ) const

Returns true if *this equals ideal.

This comparison takes non-minimal generators and the order of the generators into account.

Definition at line 597 of file RawSquareFreeIdeal.cpp.

◆ print() [1/2]

void RSFIdeal::print ( FILE * file ) const

Print a debug-suitable representation of this object to file.

Definition at line 179 of file RawSquareFreeIdeal.cpp.

◆ print() [2/2]

void RSFIdeal::print ( ostream & out ) const

Print a debug-suitable representation of this object to out.

Definition at line 185 of file RawSquareFreeIdeal.cpp.

◆ removeGenerator()

void RSFIdeal::removeGenerator ( size_t index )

Removes the generator at index.

Definition at line 480 of file RawSquareFreeIdeal.cpp.

◆ setToTransposeOf()

void RSFIdeal::setToTransposeOf	(	const RawSquareFreeIdeal &	ideal,
		Word *	eraseVars = `0`
	)

Resets this object to the transpose of ideal.

Let M be a matrix with variable-labeled columns and generator-labeled rows. Entry (g,v) is 1 if and only if v divides g and otherwise it is 0. There is a bijection between such matrices and generating sets of ideals. Take a generating set, construct its matric and transpose the matrix. The generating set corresponding to the transposed matrix generates the transpose ideal.

The eraseVars parameter is used as for compact(). So the variables who have a 1 at their index into eraseVars (as bits) will not be taken into the matrix that is transposed. A null value indicates to take along all variables.

Definition at line 140 of file RawSquareFreeIdeal.cpp.

◆ sortLexAscending()

void RSFIdeal::sortLexAscending ( )

Sorts the generators in ascending lex order.

Definition at line 623 of file RawSquareFreeIdeal.cpp.

◆ swap()

void RSFIdeal::swap	(	size_t	a,
		size_t	b
	)

Definition at line 590 of file RawSquareFreeIdeal.cpp.

◆ swap01Exponents()

void RSFIdeal::swap01Exponents ( )

Change 0 exponents into 1 and vice versa.

Definition at line 651 of file RawSquareFreeIdeal.cpp.

◆ transpose()

void RSFIdeal::transpose ( Word * eraseVars = 0 )

Equivalent to setToTransposeOf(this, eraseVars).

Definition at line 168 of file RawSquareFreeIdeal.cpp.

Member Data Documentation

◆ _genCount

size_t RawSquareFreeIdeal::_genCount

private

Definition at line 320 of file RawSquareFreeIdeal.h.

◆ _memory

Word RawSquareFreeIdeal::_memory[1]

private

Definition at line 322 of file RawSquareFreeIdeal.h.

◆ _memoryEnd

Word* RawSquareFreeIdeal::_memoryEnd

private

Definition at line 321 of file RawSquareFreeIdeal.h.

◆ _varCount

size_t RawSquareFreeIdeal::_varCount

private

Definition at line 318 of file RawSquareFreeIdeal.h.

◆ _wordsPerTerm

size_t RawSquareFreeIdeal::_wordsPerTerm

private

Definition at line 319 of file RawSquareFreeIdeal.h.

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

src/RawSquareFreeIdeal.h
src/RawSquareFreeIdeal.cpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RawSquareFreeIdeal() [1/2]

◆ RawSquareFreeIdeal() [2/2]

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ colon() [1/2]

◆ colon() [2/2]

◆ colonReminimize() [1/2]

◆ colonReminimize() [2/2]

◆ compact()

◆ construct() [1/3]

◆ construct() [2/3]

◆ construct() [3/3]

◆ end() [1/2]

◆ end() [2/2]

◆ getBytesOfMemoryFor()

◆ getExclusiveVarGenerator()

◆ getGcdOfMultiples() [1/2]

◆ getGcdOfMultiples() [2/2]

◆ getGenerator() [1/2]

◆ getGenerator() [2/2]

◆ getGeneratorCount()

◆ getGeneratorUnsafe() [1/2]

◆ getGeneratorUnsafe() [2/2]

◆ getLcm()

◆ getLcmOfNonMultiples()

◆ getMaxSupportGen()

◆ getMinSupportGen()

◆ getMultiple()

◆ getNonMultiple()

◆ getNotRelativelyPrime()

◆ getVarCount()

◆ getVarDividesCounts()

◆ getWordsPerTerm()

◆ hasFullSupport()

◆ insert() [1/5]

◆ insert() [2/5]

◆ insert() [3/5]

◆ insert() [4/5]

◆ insert() [5/5]

◆ insertIdentity()

◆ insertNonMultiples() [1/2]

◆ insertNonMultiples() [2/2]

◆ isMinimallyGenerated()

◆ isValid()

◆ minimize()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ print() [1/2]

◆ print() [2/2]

◆ removeGenerator()

◆ setToTransposeOf()

◆ sortLexAscending()

◆ swap()

◆ swap01Exponents()

◆ transpose()

Member Data Documentation

◆ _genCount

◆ _memory

◆ _memoryEnd

◆ _varCount

◆ _wordsPerTerm