Frobby 0.9.5
EulerState.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2011 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "EulerState.h"
19
20#include "RawSquareFreeTerm.h"
21#include "Ideal.h"
22#include "Arena.h"
23
24#include <limits>
25
26namespace Ops = SquareFreeTermOps;
27
29 ASSERT(arena != 0);
30
31 const size_t varCount = idealParam.getVarCount();
32 const size_t capacity = idealParam.getGeneratorCount();
34
35 state->ideal->insert(idealParam);
36 Ops::setToIdentity(state->eliminated, varCount);
37 ASSERT(state->debugIsValid());
38
39 return state;
40}
41
44 ASSERT(arena != 0);
45
46 const size_t varCount = idealParam.getVarCount();
47 const size_t capacity = idealParam.getGeneratorCount();
49
50 state->ideal->insert(idealParam);
51 Ops::setToIdentity(state->eliminated, varCount);
52 ASSERT(state->debugIsValid());
53
54 return state;
55}
56
58 Arena* arena) {
59 ASSERT(arena != 0);
60 // Do both ways around to support transpose.
61 size_t bytesIdeal = std::max(
64 size_t wordsElim = std::max(
66 if (bytesIdeal == 0 || wordsElim == 0)
67 throw bad_alloc();
68
70 static_cast<EulerState*>(arena->alloc(sizeof(EulerState)));
72 state->ideal =
74 state->eliminated = arena->allocArrayNoCon<Word>(wordsElim).first;
75 state->sign = 1;
76 state->_parent = 0;
77
78 return state;
79}
80
87
94
96 ASSERT(pivotIndex < getIdeal().getGeneratorCount());
97
98 const size_t varCount = ideal->getVarCount();
99 const size_t capacity = ideal->getGeneratorCount();
101 subState->_parent = this;
102
103 *subState->ideal = *ideal;
104
106 subState->sign = sign;
107
109 subState->removeGenerator(pivotIndex);
110 subState->toColonSubState(pivot);
111 subState->flipSign();
113
114 ASSERT(subState->debugIsValid());
115 return subState;
116}
117
128
139
148
157
159 const size_t varCount = ideal->getVarCount();
160 const size_t capacity = ideal->getGeneratorCount();
162 subState->_parent = this;
163
164 subState->ideal->insertNonMultiples(pivotVar, *ideal);
166 Ops::setExponent(subState->eliminated, pivotVar, 1);
167 subState->sign = sign;
168 subState->flipSign();
169
170 ASSERT(subState->debugIsValid());
171 return subState;
172}
173
175 const size_t varCount = ideal->getVarCount();
176 const size_t capacity = ideal->getGeneratorCount() + 1;
178 subState->_parent = this;
179
180 subState->ideal->insertNonMultiples(pivot, *ideal);
181 ASSERT(subState->ideal->getGeneratorCount() < ideal->getGeneratorCount());
182 subState->ideal->insert(pivot);
184 subState->sign = sign;
185
186 ASSERT(subState->debugIsValid());
187 return subState;
188}
189
195
205
207 fputs("** an Euler characteristic algorithm state:\n", out);
208 fprintf(out, "State sign: %s\n", sign == 1 ? "+1" : "-1");
209 fputs("Eliminated: ", out);
211 fputc('\n', out);
212 ideal->print(out);
213}
214
215#ifdef DEBUG
216bool EulerState::debugIsValid() const {
217 if (ideal == 0 || eliminated == 0 || _alloc == 0)
218 return false;
219 if (sign != 1 && sign != -1)
220 return false;
222 return false;
224 return false;
225 if (ideal->getVarCount() != 0 &&
228 return false;
229 return true;
230}
231#endif
232
234 ideal = 0;
235 eliminated = 0;
236 sign = 1;
237 _parent = 0;
238}
239
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
This is an arena allocator.
Definition Arena.h:53
void removeGenerator(size_t index)
Definition EulerState.h:55
static EulerState * rawConstruct(size_t varCount, size_t capacity, Arena *arena)
EulerState * makeSumSubState(size_t pivotVar)
EulerState * inPlaceGenSplit(size_t pivotIndex)
void toColonSubStateNoReminimizeNecessary(size_t pivotVar)
Word * eliminated
Definition EulerState.h:77
void compactEliminatedVariablesIfProfitable()
void toZero()
RawSquareFreeIdeal & getIdeal()
Definition EulerState.h:49
bool toColonSubState(const Word *pivot)
static EulerState * construct(const Ideal &idealParam, Arena *arena)
RawSquareFreeIdeal * ideal
Definition EulerState.h:76
Arena * _alloc
Definition EulerState.h:79
void transpose()
size_t getVarCount() const
Definition EulerState.h:52
EulerState * inPlaceStdSplit(size_t pivotVar)
void print(FILE *out)
const Word * getEliminatedVars() const
Definition EulerState.h:51
EulerState * _parent
Definition EulerState.h:80
size_t getNonEliminatedVarCount() const
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
A bit packed square free ideal placed in a pre-allocated buffer.
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
void colon(const Word *by)
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.
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.
size_t getVarCount() const
Word * getGenerator(size_t index)
Returns the generator at index.
void colonReminimize(const Word *colon)
Performs a colon and minimize.
size_t getGeneratorCount() const
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
bool isMinimallyGenerated() const
Returns true if no generator divides another.
void setExponent(Word *a, size_t var, bool value)
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.
size_t getWordCount(size_t varCount)
size_t getSizeOfSupport(const Word *a, size_t varCount)
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void print(FILE *file, const Word *term, size_t varCount)
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void setToIdentity(Word *res, const Word *resEnd)
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
#define ASSERT(X)
Definition stdinc.h:86