RawSquareFreeIdeal Class Reference

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.
void | setToTransposeOf (const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
| Resets this object to the transpose of ideal.
void | transpose (Word *eraseVars=0)
| Equivalent to setToTransposeOf(this, eraseVars).
void | compact (const Word *remove)
| Removes the variables that divide remove.
void | print (FILE *file) const
| Print a debug-suitable representation of this object to file.
void | print (ostream &out) const
| Print a debug-suitable representation of this object to out.
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.
size_t | insert (const BigIdeal &ideal)
void | insert (const RawSquareFreeIdeal &ideal)
| Inserts all the generators of ideal.
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".
void | minimize ()
void | colon (const Word *by)
void | colon (size_t var)
void | colonReminimize (const Word *colon)
| Performs a colon and minimize.
void | colonReminimize (size_t var)
| Performs a colon by var and minimize.
void | swap01Exponents ()
| Change 0 exponents into 1 and vice versa.
void | getLcm (Word *lcm) const
| Puts the least common multiple of the generators of the ideal into lcm.
size_t | getGeneratorCount () const
size_t | getVarCount () const
size_t | getWordsPerTerm () const
Word * | getGenerator (size_t index)
| Returns the generator at index.
const Word * | getGenerator (size_t index) const
| Returns the generator at index.
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().
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().
void | getLcmOfNonMultiples (Word *lcm, size_t var) const
| Sets lcm to be the least common multple of those generators that var does not divide.
void | getGcdOfMultiples (Word *gcd, size_t var) const
| Sets gcd to be the greatest common denominator of those generators that are divisible by var.
void | getGcdOfMultiples (Word *gcd, const Word *div) const
| Sets gcd to be the greatest common denominator of those generators that are divisible by div.
void | getVarDividesCounts (vector< size_t > &counts) const
| Sets counts[var] to the number of generators that var divides.
size_t | getMultiple (size_t var) const
| Returns the index of the first generator that var divides or getGeneratorCount() if no such generator exists.
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.
size_t | getMaxSupportGen () const
| Returns the index of a generator with maximum support.
size_t | getMinSupportGen () const
| Returns the index of a generator with minimum support.
void | removeGenerator (size_t index)
| Removes the generator at index.
void | insertNonMultiples (const Word *term, const RawSquareFreeIdeal &ideal)
| Insert those generators of ideal that are not multiples of term.
void | insertNonMultiples (size_t var, const RawSquareFreeIdeal &ideal)
| Insert those generators of ideal that are not multiples of var.
size_t | getNotRelativelyPrime (const Word *term)
| Returns the index of the first generator that is not relatively prime with term.
size_t | getExclusiveVarGenerator ()
| Returns the index of a generator that is the only one to be divisible by some variable.
bool | hasFullSupport (const Word *ignore) const
| Returns true if for every variable it either divides ignore or it divides some (not necessarily minimal) generator.
bool | isMinimallyGenerated () const
| Returns true if no generator divides another.
void | swap (size_t a, size_t b)
bool | operator== (const RawSquareFreeIdeal &ideal) const
| Returns true if *this equals ideal.
bool | operator!= (const RawSquareFreeIdeal &ideal) const
Word * | back ()
const Word * | back () const
void | sortLexAscending ()
| Sorts the generators in ascending lex order.
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.

## 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.

## 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