RawSquareFreeTerm.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_TERM_GUARD
#define RAW_SQUARE_FREE_TERM_GUARD
#include <ostream>
#include <algorithm>
#include <vector>
namespace SquareFreeTermOps {
bool isIdentity(const Word* a, Word* aEnd);
bool isIdentity(const Word* a, size_t varCount);
size_t getSizeOfSupport(const Word* a, size_t varCount);
size_t getWordCount(size_t varCount);
void compact(Word* compacted, const Word* term,
const Word* remove, size_t varCount);
void setToIdentity(Word* res, const Word* resEnd);
void setToIdentity(Word* res, size_t varCount);
void setToAllVarProd(Word* res, size_t varCount);
Word* newTerm(size_t varCount);
Word* newTermParse(const char* str);
void deleteTerm(Word* term);
bool divides(const Word* a, const Word* aEnd, const Word* b);
bool lexLess(const Word* a, const Word* b, size_t varCount);
void colon(Word* res, const Word* resEnd, const Word* a, const Word* b);
void colonInPlace(Word* res, const Word* resEnd, const Word* b);
void assign(Word* a, const Word* aEnd, const Word* b);
void assign(Word* a, const Word* b, size_t varCount);
bool encodeTerm(Word* encoded, const Exponent* term, const size_t varCount);
bool encodeTerm(Word* encoded, const std::vector<mpz_class>& term, const size_t varCount);
bool encodeTerm(Word* encoded, const std::vector<std::string>& it, const size_t varCount);
inline size_t getBitOffset(size_t var);
inline size_t getWordOffset(size_t var);
bool hasFullSupport(const Word* a, size_t varCount);
void lcm(Word* res, const Word* resEnd,
const Word* a, const Word* b);
void lcm(Word* res, const Word* a, const Word* b, size_t varCount);
void lcmInPlace(Word* res, const Word* resEnd, const Word* a);
void lcmInPlace(Word* res, const Word* a, size_t varCount);
void gcd(Word* res, const Word* resEnd, const Word* a, const Word* b);
void gcd(Word* res, const Word* a, const Word* b, size_t varCount);
void gcdInPlace(Word* res, const Word* resEnd, const Word* a);
void gcdInPlace(Word* res, const Word* a, size_t varCount);
bool isRelativelyPrime(const Word* a, const Word* aEnd, const Word* b);
bool isRelativelyPrime(const Word* a, const Word* b, size_t varCount);
void setExponent(Word* a, size_t var, bool value);
bool getExponent(const Word* a, size_t var);
void swap(Word* a, Word* b, size_t varCount);
void swap(Word* a, Word* aEnd, Word* b);
void invert(Word* a, size_t varCount);
size_t getVarIfPure(const Word* const a, size_t varCount);
void decrementAtSupport(const Word* a, size_t* inc, size_t varCount);
void toZeroAtSupport(const Word* a, size_t* inc, size_t varCount);
bool equals(const Word* a, const Word* b, size_t varCount);
bool isValid(const Word* a, size_t varCount);
inline bool divides(const Word* a, const Word* aEnd, const Word* b) {
for (; a != aEnd; ++a, ++b)
if ((*a & (~*b)) != 0)
return false;
return true;
}
inline bool getExponent(const Word* a, size_t var) {
const Word word = a[getWordOffset(var)];
const Word bitMask = ((Word)1) << getBitOffset(var);
return word & bitMask;
}
inline size_t getBitOffset(size_t var) {
return var % BitsPerWord;
}
inline size_t getWordOffset(size_t var) {
return var / BitsPerWord;
}
inline void assign(Word* a, const Word* aEnd, const Word* b) {
for (; a != aEnd; ++a, ++b)
*a = *b;
}
inline void setExponent(Word* a, size_t var, bool value) {
Word& word = a[getWordOffset(var)];
const size_t bitOffset = getBitOffset(var);
const Word setBit = ((Word)1) << bitOffset;
const Word valueBit = ((Word)value) << bitOffset;
word = (word & (~setBit)) | valueBit;
}
inline void swap(Word* a, Word* aEnd, Word* b) {
for (; a != aEnd; ++a, ++b)
std::swap(*a, *b);
}
inline bool hasFullSupport(const Word* a, size_t varCount) {
const Word allOnes = ~((Word)0);
for (; varCount >= BitsPerWord; varCount -= BitsPerWord, ++a)
if (*a != allOnes)
return false;
if (varCount == 0)
return true;
const Word fullSupportWord = (((Word)1) << varCount) - 1;
return *a == fullSupportWord;
}
inline bool isRelativelyPrime(const Word* a, const Word* aEnd, const Word* b) {
for (; a != aEnd; ++a, ++b)
if ((*a) & (*b))
return false;
return true;
}
void print(FILE* file, const Word* term, size_t varCount);
void print(ostream& out, const Word* term, size_t varCount);
}
#endif
SquareFreeTermOps
Definition RawSquareFreeTerm.cpp:24
SquareFreeTermOps::getWordOffset
size_t getWordOffset(size_t var)
Definition RawSquareFreeTerm.h:161
SquareFreeTermOps::setExponent
void setExponent(Word *a, size_t var, bool value)
Definition RawSquareFreeTerm.h:170
SquareFreeTermOps::newTerm
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
Definition RawSquareFreeTerm.cpp:139
SquareFreeTermOps::isValid
bool isValid(const Word *a, size_t varCount)
The unused bits at the end of the last word must be zero for the functions here to work correctly.
Definition RawSquareFreeTerm.cpp:415
SquareFreeTermOps::getWordCount
size_t getWordCount(size_t varCount)
Definition RawSquareFreeTerm.cpp:91
SquareFreeTermOps::colon
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition RawSquareFreeTerm.cpp:176
SquareFreeTermOps::getBitOffset
size_t getBitOffset(size_t var)
Definition RawSquareFreeTerm.h:157
SquareFreeTermOps::encodeTerm
bool encodeTerm(Word *encoded, const Exponent *term, const size_t varCount)
Assigns the RawSquareFreeTerm-encoded form of term to encoded and returns true if term is square free...
Definition RawSquareFreeTerm.cpp:193
SquareFreeTermOps::getVarIfPure
size_t getVarIfPure(const Word *const a, size_t varCount)
Returns var if a equals var.
Definition RawSquareFreeTerm.cpp:322
SquareFreeTermOps::newTermParse
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
Definition RawSquareFreeTerm.cpp:25
SquareFreeTermOps::invert
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
Definition RawSquareFreeTerm.cpp:311
SquareFreeTermOps::decrementAtSupport
void decrementAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, decrement inc[var] by one.
Definition RawSquareFreeTerm.cpp:356
SquareFreeTermOps::lexLess
bool lexLess(const Word *a, const Word *b, size_t varCount)
Definition RawSquareFreeTerm.cpp:158
SquareFreeTermOps::isIdentity
bool isIdentity(const Word *a, Word *aEnd)
Definition RawSquareFreeTerm.cpp:51
SquareFreeTermOps::hasFullSupport
bool hasFullSupport(const Word *a, size_t varCount)
Definition RawSquareFreeTerm.h:183
SquareFreeTermOps::toZeroAtSupport
void toZeroAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, set inc[var] to zero.
Definition RawSquareFreeTerm.cpp:376
SquareFreeTermOps::getSizeOfSupport
size_t getSizeOfSupport(const Word *a, size_t varCount)
Definition RawSquareFreeTerm.cpp:71
SquareFreeTermOps::colonInPlace
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
Definition RawSquareFreeTerm.cpp:181
SquareFreeTermOps::lcmInPlace
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
Definition RawSquareFreeTerm.cpp:264
SquareFreeTermOps::getExponent
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
Definition RawSquareFreeTerm.h:151
SquareFreeTermOps::print
void print(FILE *file, const Word *term, size_t varCount)
Definition RawSquareFreeTerm.cpp:35
SquareFreeTermOps::compact
void compact(Word *compacted, const Word *term, const Word *remove, size_t varCount)
For every variable var that divides remove, remove the space for that variable in term and put the re...
Definition RawSquareFreeTerm.cpp:100
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition RawSquareFreeTerm.cpp:251
SquareFreeTermOps::setToAllVarProd
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
Definition RawSquareFreeTerm.cpp:128
SquareFreeTermOps::equals
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
Definition RawSquareFreeTerm.cpp:397
SquareFreeTermOps::divides
bool divides(const Word *a, const Word *aEnd, const Word *b)
Returns true if a divides b.
Definition RawSquareFreeTerm.h:144
SquareFreeTermOps::swap
void swap(Word *a, Word *b, size_t varCount)
Definition RawSquareFreeTerm.cpp:425
SquareFreeTermOps::deleteTerm
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
Definition RawSquareFreeTerm.cpp:154
SquareFreeTermOps::gcdInPlace
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
Definition RawSquareFreeTerm.cpp:288
SquareFreeTermOps::assign
void assign(Word *a, const Word *b, size_t varCount)
Definition RawSquareFreeTerm.cpp:186
SquareFreeTermOps::isRelativelyPrime
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
Definition RawSquareFreeTerm.cpp:300
SquareFreeTermOps::gcd
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition RawSquareFreeTerm.cpp:276
SquareFreeTermOps::setToIdentity
void setToIdentity(Word *res, const Word *resEnd)
Definition RawSquareFreeTerm.cpp:115
Exponent
unsigned int Exponent
Definition stdinc.h:89
BitsPerWord
static const size_t BitsPerWord
Definition stdinc.h:94
Word
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93