RawSquareFreeIdeal.h
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2010 University of Aarhus
Contact Bjarke Hammersholt Roune for license information (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#ifndef RAW_SQUARE_FREE_IDEAL_GUARD
#define RAW_SQUARE_FREE_IDEAL_GUARD
#include <ostream>
#include <vector>
class Ideal;
class BigIdeal;
class RawSquareFreeIdeal {
public:
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);
RawSquareFreeIdeal& operator=(const RawSquareFreeIdeal& ideal)
{return *construct(this, ideal);}
void setToTransposeOf(const RawSquareFreeIdeal& ideal, Word* eraseVars = 0);
void transpose(Word* eraseVars = 0);
void compact(const Word* remove);
void print(FILE* file) const;
void print(ostream& out) const;
size_t insert(const Ideal& ideal);
size_t insert(const BigIdeal& ideal);
void insert(const RawSquareFreeIdeal& ideal);
void insert(const Word* term);
void insertIdentity();
bool insert(const std::vector<std::string>& term);
void minimize();
void colon(const Word* by);
void colon(size_t var);
void colonReminimize(const Word* colon);
void colonReminimize(size_t var);
void swap01Exponents();
void getLcm(Word* lcm) const;
size_t getGeneratorCount() const {return _genCount;}
size_t getVarCount() const {return _varCount;}
size_t getWordsPerTerm() const {return _wordsPerTerm;}
Word* getGenerator(size_t index);
const Word* getGenerator(size_t index) const;
Word* getGeneratorUnsafe(size_t index);
const Word* getGeneratorUnsafe(size_t index) const;
void getLcmOfNonMultiples(Word* lcm, size_t var) const;
void getGcdOfMultiples(Word* gcd, size_t var) const;
void getGcdOfMultiples(Word* gcd, const Word* div) const;
void getVarDividesCounts(vector<size_t>& counts) const;
size_t getMultiple(size_t var) const;
size_t getNonMultiple(size_t var) const;
size_t getMaxSupportGen() const;
size_t getMinSupportGen() const;
void removeGenerator(size_t index);
void insertNonMultiples(const Word* term, const RawSquareFreeIdeal& ideal);
void insertNonMultiples(size_t var, const RawSquareFreeIdeal& ideal);
size_t getNotRelativelyPrime(const Word* term);
size_t getExclusiveVarGenerator();
bool hasFullSupport(const Word* ignore) const;
bool isMinimallyGenerated() const;
void swap(size_t a, size_t b);
bool operator==(const RawSquareFreeIdeal& ideal) const;
bool operator!=(const RawSquareFreeIdeal& ideal) const {
return !(*this == ideal);
}
Word* back() {iterator e = end(); --e; return *e;}
const Word* back() const {const_iterator e = end(); --e; return *e;}
void sortLexAscending();
class const_iterator {
public:
const_iterator(const Word* term, size_t wordsPerTerm):
_term(term), _wordsPerTerm(wordsPerTerm) {
}
const Word* operator*() const {return _term;}
const_iterator operator++() {_term += _wordsPerTerm; return *this;}
const_iterator operator--() {_term -= _wordsPerTerm; return *this;}
bool operator==(const const_iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return _term == it._term;
}
bool operator!=(const const_iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return _term != it._term;
}
ptrdiff_t operator-(const const_iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return (_term - it._term) / _wordsPerTerm;
}
const_iterator operator+(ptrdiff_t i) const {
return const_iterator(_term + i * _wordsPerTerm, _wordsPerTerm);
}
const_iterator& operator=(const const_iterator& it) {
ASSERT(it._wordsPerTerm == _wordsPerTerm);
_term = it._term;
return *this;
}
private:
const Word* _term;
const size_t _wordsPerTerm;
};
class iterator {
public:
iterator(Word* term, size_t wordsPerTerm):
_term(term), _wordsPerTerm(wordsPerTerm) {
}
operator const_iterator() const {
return const_iterator(_term, _wordsPerTerm);
}
Word* operator*() const {return _term;}
iterator operator++() {_term += _wordsPerTerm; return *this;}
iterator operator--() {_term -= _wordsPerTerm; return *this;}
bool operator==(const iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return _term == it._term;
}
bool operator!=(const iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return _term != it._term;
}
ptrdiff_t operator-(const iterator& it) const {
ASSERT(_wordsPerTerm == it._wordsPerTerm);
return (_term - it._term) / _wordsPerTerm;
}
iterator operator+(ptrdiff_t i) const {
return iterator(_term + i * _wordsPerTerm, _wordsPerTerm);
}
iterator& operator=(const iterator& it) {
ASSERT(it._wordsPerTerm == _wordsPerTerm);
_term = it._term;
return *this;
}
private:
Word* _term;
const size_t _wordsPerTerm;
};
iterator begin()
{return iterator(_memory, getWordsPerTerm());}
const_iterator begin() const
{return const_iterator(_memory, getWordsPerTerm());}
iterator end()
{return iterator(_memoryEnd, getWordsPerTerm());}
const_iterator end() const
{return const_iterator(_memoryEnd, getWordsPerTerm());}
bool isValid() const;
private:
RawSquareFreeIdeal(); // Not available
RawSquareFreeIdeal(const RawSquareFreeIdeal&); // Not available
size_t _varCount;
size_t _wordsPerTerm;
size_t _genCount;
Word* _memoryEnd;
Word _memory[1]; // variable size array
};
RawSquareFreeIdeal* newRawSquareFreeIdeal(size_t varCount, size_t capacity);
RawSquareFreeIdeal* newRawSquareFreeIdeal(const RawSquareFreeIdeal& ideal);
RawSquareFreeIdeal* newRawSquareFreeIdealParse(const char* str);
void deleteRawSquareFreeIdeal(RawSquareFreeIdeal* ideal);
inline ostream& operator<<(ostream& out, const RawSquareFreeIdeal& ideal) {
ideal.print(out);
return out;
}
inline Word* RawSquareFreeIdeal::getGenerator(size_t index) {
ASSERT(index < getGeneratorCount());
return _memory + index * getWordsPerTerm();
}
inline const Word* RawSquareFreeIdeal::getGenerator(size_t index) const {
ASSERT(index < getGeneratorCount());
return _memory + index * getWordsPerTerm();
}
inline Word* RawSquareFreeIdeal::getGeneratorUnsafe(size_t index) {
// no assert to check index is valid as this method specifically
// allows out-of-bounds access.
return _memory + index * getWordsPerTerm();
}
inline const Word* RawSquareFreeIdeal::getGeneratorUnsafe(size_t index) const {
// no assert to check index is valid as this method specifically
// allows out-of-bounds access.
return _memory + index * getWordsPerTerm();
}
#endif
operator<<
ostream & operator<<(ostream &out, const RawSquareFreeIdeal &ideal)
Definition RawSquareFreeIdeal.h:345
newRawSquareFreeIdealParse
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
Definition RawSquareFreeIdeal.cpp:819
newRawSquareFreeIdeal
RawSquareFreeIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
Definition RawSquareFreeIdeal.cpp:797
deleteRawSquareFreeIdeal
void deleteRawSquareFreeIdeal(RawSquareFreeIdeal *ideal)
Deallocates memory returned by newRawSquareFreeIdeal().
BigIdeal
Definition BigIdeal.h:27
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
RawSquareFreeIdeal::const_iterator
const_iterator doesn't have all it needs to be a proper STL iterator.
Definition RawSquareFreeIdeal.h:219
RawSquareFreeIdeal::const_iterator::operator--
const_iterator operator--()
Definition RawSquareFreeIdeal.h:227
RawSquareFreeIdeal::const_iterator::operator!=
bool operator!=(const const_iterator &it) const
Definition RawSquareFreeIdeal.h:233
RawSquareFreeIdeal::const_iterator::operator=
const_iterator & operator=(const const_iterator &it)
Definition RawSquareFreeIdeal.h:246
RawSquareFreeIdeal::const_iterator::_term
const Word * _term
Definition RawSquareFreeIdeal.h:253
RawSquareFreeIdeal::const_iterator::operator==
bool operator==(const const_iterator &it) const
Definition RawSquareFreeIdeal.h:229
RawSquareFreeIdeal::const_iterator::operator-
ptrdiff_t operator-(const const_iterator &it) const
Definition RawSquareFreeIdeal.h:238
RawSquareFreeIdeal::const_iterator::const_iterator
const_iterator(const Word *term, size_t wordsPerTerm)
Definition RawSquareFreeIdeal.h:221
RawSquareFreeIdeal::const_iterator::operator++
const_iterator operator++()
Definition RawSquareFreeIdeal.h:226
RawSquareFreeIdeal::const_iterator::operator*
const Word * operator*() const
Definition RawSquareFreeIdeal.h:225
RawSquareFreeIdeal::const_iterator::_wordsPerTerm
const size_t _wordsPerTerm
Definition RawSquareFreeIdeal.h:254
RawSquareFreeIdeal::const_iterator::operator+
const_iterator operator+(ptrdiff_t i) const
Definition RawSquareFreeIdeal.h:242
RawSquareFreeIdeal::iterator
iterator doesn't have all it needs to be a proper STL iterator.
Definition RawSquareFreeIdeal.h:259
RawSquareFreeIdeal::iterator::operator++
iterator operator++()
Definition RawSquareFreeIdeal.h:270
RawSquareFreeIdeal::iterator::iterator
iterator(Word *term, size_t wordsPerTerm)
Definition RawSquareFreeIdeal.h:261
RawSquareFreeIdeal::iterator::operator*
Word * operator*() const
Definition RawSquareFreeIdeal.h:269
RawSquareFreeIdeal::iterator::operator--
iterator operator--()
Definition RawSquareFreeIdeal.h:271
RawSquareFreeIdeal::iterator::_term
Word * _term
Definition RawSquareFreeIdeal.h:296
RawSquareFreeIdeal::iterator::operator-
ptrdiff_t operator-(const iterator &it) const
Definition RawSquareFreeIdeal.h:282
RawSquareFreeIdeal::iterator::operator!=
bool operator!=(const iterator &it) const
Definition RawSquareFreeIdeal.h:277
RawSquareFreeIdeal::iterator::operator+
iterator operator+(ptrdiff_t i) const
Definition RawSquareFreeIdeal.h:286
RawSquareFreeIdeal::iterator::_wordsPerTerm
const size_t _wordsPerTerm
Definition RawSquareFreeIdeal.h:297
RawSquareFreeIdeal::iterator::operator==
bool operator==(const iterator &it) const
Definition RawSquareFreeIdeal.h:273
RawSquareFreeIdeal::iterator::operator=
iterator & operator=(const iterator &it)
Definition RawSquareFreeIdeal.h:289
RawSquareFreeIdeal
A bit packed square free ideal placed in a pre-allocated buffer.
Definition RawSquareFreeIdeal.h:37
RawSquareFreeIdeal::sortLexAscending
void sortLexAscending()
Sorts the generators in ascending lex order.
Definition RawSquareFreeIdeal.cpp:623
RawSquareFreeIdeal::construct
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
Definition RawSquareFreeIdeal.cpp:86
RawSquareFreeIdeal::getNotRelativelyPrime
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
Definition RawSquareFreeIdeal.cpp:513
RawSquareFreeIdeal::isValid
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
Definition RawSquareFreeIdeal.cpp:774
RawSquareFreeIdeal::hasFullSupport
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
Definition RawSquareFreeIdeal.cpp:545
RawSquareFreeIdeal::getGcdOfMultiples
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var.
Definition RawSquareFreeIdeal.cpp:455
RawSquareFreeIdeal::_wordsPerTerm
size_t _wordsPerTerm
Definition RawSquareFreeIdeal.h:319
RawSquareFreeIdeal::RawSquareFreeIdeal
RawSquareFreeIdeal()
RawSquareFreeIdeal::back
const Word * back() const
Definition RawSquareFreeIdeal.h:212
RawSquareFreeIdeal::operator==
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
Definition RawSquareFreeIdeal.cpp:597
RawSquareFreeIdeal::colon
void colon(const Word *by)
Definition RawSquareFreeIdeal.cpp:249
RawSquareFreeIdeal::getExclusiveVarGenerator
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
Definition RawSquareFreeIdeal.cpp:521
RawSquareFreeIdeal::getLcm
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
Definition RawSquareFreeIdeal.cpp:765
RawSquareFreeIdeal::getMinSupportGen
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
Definition RawSquareFreeIdeal.cpp:435
RawSquareFreeIdeal::getVarDividesCounts
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
Definition RawSquareFreeIdeal.cpp:366
RawSquareFreeIdeal::compact
void compact(const Word *remove)
Removes the variables that divide remove.
Definition RawSquareFreeIdeal.cpp:264
RawSquareFreeIdeal::removeGenerator
void removeGenerator(size_t index)
Removes the generator at index.
Definition RawSquareFreeIdeal.cpp:480
RawSquareFreeIdeal::print
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
Definition RawSquareFreeIdeal.cpp:179
RawSquareFreeIdeal::getBytesOfMemoryFor
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.
Definition RawSquareFreeIdeal.cpp:110
RawSquareFreeIdeal::begin
iterator begin()
Definition RawSquareFreeIdeal.h:300
RawSquareFreeIdeal::operator=
RawSquareFreeIdeal & operator=(const RawSquareFreeIdeal &ideal)
Resets this object to be a copy of ideal.
Definition RawSquareFreeIdeal.h:55
RawSquareFreeIdeal::_genCount
size_t _genCount
Definition RawSquareFreeIdeal.h:320
RawSquareFreeIdeal::getMaxSupportGen
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
Definition RawSquareFreeIdeal.cpp:415
RawSquareFreeIdeal::getVarCount
size_t getVarCount() const
Definition RawSquareFreeIdeal.h:125
RawSquareFreeIdeal::_memoryEnd
Word * _memoryEnd
Definition RawSquareFreeIdeal.h:321
RawSquareFreeIdeal::getGenerator
Word * getGenerator(size_t index)
Returns the generator at index.
Definition RawSquareFreeIdeal.h:350
RawSquareFreeIdeal::operator!=
bool operator!=(const RawSquareFreeIdeal &ideal) const
Definition RawSquareFreeIdeal.h:207
RawSquareFreeIdeal::colonReminimize
void colonReminimize(const Word *colon)
Performs a colon and minimize.
Definition RawSquareFreeIdeal.cpp:675
RawSquareFreeIdeal::_varCount
size_t _varCount
Definition RawSquareFreeIdeal.h:318
RawSquareFreeIdeal::getNonMultiple
size_t getNonMultiple(size_t var) const
Returns the index of the first generator that var does not divide or getGeneratorCount() if no such g...
Definition RawSquareFreeIdeal.cpp:404
RawSquareFreeIdeal::getGeneratorUnsafe
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 gre...
Definition RawSquareFreeIdeal.h:360
RawSquareFreeIdeal::end
const_iterator end() const
Definition RawSquareFreeIdeal.h:307
RawSquareFreeIdeal::_memory
Word _memory[1]
Definition RawSquareFreeIdeal.h:322
RawSquareFreeIdeal::begin
const_iterator begin() const
Definition RawSquareFreeIdeal.h:302
RawSquareFreeIdeal::getMultiple
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
Definition RawSquareFreeIdeal.cpp:393
RawSquareFreeIdeal::getGeneratorCount
size_t getGeneratorCount() const
Definition RawSquareFreeIdeal.h:124
RawSquareFreeIdeal::insert
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
Definition RawSquareFreeIdeal.cpp:196
RawSquareFreeIdeal::end
iterator end()
Definition RawSquareFreeIdeal.h:305
RawSquareFreeIdeal::transpose
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
Definition RawSquareFreeIdeal.cpp:168
RawSquareFreeIdeal::swap01Exponents
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
Definition RawSquareFreeIdeal.cpp:651
RawSquareFreeIdeal::back
Word * back()
Definition RawSquareFreeIdeal.h:211
RawSquareFreeIdeal::swap
void swap(size_t a, size_t b)
Definition RawSquareFreeIdeal.cpp:590
RawSquareFreeIdeal::setToTransposeOf
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
Definition RawSquareFreeIdeal.cpp:140
RawSquareFreeIdeal::RawSquareFreeIdeal
RawSquareFreeIdeal(const RawSquareFreeIdeal &)
RawSquareFreeIdeal::isMinimallyGenerated
bool isMinimallyGenerated() const
Returns true if no generator divides another.
Definition RawSquareFreeIdeal.cpp:579
RawSquareFreeIdeal::getLcmOfNonMultiples
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
Definition RawSquareFreeIdeal.cpp:304
RawSquareFreeIdeal::insertNonMultiples
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
Definition RawSquareFreeIdeal.cpp:490
RawSquareFreeIdeal::minimize
void minimize()
Definition RawSquareFreeIdeal.cpp:242
RawSquareFreeIdeal::insertIdentity
void insertIdentity()
Definition RawSquareFreeIdeal.cpp:658
RawSquareFreeIdeal::getWordsPerTerm
size_t getWordsPerTerm() const
Definition RawSquareFreeIdeal.h:126
Word
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
ASSERT
#define ASSERT(X)
Definition stdinc.h:86