Frobby  0.9.0
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 
26 namespace Ops = SquareFreeTermOps;
27 
28 EulerState* 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 
57 EulerState* 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(
62  RawSquareFreeIdeal::getBytesOfMemoryFor(varCount, capacity),
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 
118 bool EulerState::toColonSubState(const Word* pivot) {
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 
129 bool 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 
192  ideal->minimize();
194 }
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 
206 void 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
216 bool 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;
223  if (!ideal->isMinimallyGenerated())
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 }
EulerState * makeSumSubState(size_t pivotVar)
Definition: EulerState.cpp:158
bool toColonSubState(const Word *pivot)
Definition: EulerState.cpp:118
void flipSign()
Definition: EulerState.h:43
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
EulerState * inPlaceStdSplit(size_t pivotVar)
Definition: EulerState.cpp:81
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
Arena * _alloc
Definition: EulerState.h:79
void transpose()
Definition: EulerState.cpp:190
void colonReminimize(const Word *colon)
Performs a colon and minimize.
RawSquareFreeIdeal * ideal
Definition: EulerState.h:76
void compactEliminatedVariablesIfProfitable()
Definition: EulerState.cpp:196
size_t getNonEliminatedVarCount() const
Definition: EulerState.cpp:240
Word * getGenerator(size_t index)
Returns the generator at index.
void toZero()
Definition: EulerState.cpp:233
void print(FILE *out)
Definition: EulerState.cpp:206
#define ASSERT(X)
Definition: stdinc.h:85
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
void setToIdentity(Word *res, const Word *resEnd)
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
void removeGenerator(size_t index)
Definition: EulerState.h:55
A bit packed square free ideal placed in a pre-allocated buffer.
size_t getVarCount() const
Definition: EulerState.h:52
void setExponent(Word *a, size_t var, bool value)
void compact(const Word *remove)
Removes the variables that divide remove.
pair< T *, T * > allocArrayNoCon(size_t elementCount)
As alloc(elementCount * sizeof(T)).
Definition: Arena.h:250
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:92
size_t getVarCount() const
void print(FILE *out, const ColumnPrinter &pr)
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
This is an arena allocator.
Definition: Arena.h:53
static EulerState * construct(const Ideal &idealParam, Arena *arena)
Definition: EulerState.cpp:28
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
Definition: Arena.h:180
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
size_t getWordCount(size_t varCount)
static EulerState * rawConstruct(size_t varCount, size_t capacity, Arena *arena)
Definition: EulerState.cpp:57
size_t getGeneratorCount() const
Definition: Ideal.h:57
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...
bool isMinimallyGenerated() const
Returns true if no generator divides another.
size_t getVarCount() const
Definition: Ideal.h:56
const Word * getEliminatedVars() const
Definition: EulerState.h:51
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void toColonSubStateNoReminimizeNecessary(size_t pivotVar)
Definition: EulerState.cpp:140
size_t getSizeOfSupport(const Word *a, size_t varCount)
size_t getGeneratorCount() const
void assign(Word *a, const Word *b, size_t varCount)
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
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...
EulerState * inPlaceGenSplit(size_t pivotIndex)
Definition: EulerState.cpp:95
EulerState * _parent
Definition: EulerState.h:80
void colon(const Word *by)
Word * eliminated
Definition: EulerState.h:77
RawSquareFreeIdeal & getIdeal()
Definition: EulerState.h:49