Frobby  0.9.0
Term.h
Go to the documentation of this file.
1 /* Frobby: Software for monomial ideal computations.
2  Copyright (C) 2007 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 #ifndef TERM_GUARD
18 #define TERM_GUARD
19 
20 #include <ostream>
21 
49 class Term {
50  public:
51  Term(): _exponents(0), _varCount(0) {}
52  Term(const Term& term) {initialize(term._exponents, term._varCount);}
53  Term(const Exponent* exponents, size_t varCount) {
54  initialize(exponents, varCount);
55  }
56 
60  Term(size_t varCount):
61  _varCount(varCount) {
62  if (varCount > 0) {
63  _exponents = allocate(varCount);
64  setToIdentity();
65  } else
66  _exponents = 0;
67  }
68 
72  Term(const string& str);
73 
75 
76  operator Exponent*() {return _exponents;}
77  operator const Exponent*() const {return _exponents;}
78 
79  Exponent* begin() {return _exponents;}
80  const Exponent* begin() const {return _exponents;}
81 
83  const Exponent* end() const {return _exponents + _varCount;}
84 
85  size_t getVarCount() const {return _varCount;}
86 
87  // We need all these versions to make everything work out on
88  // different platforms.
89  Exponent operator[](int offset) const {
90  ASSERT(0 <= offset);
91  ASSERT((unsigned int)offset < _varCount);
92  return _exponents[offset];
93  }
94  Exponent operator[](unsigned int offset) const {
95  ASSERT(offset < _varCount);
96  return _exponents[offset];
97  }
98  Exponent operator[](unsigned long offset) const {
99  ASSERT(offset < _varCount);
100  return _exponents[offset];
101  }
102 
103  Exponent& operator[](int offset) {
104  ASSERT(0 <= offset);
105  ASSERT((unsigned int)offset < _varCount);
106  return _exponents[offset];
107  }
108  Exponent& operator[](unsigned int offset) {
109  ASSERT(offset < _varCount);
110  return _exponents[offset];
111  }
112  Exponent& operator[](unsigned long offset) {
113  ASSERT(offset < _varCount);
114  return _exponents[offset];
115  }
116 
117  bool operator==(const Term& term) const {
118  ASSERT(_varCount == term._varCount);
119  return (*this) == term._exponents;
120  }
121  bool operator==(const Exponent* term) const;
122  bool operator!=(const Term& term) const {return !(*this == term);}
123  bool operator!=(const Exponent* term) const {return !(*this == term);}
124 
125  Term& operator=(const Term& term) {
126  if (_varCount != term._varCount) {
127  Exponent* newBuffer = allocate(term._varCount);
129  _exponents = newBuffer;
130  _varCount = term._varCount;
131  }
132 
133  ASSERT(_varCount == term._varCount);
134  return (*this) = term._exponents;
135  }
136 
137  Term& operator=(const Exponent* exponents) {
138  IF_DEBUG(if (_varCount > 0)) // avoid copy asserting on null pointer
139  copy(exponents, exponents + _varCount, _exponents);
140  return *this;
141  }
142 
144  inline static bool divides(const Exponent* a, const Exponent* b, size_t varCount) {
145  ASSERT(a != 0 || varCount == 0);
146  ASSERT(b != 0 || varCount == 0);
147  for (size_t var = 0; var < varCount; ++var)
148  if (a[var] > b[var])
149  return false;
150  return true;
151  }
152 
153  bool divides(const Term& term) const {
154  ASSERT(_varCount == term._varCount);
155  return divides(_exponents, term._exponents, _varCount);
156  }
157 
158  bool divides(const Exponent* term) const {
159  return divides(_exponents, term, _varCount);
160  }
161 
164  inline static bool dominates(const Exponent* a, const Exponent* b,
165  size_t varCount) {
166  ASSERT(a != 0 || varCount == 0);
167  ASSERT(b != 0 || varCount == 0);
168  for (size_t var = 0; var < varCount; ++var)
169  if (a[var] < b[var])
170  return false;
171  return true;
172  }
173 
174  bool dominates(const Term& term) const {
175  ASSERT(_varCount == term._varCount);
176  return dominates(_exponents, term._exponents, _varCount);
177  }
178 
179  bool dominates(const Exponent* term) const {
180  return dominates(_exponents, term, _varCount);
181  }
182 
188  inline static bool strictlyDivides(const Exponent* a, const Exponent* b,
189  size_t varCount) {
190  ASSERT(a != 0 || varCount == 0);
191  ASSERT(b != 0 || varCount == 0);
192  bool bIsIdentity = true;
193  for (size_t var = 0; var < varCount; ++var) {
194  if (a[var] >= b[var] && a[var] != 0)
195  return false;
196  if (b[var] != 0)
197  bIsIdentity = false;
198  }
199 
200  return !bIsIdentity;
201  }
202 
203  bool strictlyDivides(const Term& term) const {
204  ASSERT(_varCount == term._varCount);
206  }
207 
208  bool strictlyDivides(const Exponent* term) const {
209  return strictlyDivides(_exponents, term, _varCount);
210  }
211 
213  inline static void lcm(Exponent* res,
214  const Exponent* a, const Exponent* b,
215  size_t varCount) {
216  ASSERT(res != 0 || varCount == 0);
217  ASSERT(a != 0 || varCount == 0);
218  ASSERT(b != 0 || varCount == 0);
219  for (size_t var = 0; var < varCount; ++var) {
220  if (a[var] > b[var])
221  res[var] = a[var];
222  else
223  res[var] = b[var];
224  }
225  }
226 
227  void lcm(const Term& a, const Term& b, int position) {
228  ASSERT(_varCount == a._varCount);
229  ASSERT(_varCount == b._varCount);
230  lcm(_exponents + position,
231  a._exponents + position,
232  b._exponents + position,
233  _varCount - position);
234  }
235 
236  void lcm(const Term& a, const Term& b) {
237  ASSERT(_varCount == a._varCount);
238  ASSERT(_varCount == b._varCount);
240  }
241 
242  void lcm(const Exponent* a, const Exponent* b) {
243  lcm(_exponents, a, b, _varCount);
244  }
245 
247  inline static void gcd(Exponent* res,
248  const Exponent* a, const Exponent* b,
249  size_t varCount) {
250  ASSERT(res != 0 || varCount == 0);
251  ASSERT(a != 0 || varCount == 0);
252  ASSERT(b != 0 || varCount == 0);
253  for (size_t var = 0; var < varCount; ++var) {
254  if (a[var] < b[var])
255  res[var] = a[var];
256  else
257  res[var] = b[var];
258  }
259  }
260 
261  void gcd(const Term& a, const Term& b) {
262  ASSERT(_varCount == a._varCount);
263  ASSERT(_varCount == b._varCount);
264  gcd(a._exponents, b._exponents);
265  }
266 
267  void gcd(const Exponent* a, const Exponent* b) {
268  gcd(_exponents, a, b, _varCount);
269  }
270 
272  inline static void product(Exponent* res,
273  const Exponent* a, const Exponent* b,
274  size_t varCount) {
275  ASSERT(res != 0 || varCount == 0);
276  ASSERT(a != 0 || varCount == 0);
277  ASSERT(b != 0 || varCount == 0);
278  for (size_t var = 0; var < varCount; ++var)
279  res[var] = a[var] + b[var];
280  }
281 
283  void product(const Term& a, const Term& b) {
284  ASSERT(_varCount == a._varCount);
285  ASSERT(_varCount == b._varCount);
287  }
288 
289  void product(const Exponent* a, const Exponent* b) {
290  product(_exponents, a, b, _varCount);
291  }
292 
296  inline static void setToIdentity(Exponent* res, size_t varCount) {
297  ASSERT(res != 0 || varCount == 0);
298  for (size_t var = 0; var < varCount; ++var)
299  res[var] = 0;
300  }
301 
302  void setToIdentity() {
304  }
305 
308  inline static bool isIdentity(const Exponent* a, size_t varCount) {
309  ASSERT(a != 0 || varCount == 0);
310  for (size_t var = 0; var < varCount; ++var)
311  if (a[var] != 0)
312  return false;
313  return true;
314  }
315 
316  bool isIdentity() const {
318  }
319 
323  inline static bool isSquareFree(const Exponent* a, size_t varCount) {
324  ASSERT(a != 0 || varCount == 0);
325  for (size_t var = 0; var < varCount; ++var)
326  if (a[var] >= 2)
327  return false;
328  return true;
329  }
330 
331  bool isSquareFree() const {
333  }
334 
338  inline static size_t getFirstNonZeroExponent(const Exponent* a, size_t varCount) {
339  ASSERT(a != 0 || varCount == 0);
340  for (size_t var = 0; var < varCount; ++var)
341  if (a[var] != 0)
342  return var;
343  return varCount;
344  }
345 
346  size_t getFirstNonZeroExponent() const {
348  }
349 
353  inline static size_t getMiddleNonZeroExponent(const Exponent* a, size_t varCount) {
354  ASSERT(a != 0 || varCount == 0);
355  size_t nonZeroOffset = getSizeOfSupport(a, varCount) / 2;
356  for (size_t var = 0; var < varCount; ++var) {
357  if (a[var] != 0) {
358  if (nonZeroOffset == 0)
359  return var;
360  --nonZeroOffset;
361  }
362  }
363 
364  ASSERT(isIdentity(a, varCount));
365  return varCount;
366  }
367 
368  size_t getMiddleNonZeroExponent() const {
370  }
371 
373  inline static size_t getFirstMaxExponent(const Exponent* a, size_t varCount) {
374  ASSERT(a != 0 || varCount == 0);
375  size_t max = 0;
376  for (size_t var = 1; var < varCount; ++var)
377  if (a[max] < a[var])
378  max = var;
379  return max;
380  }
381 
382  size_t getFirstMaxExponent() const {
384  }
385 
386  size_t getMaxExponent() const {
387  ASSERT(_varCount > 0);
389  }
390 
394  inline static size_t getSizeOfSupport(const Exponent* a, size_t varCount) {
395  ASSERT(a != 0 || varCount == 0);
396  size_t size = 0;
397  for (size_t var = 0; var < varCount; ++var)
398  if (a[var] != 0)
399  ++size;
400  return size;
401  }
402 
403  size_t getSizeOfSupport() const {
405  }
406 
408  static bool sharesNonZeroExponent(const Exponent* a, const Exponent* b,
409  size_t varCount) {
410  for (size_t var = 0; var < varCount; ++var)
411  if (a[var] != 0 && a[var] == b[var])
412  return true;
413  return false;
414  }
415 
416  inline static size_t getHashCode(const Exponent* a, size_t varCount) {
417  size_t hashCode = varCount;
418  for (size_t var = 0; var < varCount; ++var)
419  hashCode = 31 * hashCode + a[var];
420  return hashCode;
421  }
422 
423  size_t getHashCode() const {
425  }
426 
427  bool sharesNonZeroExponent(const Exponent* a) const {
429  }
430 
431  bool sharesNonZeroExponent(const Term& a) const {
433  }
434 
438  inline static bool hasSameSupport(const Exponent* a, const Exponent* b,
439  size_t varCount) {
440  ASSERT(a != 0 || varCount == 0);
441  ASSERT(b != 0 || varCount == 0);
442  for (size_t var = 0; var < varCount; ++var) {
443  if (a[var] == 0) {
444  if (b[var] != 0)
445  return false;
446  } else {
447  ASSERT(a[var] != 0);
448  if (b[var] == 0)
449  return false;
450  }
451  }
452  return true;
453  }
454 
455  bool hasSameSupport(const Term& a) const {
456  ASSERT(_varCount == a._varCount);
457  return hasSameSupport(a._exponents);
458  }
459 
460  bool hasSameSupport(const Exponent* a) const {
461  return hasSameSupport(_exponents, a, _varCount);
462  }
463 
468  inline static void colon(Exponent* res,
469  const Exponent* a, const Exponent* b,
470  size_t varCount) {
471  ASSERT(res != 0 || varCount == 0);
472  ASSERT(a != 0 || varCount == 0);
473  ASSERT(b != 0 || varCount == 0);
474  for (size_t var = 0; var < varCount; ++var) {
475  if (a[var] > b[var])
476  res[var] = a[var] - b[var];
477  else
478  res[var] = 0;
479  }
480  }
481 
482  void colon(const Term& a, const Term& b) {
483  ASSERT(_varCount == a._varCount);
484  ASSERT(_varCount == b._varCount);
486  }
487 
488  void colon(const Exponent* a, const Exponent* b) {
489  colon(_exponents, a, b, _varCount);
490  }
491 
497  inline static void encodedDual(Exponent* res,
498  const Exponent* dualOf, const Exponent* point,
499  size_t varCount) {
500  ASSERT(res != 0 || varCount == 0);
501  ASSERT(dualOf != 0 || varCount == 0);
502  ASSERT(point != 0 || varCount == 0);
503 
504  for (size_t var = 0; var < varCount; ++var) {
505  ASSERT(dualOf[var] <= point[var]);
506  if (dualOf[var] != 0)
507  res[var] = point[var] - dualOf[var] + 1;
508  else
509  res[var] = 0;
510  }
511  }
512 
513  void encodedDual(const Term& dualOf, const Term& point) {
514  ASSERT(_varCount == dualOf._varCount);
515  ASSERT(_varCount == point._varCount);
516  encodedDual(dualOf._exponents, point._exponents);
517  }
518 
519  void encodedDual(const Exponent* dualOf, const Exponent* point) {
520  encodedDual(_exponents, dualOf, point, _varCount);
521  }
522 
524  inline static void decrement(Exponent* a, size_t varCount) {
525  ASSERT(a != 0 || varCount == 0);
526  for (size_t var = 0; var < varCount; ++var)
527  if (a[var] > 0)
528  a[var] -= 1;
529  }
530 
531  void decrement() {
533  }
534 
535  void swap(Term& term) {
537 
538  Exponent* tmp = _exponents;
539  _exponents = term._exponents;
540  term._exponents = tmp;
541  }
542 
543  void reset(size_t newVarCount) {
544  if (newVarCount != _varCount) {
545  Exponent* newBuffer = allocate(newVarCount);
546 
548  _varCount = newVarCount;
549  _exponents = newBuffer;
550  }
551  setToIdentity();
552  }
553 
554  void clear() {
556  _exponents = 0;
557  _varCount = 0;
558  }
559 
561  static void print(FILE* file, const Exponent* e, size_t varCount);
562 
564  static void print(ostream& out, const Exponent* e, size_t varCount);
565 
566  void print(FILE* file) const {
567  print(file, _exponents, _varCount);
568  }
569 
570  void print(ostream& out) const {
571  print(out, _exponents, _varCount);
572  }
573 
574 
575  private:
576  static Exponent* allocate(size_t size);
577  static void deallocate(Exponent* p, size_t size);
578 
579  void initialize(const Exponent* exponents, size_t varCount) {
580  if (varCount > 0) {
581  ASSERT(exponents != 0);
582  _exponents = allocate(varCount);
583  copy(exponents, exponents + varCount, _exponents);
584  } else
585  _exponents = 0;
586  _varCount = varCount;
587  }
588 
590  size_t _varCount;
591 };
592 
593 namespace std {
594  // This allows STL to swap terms more efficiently.
595  template<> inline void swap<Term>(Term& a, Term& b) {
596  a.swap(b);
597  }
598 }
599 
600 inline ostream& operator<<(ostream& out, const Term& term) {
601  term.print(out);
602  return out;
603 }
604 
605 #endif
size_t getMiddleNonZeroExponent() const
Definition: Term.h:368
static Exponent * allocate(size_t size)
Definition: Term.cpp:86
bool isSquareFree() const
Definition: Term.h:331
void swap< Term >(Term &a, Term &b)
Definition: Term.h:595
ostream & operator<<(ostream &out, const Term &term)
Definition: Term.h:600
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition: Term.h:308
Exponent operator[](int offset) const
Definition: Term.h:89
void print(ostream &out) const
Definition: Term.h:570
Exponent * begin()
Definition: Term.h:79
static void encodedDual(Exponent *res, const Exponent *dualOf, const Exponent *point, size_t varCount)
The parameter dualOf is interpreted to encode an irreducible ideal, and the dual of that reflected in...
Definition: Term.h:497
bool sharesNonZeroExponent(const Term &a) const
Definition: Term.h:431
const Exponent * end() const
Definition: Term.h:83
void encodedDual(const Term &dualOf, const Term &point)
Definition: Term.h:513
bool operator!=(const Term &term) const
Definition: Term.h:122
void gcd(const Term &a, const Term &b)
Definition: Term.h:261
bool hasSameSupport(const Exponent *a) const
Definition: Term.h:460
size_t getFirstMaxExponent() const
Definition: Term.h:382
bool operator!=(const Exponent *term) const
Definition: Term.h:123
#define ASSERT(X)
Definition: stdinc.h:85
void reset(size_t newVarCount)
Definition: Term.h:543
Term & operator=(const Exponent *exponents)
Definition: Term.h:137
Term(const Term &term)
Definition: Term.h:52
bool sharesNonZeroExponent(const Exponent *a) const
Definition: Term.h:427
void clear()
Definition: Term.h:554
void encodedDual(const Exponent *dualOf, const Exponent *point)
Definition: Term.h:519
static size_t getFirstNonZeroExponent(const Exponent *a, size_t varCount)
Returns least var such that a[var] is non-zero.
Definition: Term.h:338
Exponent & operator[](unsigned int offset)
Definition: Term.h:108
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition: Term.h:524
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
Definition: Term.h:188
~Term()
Definition: Term.h:74
size_t _varCount
Definition: Term.h:590
Term(size_t varCount)
This object is initialized to the identity, i.e. the exponent vector is the zero vector.
Definition: Term.h:60
#define IF_DEBUG(X)
Definition: stdinc.h:84
bool strictlyDivides(const Exponent *term) const
Definition: Term.h:208
size_t getVarCount() const
Definition: Term.h:85
void initialize(const Exponent *exponents, size_t varCount)
Definition: Term.h:579
void lcm(const Exponent *a, const Exponent *b)
Definition: Term.h:242
bool operator==(const Term &term) const
Definition: Term.h:117
bool dominates(const Term &term) const
Definition: Term.h:174
void product(const Term &a, const Term &b)
Set this object equal to the product of a and b.
Definition: Term.h:283
Term & operator=(const Term &term)
Definition: Term.h:125
Term()
Definition: Term.h:51
static void product(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the product of a and b.
Definition: Term.h:272
static size_t getHashCode(const Exponent *a, size_t varCount)
Definition: Term.h:416
bool hasSameSupport(const Term &a) const
Definition: Term.h:455
void gcd(const Exponent *a, const Exponent *b)
Definition: Term.h:267
const Exponent * begin() const
Definition: Term.h:80
bool isIdentity() const
Definition: Term.h:316
void lcm(const Term &a, const Term &b, int position)
Definition: Term.h:227
static void deallocate(Exponent *p, size_t size)
Definition: Term.cpp:98
void print(FILE *file) const
Definition: Term.h:566
bool divides(const Exponent *term) const
Definition: Term.h:158
size_t getSizeOfSupport() const
Definition: Term.h:403
void decrement()
Definition: Term.h:531
static size_t getSizeOfSupport(const Exponent *a, size_t varCount)
Returns the number of variables such that divides .
Definition: Term.h:394
Term(const Exponent *exponents, size_t varCount)
Definition: Term.h:53
void colon(const Exponent *a, const Exponent *b)
Definition: Term.h:488
bool dominates(const Exponent *term) const
Definition: Term.h:179
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition: Term.h:144
void colon(const Term &a, const Term &b)
Definition: Term.h:482
void swap(Term &term)
Definition: Term.h:535
bool divides(const Term &term) const
Definition: Term.h:153
Exponent * end()
Definition: Term.h:82
Exponent * _exponents
Definition: Term.h:589
void lcm(const Term &a, const Term &b)
Definition: Term.h:236
size_t getHashCode() const
Definition: Term.h:423
static size_t getFirstMaxExponent(const Exponent *a, size_t varCount)
Returns a var such that a[var] >= a[i] for all i.
Definition: Term.h:373
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
Definition: Term.cpp:110
static size_t getMiddleNonZeroExponent(const Exponent *a, size_t varCount)
Returns a median element of the set of var's such that a[var] is non-zero.
Definition: Term.h:353
static bool dominates(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a dominates b, i.e. whether b divides a.
Definition: Term.h:164
static void gcd(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the greatest common divisor of a and b.
Definition: Term.h:247
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition: Term.h:296
Exponent & operator[](unsigned long offset)
Definition: Term.h:112
size_t getFirstNonZeroExponent() const
Definition: Term.h:346
Exponent & operator[](int offset)
Definition: Term.h:103
void setToIdentity()
Definition: Term.h:302
static void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
Definition: Term.h:468
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
Definition: Term.h:408
Exponent operator[](unsigned int offset) const
Definition: Term.h:94
static void lcm(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the least commom multiple of a and b.
Definition: Term.h:213
size_t getMaxExponent() const
Definition: Term.h:386
static bool hasSameSupport(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether for every variable .
Definition: Term.h:438
unsigned int Exponent
Definition: stdinc.h:88
bool strictlyDivides(const Term &term) const
Definition: Term.h:203
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
void product(const Exponent *a, const Exponent *b)
Definition: Term.h:289
static bool isSquareFree(const Exponent *a, size_t varCount)
Returns whether a is square free, i.e. for each where .
Definition: Term.h:323
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
Exponent operator[](unsigned long offset) const
Definition: Term.h:98