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
28EulerState* EulerState::construct(const Ideal& idealParam, Arena* arena) {
29 ASSERT(arena != 0);
30
31 const size_t varCount = idealParam.getVarCount();
32 const size_t capacity = idealParam.getGeneratorCount();
33 EulerState* state = rawConstruct(varCount, capacity, arena);
34
35 state->ideal->insert(idealParam);
36 Ops::setToIdentity(state->eliminated, varCount);
37 ASSERT(state->debugIsValid());
38
39 return state;
40}
41
43(const RawSquareFreeIdeal& idealParam, Arena* arena) {
44 ASSERT(arena != 0);
45
46 const size_t varCount = idealParam.getVarCount();
47 const size_t capacity = idealParam.getGeneratorCount();
48 EulerState* state = rawConstruct(varCount, capacity, arena);
49
50 state->ideal->insert(idealParam);
51 Ops::setToIdentity(state->eliminated, varCount);
52 ASSERT(state->debugIsValid());
53
54 return state;
55}
56
57EulerState* EulerState::rawConstruct(size_t varCount, size_t capacity,
58 Arena* arena) {
59 ASSERT(arena != 0);
60 // Do both ways around to support transpose.
61 size_t bytesIdeal = std::max(
63 RawSquareFreeIdeal::getBytesOfMemoryFor(capacity, varCount));
64 size_t wordsElim = std::max(
65 Ops::getWordCount(varCount), Ops::getWordCount(capacity));
66 if (bytesIdeal == 0 || wordsElim == 0)
67 throw bad_alloc();
68
69 EulerState* state =
70 static_cast<EulerState*>(arena->alloc(sizeof(EulerState)));
71 state->_alloc = arena;
72 state->ideal =
73 RawSquareFreeIdeal::construct(arena->alloc(bytesIdeal), varCount);
74 state->eliminated = arena->allocArrayNoCon<Word>(wordsElim).first;
75 state->sign = 1;
76 state->_parent = 0;
77
78 return state;
79}
80
82 ASSERT(pivotVar < getVarCount());
83 EulerState* subState = makeSumSubState(pivotVar);
84 toColonSubState(pivotVar);
85 return subState;
86}
87
89 ASSERT(pivot != 0);
90 EulerState* subState = makeSumSubState(pivot);
91 toColonSubState(pivot);
92 return subState;
93}
94
96 ASSERT(pivotIndex < getIdeal().getGeneratorCount());
97
98 const size_t varCount = ideal->getVarCount();
99 const size_t capacity = ideal->getGeneratorCount();
100 EulerState* subState = rawConstruct(varCount, capacity, _alloc);
101 subState->_parent = this;
102
103 *subState->ideal = *ideal;
104
105 Ops::assign(subState->eliminated, eliminated, varCount);
106 subState->sign = sign;
107
108 const Word* pivot = getIdeal().getGenerator(pivotIndex);
109 subState->removeGenerator(pivotIndex);
110 subState->toColonSubState(pivot);
111 subState->flipSign();
112 removeGenerator(pivotIndex);
113
114 ASSERT(subState->debugIsValid());
115 return subState;
116}
117
119 ASSERT(pivot != 0);
121
122 const size_t genCountBefore = getIdeal().getGeneratorCount();
123 ideal->colonReminimize(pivot);
125 ASSERT(debugIsValid());
126 return genCountBefore != getIdeal().getGeneratorCount();
127}
128
129bool EulerState::toColonSubState(size_t pivotVar) {
130 ASSERT(pivotVar < getVarCount());
131 ASSERT(Ops::getExponent(getEliminatedVars(), pivotVar) == 0);
132
133 const size_t genCountBefore = getIdeal().getGeneratorCount();
134 ideal->colonReminimize(pivotVar);
135 Ops::setExponent(eliminated, pivotVar, true);
136 ASSERT(debugIsValid());
137 return genCountBefore != getIdeal().getGeneratorCount();
138}
139
141 ASSERT(pivotVar < getVarCount());
142 ASSERT(Ops::getExponent(getEliminatedVars(), pivotVar) == 0);
143
144 ideal->colon(pivotVar);
145 Ops::setExponent(eliminated, pivotVar, true);
146 ASSERT(debugIsValid());
147}
148
150 ASSERT(pivot != 0);
152
153 ideal->colon(pivot);
155 ASSERT(debugIsValid());
156}
157
159 const size_t varCount = ideal->getVarCount();
160 const size_t capacity = ideal->getGeneratorCount();
161 EulerState* subState = rawConstruct(varCount, capacity, _alloc);
162 subState->_parent = this;
163
164 subState->ideal->insertNonMultiples(pivotVar, *ideal);
165 Ops::assign(subState->eliminated, eliminated, varCount);
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;
177 EulerState* subState = rawConstruct(varCount, capacity, _alloc);
178 subState->_parent = this;
179
180 subState->ideal->insertNonMultiples(pivot, *ideal);
182 subState->ideal->insert(pivot);
183 Ops::assign(subState->eliminated, eliminated, varCount);
184 subState->sign = sign;
185
186 ASSERT(subState->debugIsValid());
187 return subState;
188}
189
195
197 const size_t varCount = getVarCount();
198 const size_t varsLeft = getNonEliminatedVarCount();
199 if (Ops::getWordCount(varCount) > Ops::getWordCount(varsLeft)) {
202 ASSERT(debugIsValid());
203 }
204}
205
206void EulerState::print(FILE* out) {
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
241 const size_t eliminatedVarCount =
243
244 ASSERT(getVarCount() >= eliminatedVarCount);
245 return getVarCount() - eliminatedVarCount;
246}
This is an arena allocator.
Definition Arena.h:53
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
Definition Arena.h:180
pair< T *, T * > allocArrayNoCon(size_t elementCount)
As alloc(elementCount * sizeof(T)).
Definition Arena.h:250
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 flipSign()
Definition EulerState.h:43
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
size_t getGeneratorCount() const
Definition Ideal.h:57
size_t getVarCount() const
Definition Ideal.h:56
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
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
bool isMinimallyGenerated() const
Returns true if no generator divides another.
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
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)
This header file includes common definitions and is included as the first line of code in every imple...
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
#define ASSERT(X)
Definition stdinc.h:86