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 {
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
BigIdeal
Definition: BigIdeal.h:27
RawSquareFreeIdeal::operator!=
bool operator!=(const RawSquareFreeIdeal &ideal) const
Definition: RawSquareFreeIdeal.h:207
RawSquareFreeIdeal::iterator::iterator
iterator(Word *term, size_t wordsPerTerm)
Definition: RawSquareFreeIdeal.h:261
RawSquareFreeIdeal::const_iterator::operator+
const_iterator operator+(ptrdiff_t i) const
Definition: RawSquareFreeIdeal.h:242
RawSquareFreeIdeal::_memory
Word _memory[1]
Definition: RawSquareFreeIdeal.h:322
RawSquareFreeIdeal::_varCount
size_t _varCount
Definition: RawSquareFreeIdeal.h:318
RawSquareFreeIdeal::getGeneratorCount
size_t getGeneratorCount() const
Definition: RawSquareFreeIdeal.h:124
RawSquareFreeIdeal::const_iterator
const_iterator doesn't have all it needs to be a proper STL iterator.
Definition: RawSquareFreeIdeal.h:219
RawSquareFreeIdeal::insertNonMultiples
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
Definition: RawSquareFreeIdeal.cpp:490
RawSquareFreeIdeal::insert
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
Definition: RawSquareFreeIdeal.cpp:196
RawSquareFreeIdeal::back
Word * back()
Definition: RawSquareFreeIdeal.h:211
RawSquareFreeIdeal::iterator::_wordsPerTerm
const size_t _wordsPerTerm
Definition: RawSquareFreeIdeal.h:297
RawSquareFreeIdeal::getGeneratorUnsafe
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...
Definition: RawSquareFreeIdeal.h:360
RawSquareFreeIdeal::isValid
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
Definition: RawSquareFreeIdeal.cpp:774
RawSquareFreeIdeal::const_iterator::_wordsPerTerm
const size_t _wordsPerTerm
Definition: RawSquareFreeIdeal.h:254
RawSquareFreeIdeal::begin
const_iterator begin() const
Definition: RawSquareFreeIdeal.h:302
RawSquareFreeIdeal::getVarCount
size_t getVarCount() const
Definition: RawSquareFreeIdeal.h:125
RawSquareFreeIdeal::_genCount
size_t _genCount
Definition: RawSquareFreeIdeal.h:320
RawSquareFreeIdeal::_memoryEnd
Word * _memoryEnd
Definition: RawSquareFreeIdeal.h:321
RawSquareFreeIdeal::insertIdentity
void insertIdentity()
Definition: RawSquareFreeIdeal.cpp:658
RawSquareFreeIdeal::const_iterator::const_iterator
const_iterator(const Word *term, size_t wordsPerTerm)
Definition: RawSquareFreeIdeal.h:221
RawSquareFreeIdeal::const_iterator::operator!=
bool operator!=(const const_iterator &it) const
Definition: RawSquareFreeIdeal.h:233
RawSquareFreeIdeal::getExclusiveVarGenerator
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
Definition: RawSquareFreeIdeal.cpp:521
RawSquareFreeIdeal::_wordsPerTerm
size_t _wordsPerTerm
Definition: RawSquareFreeIdeal.h:319
RawSquareFreeIdeal::getLcmOfNonMultiples
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
Definition: RawSquareFreeIdeal.cpp:304
RawSquareFreeIdeal::isMinimallyGenerated
bool isMinimallyGenerated() const
Returns true if no generator divides another.
Definition: RawSquareFreeIdeal.cpp:579
RawSquareFreeIdeal::iterator::operator++
iterator operator++()
Definition: RawSquareFreeIdeal.h:270
RawSquareFreeIdeal::iterator
iterator doesn't have all it needs to be a proper STL iterator.
Definition: RawSquareFreeIdeal.h:259
RawSquareFreeIdeal::setToTransposeOf
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
Definition: RawSquareFreeIdeal.cpp:140
RawSquareFreeIdeal::construct
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
Definition: RawSquareFreeIdeal.cpp:86
RawSquareFreeIdeal::iterator::operator!=
bool operator!=(const iterator &it) const
Definition: RawSquareFreeIdeal.h:277
RawSquareFreeIdeal::const_iterator::operator*
const Word * operator*() const
Definition: RawSquareFreeIdeal.h:225
RawSquareFreeIdeal::iterator::operator-
ptrdiff_t operator-(const iterator &it) const
Definition: RawSquareFreeIdeal.h:282
RawSquareFreeIdeal::iterator::operator+
iterator operator+(ptrdiff_t i) const
Definition: RawSquareFreeIdeal.h:286
RawSquareFreeIdeal::compact
void compact(const Word *remove)
Removes the variables that divide remove.
Definition: RawSquareFreeIdeal.cpp:264
RawSquareFreeIdeal::const_iterator::operator=
const_iterator & operator=(const const_iterator &it)
Definition: RawSquareFreeIdeal.h:246
RawSquareFreeIdeal::const_iterator::operator++
const_iterator operator++()
Definition: RawSquareFreeIdeal.h:226
RawSquareFreeIdeal::iterator::_term
Word * _term
Definition: RawSquareFreeIdeal.h:296
RawSquareFreeIdeal::minimize
void minimize()
Definition: RawSquareFreeIdeal.cpp:242
RawSquareFreeIdeal::hasFullSupport
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
Definition: RawSquareFreeIdeal.cpp:545
RawSquareFreeIdeal::const_iterator::_term
const Word * _term
Definition: RawSquareFreeIdeal.h:253
RawSquareFreeIdeal::removeGenerator
void removeGenerator(size_t index)
Removes the generator at index.
Definition: RawSquareFreeIdeal.cpp:480
RawSquareFreeIdeal::colonReminimize
void colonReminimize(const Word *colon)
Performs a colon and minimize.
Definition: RawSquareFreeIdeal.cpp:675
newRawSquareFreeIdeal
RawSquareFreeIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
Definition: RawSquareFreeIdeal.cpp:797
RawSquareFreeIdeal::swap01Exponents
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
Definition: RawSquareFreeIdeal.cpp:651
RawSquareFreeIdeal::back
const Word * back() const
Definition: RawSquareFreeIdeal.h:212
RawSquareFreeIdeal::const_iterator::operator==
bool operator==(const const_iterator &it) const
Definition: RawSquareFreeIdeal.h:229
RawSquareFreeIdeal::begin
iterator begin()
Definition: RawSquareFreeIdeal.h:300
RawSquareFreeIdeal
A bit packed square free ideal placed in a pre-allocated buffer.
Definition: RawSquareFreeIdeal.h:37
RawSquareFreeIdeal::iterator::operator--
iterator operator--()
Definition: RawSquareFreeIdeal.h:271
RawSquareFreeIdeal::RawSquareFreeIdeal
RawSquareFreeIdeal()
RawSquareFreeIdeal::operator==
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
Definition: RawSquareFreeIdeal.cpp:597
newRawSquareFreeIdealParse
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
Definition: RawSquareFreeIdeal.cpp:819
RawSquareFreeIdeal::getMultiple
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
Definition: RawSquareFreeIdeal.cpp:393
RawSquareFreeIdeal::getGenerator
Word * getGenerator(size_t index)
Returns the generator at index.
Definition: RawSquareFreeIdeal.h:350
Word
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:92
RawSquareFreeIdeal::getVarDividesCounts
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
Definition: RawSquareFreeIdeal.cpp:366
RawSquareFreeIdeal::getMinSupportGen
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
Definition: RawSquareFreeIdeal.cpp:435
RawSquareFreeIdeal::sortLexAscending
void sortLexAscending()
Sorts the generators in ascending lex order.
Definition: RawSquareFreeIdeal.cpp:623
RawSquareFreeIdeal::const_iterator::operator-
ptrdiff_t operator-(const const_iterator &it) const
Definition: RawSquareFreeIdeal.h:238
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:251
operator<<
ostream & operator<<(ostream &out, const RawSquareFreeIdeal &ideal)
Definition: RawSquareFreeIdeal.h:345
RawSquareFreeIdeal::colon
void colon(const Word *by)
Definition: RawSquareFreeIdeal.cpp:249
RawSquareFreeIdeal::swap
void swap(size_t a, size_t b)
Definition: RawSquareFreeIdeal.cpp:590
RawSquareFreeIdeal::const_iterator::operator--
const_iterator operator--()
Definition: RawSquareFreeIdeal.h:227
Ideal
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
RawSquareFreeIdeal::end
const_iterator end() const
Definition: RawSquareFreeIdeal.h:307
RawSquareFreeIdeal::print
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
Definition: RawSquareFreeIdeal.cpp:179
RawSquareFreeIdeal::getNotRelativelyPrime
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
Definition: RawSquareFreeIdeal.cpp:513
RawSquareFreeIdeal::operator=
RawSquareFreeIdeal & operator=(const RawSquareFreeIdeal &ideal)
Resets this object to be a copy of ideal.
Definition: RawSquareFreeIdeal.h:55
RawSquareFreeIdeal::transpose
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
Definition: RawSquareFreeIdeal.cpp:168
deleteRawSquareFreeIdeal
void deleteRawSquareFreeIdeal(RawSquareFreeIdeal *ideal)
Deallocates memory returned by newRawSquareFreeIdeal().
RawSquareFreeIdeal::getWordsPerTerm
size_t getWordsPerTerm() const
Definition: RawSquareFreeIdeal.h:126
RawSquareFreeIdeal::end
iterator end()
Definition: RawSquareFreeIdeal.h:305
RawSquareFreeIdeal::iterator::operator==
bool operator==(const iterator &it) const
Definition: RawSquareFreeIdeal.h:273
ASSERT
#define ASSERT(X)
Definition: stdinc.h:85
RawSquareFreeIdeal::getBytesOfMemoryFor
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.
Definition: RawSquareFreeIdeal.cpp:110
RawSquareFreeIdeal::getNonMultiple
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...
Definition: RawSquareFreeIdeal.cpp:404
RawSquareFreeIdeal::getGcdOfMultiples
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var.
Definition: RawSquareFreeIdeal.cpp:455
RawSquareFreeIdeal::iterator::operator*
Word * operator*() const
Definition: RawSquareFreeIdeal.h:269
RawSquareFreeIdeal::getLcm
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
Definition: RawSquareFreeIdeal.cpp:765
SquareFreeTermOps::gcd
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:276
RawSquareFreeIdeal::iterator::operator=
iterator & operator=(const iterator &it)
Definition: RawSquareFreeIdeal.h:289
RawSquareFreeIdeal::getMaxSupportGen
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
Definition: RawSquareFreeIdeal.cpp:415