Frobby  0.9.0
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 
24 class Ideal;
25 class 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 
192  size_t getExclusiveVarGenerator();
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 {
243  return const_iterator(_term + i * _wordsPerTerm, _wordsPerTerm);
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;}
270  iterator operator++() {_term += _wordsPerTerm; return *this;}
271  iterator operator--() {_term -= _wordsPerTerm; return *this;}
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 {
287  return iterator(_term + i * _wordsPerTerm, _wordsPerTerm);
288  }
291  _term = it._term;
292  return *this;
293  }
294 
295  private:
297  const size_t _wordsPerTerm;
298  };
299 
301  {return iterator(_memory, getWordsPerTerm());}
304 
306  {return iterator(_memoryEnd, getWordsPerTerm());}
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 
328 RawSquareFreeIdeal* newRawSquareFreeIdeal(size_t varCount, size_t capacity);
329 
332 
341 
344 
345 inline ostream& operator<<(ostream& out, const RawSquareFreeIdeal& ideal) {
346  ideal.print(out);
347  return out;
348 }
349 
350 inline Word* RawSquareFreeIdeal::getGenerator(size_t index) {
351  ASSERT(index < getGeneratorCount());
352  return _memory + index * getWordsPerTerm();
353 }
354 
355 inline 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 
366 inline 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
void sortLexAscending()
Sorts the generators in ascending lex order.
const_iterator begin() const
bool operator==(const iterator &it) const
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
iterator & operator=(const iterator &it)
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
const_iterator doesn't have all it needs to be a proper STL iterator.
ostream & operator<<(ostream &out, const RawSquareFreeIdeal &ideal)
iterator operator+(ptrdiff_t i) const
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
void colonReminimize(const Word *colon)
Performs a colon and minimize.
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
Word * getGenerator(size_t index)
Returns the generator at index.
void deleteRawSquareFreeIdeal(RawSquareFreeIdeal *ideal)
Deallocates memory returned by newRawSquareFreeIdeal().
#define ASSERT(X)
Definition: stdinc.h:85
bool operator!=(const iterator &it) const
void removeGenerator(size_t index)
Removes the generator at index.
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
A bit packed square free ideal placed in a pre-allocated buffer.
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
const_iterator(const Word *term, size_t wordsPerTerm)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
bool operator!=(const RawSquareFreeIdeal &ideal) const
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...
size_t getGeneratorCount() const
void compact(const Word *remove)
Removes the variables that divide remove.
iterator doesn't have all it needs to be a proper STL iterator.
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
RawSquareFreeIdeal & operator=(const RawSquareFreeIdeal &ideal)
Resets this object to be a copy of ideal.
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:92
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
void swap(size_t a, size_t b)
const_iterator operator+(ptrdiff_t i) const
size_t getWordsPerTerm() const
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
ptrdiff_t operator-(const iterator &it) const
ptrdiff_t operator-(const const_iterator &it) const
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
bool operator==(const const_iterator &it) const
const_iterator end() const
const_iterator & operator=(const const_iterator &it)
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...
bool isMinimallyGenerated() const
Returns true if no generator divides another.
const Word * back() const
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
size_t getVarCount() const
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
iterator(Word *term, size_t wordsPerTerm)
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...
void colon(const Word *by)
bool operator!=(const const_iterator &it) const
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var...
RawSquareFreeIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.