Frobby 0.9.5
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
49class Term {
50 public:
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);
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
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 Exponent operator[](unsigned long long offset) const {
103 ASSERT(offset < _varCount);
104 return _exponents[offset];
105 }
106
107 Exponent& operator[](int offset) {
108 ASSERT(0 <= offset);
109 ASSERT((unsigned int)offset < _varCount);
110 return _exponents[offset];
111 }
112 Exponent& operator[](unsigned int offset) {
113 ASSERT(offset < _varCount);
114 return _exponents[offset];
115 }
116 Exponent& operator[](unsigned long offset) {
117 ASSERT(offset < _varCount);
118 return _exponents[offset];
119 }
120 Exponent& operator[](unsigned long long offset) {
121 ASSERT(offset < _varCount);
122 return _exponents[offset];
123 }
124
125 bool operator==(const Term& term) const {
126 ASSERT(_varCount == term._varCount);
127 return (*this) == term._exponents;
128 }
129 bool operator==(const Exponent* term) const;
130 bool operator!=(const Term& term) const {return !(*this == term);}
131 bool operator!=(const Exponent* term) const {return !(*this == term);}
132
133 Term& operator=(const Term& term) {
134 if (_varCount != term._varCount) {
135 Exponent* newBuffer = allocate(term._varCount);
137 _exponents = newBuffer;
138 _varCount = term._varCount;
139 }
140
141 ASSERT(_varCount == term._varCount);
142 return (*this) = term._exponents;
143 }
144
145 Term& operator=(const Exponent* exponents) {
146 IF_DEBUG(if (_varCount > 0)) // avoid copy asserting on null pointer
147 copy(exponents, exponents + _varCount, _exponents);
148 return *this;
149 }
150
152 inline static bool divides(const Exponent* a, const Exponent* b, size_t varCount) {
153 ASSERT(a != 0 || varCount == 0);
154 ASSERT(b != 0 || varCount == 0);
155 for (size_t var = 0; var < varCount; ++var)
156 if (a[var] > b[var])
157 return false;
158 return true;
159 }
160
161 bool divides(const Term& term) const {
162 ASSERT(_varCount == term._varCount);
163 return divides(_exponents, term._exponents, _varCount);
164 }
165
166 bool divides(const Exponent* term) const {
167 return divides(_exponents, term, _varCount);
168 }
169
172 inline static bool dominates(const Exponent* a, const Exponent* b,
173 size_t varCount) {
174 ASSERT(a != 0 || varCount == 0);
175 ASSERT(b != 0 || varCount == 0);
176 for (size_t var = 0; var < varCount; ++var)
177 if (a[var] < b[var])
178 return false;
179 return true;
180 }
181
182 bool dominates(const Term& term) const {
183 ASSERT(_varCount == term._varCount);
185 }
186
187 bool dominates(const Exponent* term) const {
188 return dominates(_exponents, term, _varCount);
189 }
190
196 inline static bool strictlyDivides(const Exponent* a, const Exponent* b,
197 size_t varCount) {
198 ASSERT(a != 0 || varCount == 0);
199 ASSERT(b != 0 || varCount == 0);
200 bool bIsIdentity = true;
201 for (size_t var = 0; var < varCount; ++var) {
202 if (a[var] >= b[var] && a[var] != 0)
203 return false;
204 if (b[var] != 0)
205 bIsIdentity = false;
206 }
207
208 return !bIsIdentity;
209 }
210
211 bool strictlyDivides(const Term& term) const {
212 ASSERT(_varCount == term._varCount);
214 }
215
216 bool strictlyDivides(const Exponent* term) const {
217 return strictlyDivides(_exponents, term, _varCount);
218 }
219
221 inline static void lcm(Exponent* res,
222 const Exponent* a, const Exponent* b,
223 size_t varCount) {
224 ASSERT(res != 0 || varCount == 0);
225 ASSERT(a != 0 || varCount == 0);
226 ASSERT(b != 0 || varCount == 0);
227 for (size_t var = 0; var < varCount; ++var) {
228 if (a[var] > b[var])
229 res[var] = a[var];
230 else
231 res[var] = b[var];
232 }
233 }
234
235 void lcm(const Term& a, const Term& b, int position) {
238 lcm(_exponents + position,
239 a._exponents + position,
240 b._exponents + position,
241 _varCount - position);
242 }
243
244 void lcm(const Term& a, const Term& b) {
248 }
249
250 void lcm(const Exponent* a, const Exponent* b) {
251 lcm(_exponents, a, b, _varCount);
252 }
253
255 inline static void gcd(Exponent* res,
256 const Exponent* a, const Exponent* b,
257 size_t varCount) {
258 ASSERT(res != 0 || varCount == 0);
259 ASSERT(a != 0 || varCount == 0);
260 ASSERT(b != 0 || varCount == 0);
261 for (size_t var = 0; var < varCount; ++var) {
262 if (a[var] < b[var])
263 res[var] = a[var];
264 else
265 res[var] = b[var];
266 }
267 }
268
269 void gcd(const Term& a, const Term& b) {
273 }
274
275 void gcd(const Exponent* a, const Exponent* b) {
276 gcd(_exponents, a, b, _varCount);
277 }
278
280 inline static void product(Exponent* res,
281 const Exponent* a, const Exponent* b,
282 size_t varCount) {
283 ASSERT(res != 0 || varCount == 0);
284 ASSERT(a != 0 || varCount == 0);
285 ASSERT(b != 0 || varCount == 0);
286 for (size_t var = 0; var < varCount; ++var)
287 res[var] = a[var] + b[var];
288 }
289
291 void product(const Term& a, const Term& b) {
295 }
296
297 void product(const Exponent* a, const Exponent* b) {
299 }
300
304 inline static void setToIdentity(Exponent* res, size_t varCount) {
305 ASSERT(res != 0 || varCount == 0);
306 for (size_t var = 0; var < varCount; ++var)
307 res[var] = 0;
308 }
309
313
316 inline static bool isIdentity(const Exponent* a, size_t varCount) {
317 ASSERT(a != 0 || varCount == 0);
318 for (size_t var = 0; var < varCount; ++var)
319 if (a[var] != 0)
320 return false;
321 return true;
322 }
323
324 bool isIdentity() const {
326 }
327
331 inline static bool isSquareFree(const Exponent* a, size_t varCount) {
332 ASSERT(a != 0 || varCount == 0);
333 for (size_t var = 0; var < varCount; ++var)
334 if (a[var] >= 2)
335 return false;
336 return true;
337 }
338
339 bool isSquareFree() const {
341 }
342
346 inline static size_t getFirstNonZeroExponent(const Exponent* a, size_t varCount) {
347 ASSERT(a != 0 || varCount == 0);
348 for (size_t var = 0; var < varCount; ++var)
349 if (a[var] != 0)
350 return var;
351 return varCount;
352 }
353
357
361 inline static size_t getMiddleNonZeroExponent(const Exponent* a, size_t varCount) {
362 ASSERT(a != 0 || varCount == 0);
363 size_t nonZeroOffset = getSizeOfSupport(a, varCount) / 2;
364 for (size_t var = 0; var < varCount; ++var) {
365 if (a[var] != 0) {
366 if (nonZeroOffset == 0)
367 return var;
368 --nonZeroOffset;
369 }
370 }
371
372 ASSERT(isIdentity(a, varCount));
373 return varCount;
374 }
375
379
381 inline static size_t getFirstMaxExponent(const Exponent* a, size_t varCount) {
382 ASSERT(a != 0 || varCount == 0);
383 size_t max = 0;
384 for (size_t var = 1; var < varCount; ++var)
385 if (a[max] < a[var])
386 max = var;
387 return max;
388 }
389
390 size_t getFirstMaxExponent() const {
392 }
393
394 size_t getMaxExponent() const {
395 ASSERT(_varCount > 0);
397 }
398
402 inline static size_t getSizeOfSupport(const Exponent* a, size_t varCount) {
403 ASSERT(a != 0 || varCount == 0);
404 size_t size = 0;
405 for (size_t var = 0; var < varCount; ++var)
406 if (a[var] != 0)
407 ++size;
408 return size;
409 }
410
411 size_t getSizeOfSupport() const {
413 }
414
416 static bool sharesNonZeroExponent(const Exponent* a, const Exponent* b,
417 size_t varCount) {
418 for (size_t var = 0; var < varCount; ++var)
419 if (a[var] != 0 && a[var] == b[var])
420 return true;
421 return false;
422 }
423
424 inline static size_t getHashCode(const Exponent* a, size_t varCount) {
425 size_t hashCode = varCount;
426 for (size_t var = 0; var < varCount; ++var)
427 hashCode = 31 * hashCode + a[var];
428 return hashCode;
429 }
430
431 size_t getHashCode() const {
433 }
434
435 bool sharesNonZeroExponent(const Exponent* a) const {
437 }
438
439 bool sharesNonZeroExponent(const Term& a) const {
441 }
442
446 inline static bool hasSameSupport(const Exponent* a, const Exponent* b,
447 size_t varCount) {
448 ASSERT(a != 0 || varCount == 0);
449 ASSERT(b != 0 || varCount == 0);
450 for (size_t var = 0; var < varCount; ++var) {
451 if (a[var] == 0) {
452 if (b[var] != 0)
453 return false;
454 } else {
455 ASSERT(a[var] != 0);
456 if (b[var] == 0)
457 return false;
458 }
459 }
460 return true;
461 }
462
463 bool hasSameSupport(const Term& a) const {
465 return hasSameSupport(a._exponents);
466 }
467
468 bool hasSameSupport(const Exponent* a) const {
470 }
471
476 inline static void colon(Exponent* res,
477 const Exponent* a, const Exponent* b,
478 size_t varCount) {
479 ASSERT(res != 0 || varCount == 0);
480 ASSERT(a != 0 || varCount == 0);
481 ASSERT(b != 0 || varCount == 0);
482 for (size_t var = 0; var < varCount; ++var) {
483 if (a[var] > b[var])
484 res[var] = a[var] - b[var];
485 else
486 res[var] = 0;
487 }
488 }
489
490 void colon(const Term& a, const Term& b) {
494 }
495
496 void colon(const Exponent* a, const Exponent* b) {
497 colon(_exponents, a, b, _varCount);
498 }
499
505 inline static void encodedDual(Exponent* res,
506 const Exponent* dualOf, const Exponent* point,
507 size_t varCount) {
508 ASSERT(res != 0 || varCount == 0);
509 ASSERT(dualOf != 0 || varCount == 0);
510 ASSERT(point != 0 || varCount == 0);
511
512 for (size_t var = 0; var < varCount; ++var) {
513 ASSERT(dualOf[var] <= point[var]);
514 if (dualOf[var] != 0)
515 res[var] = point[var] - dualOf[var] + 1;
516 else
517 res[var] = 0;
518 }
519 }
520
521 void encodedDual(const Term& dualOf, const Term& point) {
522 ASSERT(_varCount == dualOf._varCount);
523 ASSERT(_varCount == point._varCount);
524 encodedDual(dualOf._exponents, point._exponents);
525 }
526
527 void encodedDual(const Exponent* dualOf, const Exponent* point) {
528 encodedDual(_exponents, dualOf, point, _varCount);
529 }
530
532 inline static void decrement(Exponent* a, size_t varCount) {
533 ASSERT(a != 0 || varCount == 0);
534 for (size_t var = 0; var < varCount; ++var)
535 if (a[var] > 0)
536 a[var] -= 1;
537 }
538
542
543 void swap(Term& term) {
544 std::swap(_varCount, term._varCount);
545
546 Exponent* tmp = _exponents;
547 _exponents = term._exponents;
548 term._exponents = tmp;
549 }
550
551 void reset(size_t newVarCount) {
552 if (newVarCount != _varCount) {
553 Exponent* newBuffer = allocate(newVarCount);
554
556 _varCount = newVarCount;
557 _exponents = newBuffer;
558 }
560 }
561
562 void clear() {
564 _exponents = 0;
565 _varCount = 0;
566 }
567
569 static void print(FILE* file, const Exponent* e, size_t varCount);
570
572 static void print(ostream& out, const Exponent* e, size_t varCount);
573
574 void print(FILE* file) const {
575 print(file, _exponents, _varCount);
576 }
577
578 void print(ostream& out) const {
580 }
581
582
583 private:
584 static Exponent* allocate(size_t size);
585 static void deallocate(Exponent* p, size_t size);
586
587 void initialize(const Exponent* exponents, size_t varCount) {
588 if (varCount > 0) {
589 ASSERT(exponents != 0);
590 _exponents = allocate(varCount);
591 copy(exponents, exponents + varCount, _exponents);
592 } else
593 _exponents = 0;
594 _varCount = varCount;
595 }
596
598 size_t _varCount;
599};
600
601inline void swap(Term& a, Term& b) { a.swap(b); }
602
603
604inline ostream& operator<<(ostream& out, const Term& term) {
605 term.print(out);
606 return out;
607}
608
609#endif
void swap(Term &a, Term &b)
Definition Term.h:601
ostream & operator<<(ostream &out, const Term &term)
Definition Term.h:604
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
void lcm(const Exponent *a, const Exponent *b)
Definition Term.h:250
bool divides(const Term &term) const
Definition Term.h:161
void product(const Term &a, const Term &b)
Set this object equal to the product of a and b.
Definition Term.h:291
static size_t getHashCode(const Exponent *a, size_t varCount)
Definition Term.h:424
Exponent & operator[](int offset)
Definition Term.h:107
bool dominates(const Term &term) const
Definition Term.h:182
Exponent & operator[](unsigned long offset)
Definition Term.h:116
size_t getMiddleNonZeroExponent() const
Definition Term.h:376
void reset(size_t newVarCount)
Definition Term.h:551
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition Term.h:532
bool strictlyDivides(const Exponent *term) const
Definition Term.h:216
size_t _varCount
Definition Term.h:598
bool divides(const Exponent *term) const
Definition Term.h:166
static bool hasSameSupport(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether for every variable .
Definition Term.h:446
Term & operator=(const Term &term)
Definition Term.h:133
Exponent operator[](unsigned int offset) const
Definition Term.h:94
static size_t getSizeOfSupport(const Exponent *a, size_t varCount)
Returns the number of variables such that divides .
Definition Term.h:402
Exponent * begin()
Definition Term.h:79
bool operator==(const Term &term) const
Definition Term.h:125
static Exponent * allocate(size_t size)
Definition Term.cpp:86
Exponent & operator[](unsigned long long offset)
Definition Term.h:120
Exponent * end()
Definition Term.h:82
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:505
Exponent & operator[](unsigned int offset)
Definition Term.h:112
bool isIdentity() const
Definition Term.h:324
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:280
void print(ostream &out) const
Definition Term.h:578
static void deallocate(Exponent *p, size_t size)
Definition Term.cpp:98
size_t getHashCode() const
Definition Term.h:431
void product(const Exponent *a, const Exponent *b)
Definition Term.h:297
Term()
Definition Term.h:51
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:172
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
Definition Term.h:196
Exponent operator[](unsigned long offset) const
Definition Term.h:98
void colon(const Exponent *a, const Exponent *b)
Definition Term.h:496
void setToIdentity()
Definition Term.h:310
bool isSquareFree() const
Definition Term.h:339
const Exponent * begin() const
Definition Term.h:80
bool sharesNonZeroExponent(const Term &a) const
Definition Term.h:439
const Exponent * end() const
Definition Term.h:83
void gcd(const Term &a, const Term &b)
Definition Term.h:269
size_t getVarCount() const
Definition Term.h:85
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
void encodedDual(const Term &dualOf, const Term &point)
Definition Term.h:521
bool strictlyDivides(const Term &term) const
Definition Term.h:211
bool dominates(const Exponent *term) const
Definition Term.h:187
static void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
Definition Term.h:476
void swap(Term &term)
Definition Term.h:543
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:361
void lcm(const Term &a, const Term &b, int position)
Definition Term.h:235
static size_t getFirstNonZeroExponent(const Exponent *a, size_t varCount)
Returns least var such that a[var] is non-zero.
Definition Term.h:346
bool hasSameSupport(const Exponent *a) const
Definition Term.h:468
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:316
bool hasSameSupport(const Term &a) const
Definition Term.h:463
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:255
Term(const Exponent *exponents, size_t varCount)
Definition Term.h:53
Exponent operator[](int offset) const
Definition Term.h:89
void clear()
Definition Term.h:562
size_t getFirstMaxExponent() const
Definition Term.h:390
void initialize(const Exponent *exponents, size_t varCount)
Definition Term.h:587
bool sharesNonZeroExponent(const Exponent *a) const
Definition Term.h:435
size_t getFirstNonZeroExponent() const
Definition Term.h:354
void print(FILE *file) const
Definition Term.h:574
size_t getSizeOfSupport() const
Definition Term.h:411
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition Term.h:152
Term(const Term &term)
Definition Term.h:52
void colon(const Term &a, const Term &b)
Definition Term.h:490
void decrement()
Definition Term.h:539
static bool isSquareFree(const Exponent *a, size_t varCount)
Returns whether a is square free, i.e. for each where .
Definition Term.h:331
bool operator!=(const Term &term) const
Definition Term.h:130
Exponent operator[](unsigned long long offset) const
Definition Term.h:102
void lcm(const Term &a, const Term &b)
Definition Term.h:244
bool operator!=(const Exponent *term) const
Definition Term.h:131
Term(size_t varCount)
This object is initialized to the identity, i.e. the exponent vector is the zero vector.
Definition Term.h:60
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:381
size_t getMaxExponent() const
Definition Term.h:394
void gcd(const Exponent *a, const Exponent *b)
Definition Term.h:275
Term & operator=(const Exponent *exponents)
Definition Term.h:145
Exponent * _exponents
Definition Term.h:597
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
Definition Term.h:416
void encodedDual(const Exponent *dualOf, const Exponent *point)
Definition Term.h:527
~Term()
Definition Term.h:74
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:221
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:304
unsigned int Exponent
Definition stdinc.h:89
#define IF_DEBUG(X)
Definition stdinc.h:85
#define ASSERT(X)
Definition stdinc.h:86