Frobby 0.9.5
RawSquareFreeIdeal.h
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#ifndef RAW_SQUARE_FREE_IDEAL_GUARD
19#define RAW_SQUARE_FREE_IDEAL_GUARD
20
21#include <ostream>
22#include <vector>
23
24class Ideal;
25class BigIdeal;
26
38 public:
39 static RawSquareFreeIdeal* construct(void* buffer, size_t varCount = 0);
40 static RawSquareFreeIdeal* construct(void* buffer, const Ideal& ideal);
41 static RawSquareFreeIdeal* construct(void* buffer,
42 const RawSquareFreeIdeal& ideal);
43
52 static size_t getBytesOfMemoryFor(size_t varCount, size_t generatorCount);
53
56 {return *construct(this, ideal);}
57
72 void setToTransposeOf(const RawSquareFreeIdeal& ideal, Word* eraseVars = 0);
73
75 void transpose(Word* eraseVars = 0);
76
82 void compact(const Word* remove);
83
85 void print(FILE* file) const;
86
88 void print(ostream& out) const;
89
95 size_t insert(const Ideal& ideal);
96 size_t insert(const BigIdeal& ideal);
97
99 void insert(const RawSquareFreeIdeal& ideal);
100
101 void insert(const Word* term);
102 void insertIdentity();
103
105 bool insert(const std::vector<std::string>& term);
106 void minimize();
107 void colon(const Word* by);
108 void colon(size_t var);
109
111 void colonReminimize(const Word* colon);
112
115 void colonReminimize(size_t var);
116
118 void swap01Exponents();
119
122 void getLcm(Word* lcm) const;
123
124 size_t getGeneratorCount() const {return _genCount;}
125 size_t getVarCount() const {return _varCount;}
126 size_t getWordsPerTerm() const {return _wordsPerTerm;}
127
129 Word* getGenerator(size_t index);
130
132 const Word* getGenerator(size_t index) const;
133
137 Word* getGeneratorUnsafe(size_t index);
138
142 const Word* getGeneratorUnsafe(size_t index) const;
143
146 void getLcmOfNonMultiples(Word* lcm, size_t var) const;
147
150 void getGcdOfMultiples(Word* gcd, size_t var) const;
151
154 void getGcdOfMultiples(Word* gcd, const Word* div) const;
155
157 void getVarDividesCounts(vector<size_t>& counts) const;
158
161 size_t getMultiple(size_t var) const;
162
165 size_t getNonMultiple(size_t var) const;
166
169 size_t getMaxSupportGen() const;
170
173 size_t getMinSupportGen() const;
174
176 void removeGenerator(size_t index);
177
179 void insertNonMultiples(const Word* term, const RawSquareFreeIdeal& ideal);
180
182 void insertNonMultiples(size_t var, const RawSquareFreeIdeal& ideal);
183
187 size_t getNotRelativelyPrime(const Word* term);
188
193
196 bool hasFullSupport(const Word* ignore) const;
197
199 bool isMinimallyGenerated() const;
200
201 void swap(size_t a, size_t b);
202
206 bool operator==(const RawSquareFreeIdeal& ideal) const;
207 bool operator!=(const RawSquareFreeIdeal& ideal) const {
208 return !(*this == ideal);
209 }
210
211 Word* back() {iterator e = end(); --e; return *e;}
212 const Word* back() const {const_iterator e = end(); --e; return *e;}
213
215 void sortLexAscending();
216
220 public:
221 const_iterator(const Word* term, size_t wordsPerTerm):
222 _term(term), _wordsPerTerm(wordsPerTerm) {
223 }
224
225 const Word* operator*() const {return _term;}
228
229 bool operator==(const const_iterator& it) const {
231 return _term == it._term;
232 }
233 bool operator!=(const const_iterator& it) const {
235 return _term != it._term;
236 }
237
238 ptrdiff_t operator-(const const_iterator& it) const {
240 return (_term - it._term) / _wordsPerTerm;
241 }
242 const_iterator operator+(ptrdiff_t i) const {
244 }
245
248 _term = it._term;
249 return *this;
250 }
251
252 private:
253 const Word* _term;
254 const size_t _wordsPerTerm;
255 };
256
259 class iterator {
260 public:
261 iterator(Word* term, size_t wordsPerTerm):
262 _term(term), _wordsPerTerm(wordsPerTerm) {
263 }
264
265 operator const_iterator() const {
267 }
268
269 Word* operator*() const {return _term;}
272
273 bool operator==(const iterator& it) const {
275 return _term == it._term;
276 }
277 bool operator!=(const iterator& it) const {
279 return _term != it._term;
280 }
281
282 ptrdiff_t operator-(const iterator& it) const {
284 return (_term - it._term) / _wordsPerTerm;
285 }
286 iterator operator+(ptrdiff_t i) const {
288 }
291 _term = it._term;
292 return *this;
293 }
294
295 private:
297 const size_t _wordsPerTerm;
298 };
299
304
309
312 bool isValid() const;
313
314 private:
315 RawSquareFreeIdeal(); // Not available
316 RawSquareFreeIdeal(const RawSquareFreeIdeal&); // Not available
317
318 size_t _varCount;
320 size_t _genCount;
322 Word _memory[1]; // variable size array
323};
324
328RawSquareFreeIdeal* newRawSquareFreeIdeal(size_t varCount, size_t capacity);
329
332
341
344
345inline ostream& operator<<(ostream& out, const RawSquareFreeIdeal& ideal) {
346 ideal.print(out);
347 return out;
348}
349
351 ASSERT(index < getGeneratorCount());
352 return _memory + index * getWordsPerTerm();
353}
354
355inline const Word* RawSquareFreeIdeal::getGenerator(size_t index) const {
356 ASSERT(index < getGeneratorCount());
357 return _memory + index * getWordsPerTerm();
358}
359
361 // no assert to check index is valid as this method specifically
362 // allows out-of-bounds access.
363 return _memory + index * getWordsPerTerm();
364}
365
366inline const Word* RawSquareFreeIdeal::getGeneratorUnsafe(size_t index) const {
367 // no assert to check index is valid as this method specifically
368 // allows out-of-bounds access.
369 return _memory + index * getWordsPerTerm();
370}
371
372#endif
ostream & operator<<(ostream &out, const RawSquareFreeIdeal &ideal)
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
RawSquareFreeIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
void deleteRawSquareFreeIdeal(RawSquareFreeIdeal *ideal)
Deallocates memory returned by newRawSquareFreeIdeal().
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
const_iterator doesn't have all it needs to be a proper STL iterator.
bool operator!=(const const_iterator &it) const
const_iterator & operator=(const const_iterator &it)
bool operator==(const const_iterator &it) const
ptrdiff_t operator-(const const_iterator &it) const
const_iterator(const Word *term, size_t wordsPerTerm)
const_iterator operator+(ptrdiff_t i) const
iterator doesn't have all it needs to be a proper STL iterator.
iterator(Word *term, size_t wordsPerTerm)
ptrdiff_t operator-(const iterator &it) const
bool operator!=(const iterator &it) const
iterator operator+(ptrdiff_t i) const
bool operator==(const iterator &it) const
iterator & operator=(const iterator &it)
A bit packed square free ideal placed in a pre-allocated buffer.
void sortLexAscending()
Sorts the generators in ascending lex order.
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.
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var.
const Word * back() const
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
void colon(const Word *by)
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
void compact(const Word *remove)
Removes the variables that divide remove.
void removeGenerator(size_t index)
Removes the generator at index.
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.
RawSquareFreeIdeal & operator=(const RawSquareFreeIdeal &ideal)
Resets this object to be a copy of ideal.
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
size_t getVarCount() const
Word * getGenerator(size_t index)
Returns the generator at index.
bool operator!=(const RawSquareFreeIdeal &ideal) const
void colonReminimize(const Word *colon)
Performs a colon and minimize.
size_t getNonMultiple(size_t var) const
Returns the index of the first generator that var does not divide or getGeneratorCount() if no such g...
Word * getGeneratorUnsafe(size_t index)
Returns a pointer to the memory where a generator at index would be, even if index is equal to or gre...
const_iterator end() const
const_iterator begin() const
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
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).
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
void swap(size_t a, size_t b)
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
RawSquareFreeIdeal(const RawSquareFreeIdeal &)
bool isMinimallyGenerated() const
Returns true if no generator divides another.
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
size_t getWordsPerTerm() const
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
#define ASSERT(X)
Definition stdinc.h:86