EulerState.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2011 Bjarke Hammersholt Roune (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/.
*/
#include "stdinc.h"
#include "EulerState.h"
#include "RawSquareFreeTerm.h"
#include "Ideal.h"
#include "Arena.h"
#include <limits>
namespace Ops = SquareFreeTermOps;
EulerState* EulerState::construct(const Ideal& idealParam, Arena* arena) {
ASSERT(arena != 0);
const size_t varCount = idealParam.getVarCount();
const size_t capacity = idealParam.getGeneratorCount();
EulerState* state = rawConstruct(varCount, capacity, arena);
state->ideal->insert(idealParam);
Ops::setToIdentity(state->eliminated, varCount);
ASSERT(state->debugIsValid());
return state;
}
EulerState* EulerState::construct
(const RawSquareFreeIdeal& idealParam, Arena* arena) {
ASSERT(arena != 0);
const size_t varCount = idealParam.getVarCount();
const size_t capacity = idealParam.getGeneratorCount();
EulerState* state = rawConstruct(varCount, capacity, arena);
state->ideal->insert(idealParam);
Ops::setToIdentity(state->eliminated, varCount);
ASSERT(state->debugIsValid());
return state;
}
EulerState* EulerState::rawConstruct(size_t varCount, size_t capacity,
Arena* arena) {
ASSERT(arena != 0);
// Do both ways around to support transpose.
size_t bytesIdeal = std::max(
RawSquareFreeIdeal::getBytesOfMemoryFor(varCount, capacity),
RawSquareFreeIdeal::getBytesOfMemoryFor(capacity, varCount));
size_t wordsElim = std::max(
Ops::getWordCount(varCount), Ops::getWordCount(capacity));
if (bytesIdeal == 0 || wordsElim == 0)
throw bad_alloc();
EulerState* state =
static_cast<EulerState*>(arena->alloc(sizeof(EulerState)));
state->_alloc = arena;
state->ideal =
RawSquareFreeIdeal::construct(arena->alloc(bytesIdeal), varCount);
state->eliminated = arena->allocArrayNoCon<Word>(wordsElim).first;
state->sign = 1;
state->_parent = 0;
return state;
}
EulerState* EulerState::inPlaceStdSplit(size_t pivotVar) {
ASSERT(pivotVar < getVarCount());
EulerState* subState = makeSumSubState(pivotVar);
toColonSubState(pivotVar);
return subState;
}
EulerState* EulerState::inPlaceStdSplit(Word* pivot) {
ASSERT(pivot != 0);
EulerState* subState = makeSumSubState(pivot);
toColonSubState(pivot);
return subState;
}
EulerState* EulerState::inPlaceGenSplit(size_t pivotIndex) {
ASSERT(pivotIndex < getIdeal().getGeneratorCount());
const size_t varCount = ideal->getVarCount();
const size_t capacity = ideal->getGeneratorCount();
EulerState* subState = rawConstruct(varCount, capacity, _alloc);
subState->_parent = this;
*subState->ideal = *ideal;
Ops::assign(subState->eliminated, eliminated, varCount);
subState->sign = sign;
const Word* pivot = getIdeal().getGenerator(pivotIndex);
subState->removeGenerator(pivotIndex);
subState->toColonSubState(pivot);
subState->flipSign();
removeGenerator(pivotIndex);
ASSERT(subState->debugIsValid());
return subState;
}
bool EulerState::toColonSubState(const Word* pivot) {
ASSERT(pivot != 0);
ASSERT(Ops::isRelativelyPrime(pivot, getEliminatedVars(), getVarCount()));
const size_t genCountBefore = getIdeal().getGeneratorCount();
ideal->colonReminimize(pivot);
Ops::lcmInPlace(eliminated, pivot, ideal->getVarCount());
ASSERT(debugIsValid());
return genCountBefore != getIdeal().getGeneratorCount();
}
bool EulerState::toColonSubState(size_t pivotVar) {
ASSERT(pivotVar < getVarCount());
ASSERT(Ops::getExponent(getEliminatedVars(), pivotVar) == 0);
const size_t genCountBefore = getIdeal().getGeneratorCount();
ideal->colonReminimize(pivotVar);
Ops::setExponent(eliminated, pivotVar, true);
ASSERT(debugIsValid());
return genCountBefore != getIdeal().getGeneratorCount();
}
void EulerState::toColonSubStateNoReminimizeNecessary(size_t pivotVar) {
ASSERT(pivotVar < getVarCount());
ASSERT(Ops::getExponent(getEliminatedVars(), pivotVar) == 0);
ideal->colon(pivotVar);
Ops::setExponent(eliminated, pivotVar, true);
ASSERT(debugIsValid());
}
void EulerState::toColonSubStateNoReminimizeNecessary(Word* pivot) {
ASSERT(pivot != 0);
ASSERT(Ops::isRelativelyPrime(getEliminatedVars(), pivot, getVarCount()));
ideal->colon(pivot);
Ops::lcmInPlace(eliminated, pivot, getVarCount());
ASSERT(debugIsValid());
}
EulerState* EulerState::makeSumSubState(size_t pivotVar) {
const size_t varCount = ideal->getVarCount();
const size_t capacity = ideal->getGeneratorCount();
EulerState* subState = rawConstruct(varCount, capacity, _alloc);
subState->_parent = this;
subState->ideal->insertNonMultiples(pivotVar, *ideal);
Ops::assign(subState->eliminated, eliminated, varCount);
Ops::setExponent(subState->eliminated, pivotVar, 1);
subState->sign = sign;
subState->flipSign();
ASSERT(subState->debugIsValid());
return subState;
}
EulerState* EulerState::makeSumSubState(Word* pivot) {
const size_t varCount = ideal->getVarCount();
const size_t capacity = ideal->getGeneratorCount() + 1;
EulerState* subState = rawConstruct(varCount, capacity, _alloc);
subState->_parent = this;
subState->ideal->insertNonMultiples(pivot, *ideal);
ASSERT(subState->ideal->getGeneratorCount() < ideal->getGeneratorCount());
subState->ideal->insert(pivot);
Ops::assign(subState->eliminated, eliminated, varCount);
subState->sign = sign;
ASSERT(subState->debugIsValid());
return subState;
}
void EulerState::transpose() {
ideal->transpose(eliminated);
ideal->minimize();
Ops::setToIdentity(eliminated, ideal->getVarCount());
}
void EulerState::compactEliminatedVariablesIfProfitable() {
const size_t varCount = getVarCount();
const size_t varsLeft = getNonEliminatedVarCount();
if (Ops::getWordCount(varCount) > Ops::getWordCount(varsLeft)) {
ideal->compact(eliminated);
Ops::setToIdentity(eliminated, ideal->getVarCount());
ASSERT(debugIsValid());
}
}
void EulerState::print(FILE* out) {
fputs("** an Euler characteristic algorithm state:\n", out);
fprintf(out, "State sign: %s\n", sign == 1 ? "+1" : "-1");
fputs("Eliminated: ", out);
Ops::print(out, eliminated, ideal->getVarCount());
fputc('\n', out);
ideal->print(out);
}
#ifdef DEBUG
bool EulerState::debugIsValid() const {
if (ideal == 0 || eliminated == 0 || _alloc == 0)
return false;
if (sign != 1 && sign != -1)
return false;
if (!Ops::isValid(eliminated, ideal->getVarCount()))
return false;
if (!ideal->isMinimallyGenerated())
return false;
if (ideal->getVarCount() != 0 &&
ideal->getNotRelativelyPrime(eliminated) !=
ideal->getGeneratorCount())
return false;
return true;
}
#endif
void EulerState::toZero() {
ideal = 0;
eliminated = 0;
sign = 1;
_parent = 0;
}
size_t EulerState::getNonEliminatedVarCount() const {
const size_t eliminatedVarCount =
Ops::getSizeOfSupport(getEliminatedVars(), getVarCount());
ASSERT(getVarCount() >= eliminatedVarCount);
return getVarCount() - eliminatedVarCount;
}
Arena.h
EulerState.h
Ideal.h
RawSquareFreeTerm.h
Arena
This is an arena allocator.
Definition Arena.h:53
Arena::alloc
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
Definition Arena.h:180
Arena::allocArrayNoCon
pair< T *, T * > allocArrayNoCon(size_t elementCount)
As alloc(elementCount * sizeof(T)).
Definition Arena.h:250
EulerState::removeGenerator
void removeGenerator(size_t index)
Definition EulerState.h:55
EulerState::rawConstruct
static EulerState * rawConstruct(size_t varCount, size_t capacity, Arena *arena)
Definition EulerState.cpp:57
EulerState::makeSumSubState
EulerState * makeSumSubState(size_t pivotVar)
Definition EulerState.cpp:158
EulerState::inPlaceGenSplit
EulerState * inPlaceGenSplit(size_t pivotIndex)
Definition EulerState.cpp:95
EulerState::flipSign
void flipSign()
Definition EulerState.h:43
EulerState::toColonSubStateNoReminimizeNecessary
void toColonSubStateNoReminimizeNecessary(size_t pivotVar)
Definition EulerState.cpp:140
EulerState::eliminated
Word * eliminated
Definition EulerState.h:77
EulerState::compactEliminatedVariablesIfProfitable
void compactEliminatedVariablesIfProfitable()
Definition EulerState.cpp:196
EulerState::toZero
void toZero()
Definition EulerState.cpp:233
EulerState::getIdeal
RawSquareFreeIdeal & getIdeal()
Definition EulerState.h:49
EulerState::toColonSubState
bool toColonSubState(const Word *pivot)
Definition EulerState.cpp:118
EulerState::construct
static EulerState * construct(const Ideal &idealParam, Arena *arena)
Definition EulerState.cpp:28
EulerState::ideal
RawSquareFreeIdeal * ideal
Definition EulerState.h:76
EulerState::_alloc
Arena * _alloc
Definition EulerState.h:79
EulerState::transpose
void transpose()
Definition EulerState.cpp:190
EulerState::getVarCount
size_t getVarCount() const
Definition EulerState.h:52
EulerState::inPlaceStdSplit
EulerState * inPlaceStdSplit(size_t pivotVar)
Definition EulerState.cpp:81
EulerState::print
void print(FILE *out)
Definition EulerState.cpp:206
EulerState::getEliminatedVars
const Word * getEliminatedVars() const
Definition EulerState.h:51
EulerState::_parent
EulerState * _parent
Definition EulerState.h:80
EulerState::sign
int sign
Definition EulerState.h:78
EulerState::EulerState
EulerState(const EulerState &)
EulerState::getNonEliminatedVarCount
size_t getNonEliminatedVarCount() const
Definition EulerState.cpp:240
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition Ideal.h:57
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
RawSquareFreeIdeal
A bit packed square free ideal placed in a pre-allocated buffer.
Definition RawSquareFreeIdeal.h:37
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::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::getVarCount
size_t getVarCount() const
Definition RawSquareFreeIdeal.h:125
RawSquareFreeIdeal::getGenerator
Word * getGenerator(size_t index)
Returns the generator at index.
Definition RawSquareFreeIdeal.h:350
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::isMinimallyGenerated
bool isMinimallyGenerated() const
Returns true if no generator divides another.
Definition RawSquareFreeIdeal.cpp:579
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
SquareFreeTermOps
Definition RawSquareFreeTerm.cpp:24
SquareFreeTermOps::setExponent
void setExponent(Word *a, size_t var, bool value)
Definition RawSquareFreeTerm.h:170
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::getSizeOfSupport
size_t getSizeOfSupport(const Word *a, size_t varCount)
Definition RawSquareFreeTerm.cpp:71
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::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::setToIdentity
void setToIdentity(Word *res, const Word *resEnd)
Definition RawSquareFreeTerm.cpp:115
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
Word
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
ASSERT
#define ASSERT(X)
Definition stdinc.h:86