Frobby 0.9.5
Ideal.cpp
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#include "stdinc.h"
18#include "Ideal.h"
19
20#include "TermPredicate.h"
21#include "Term.h"
22#include "Minimizer.h"
23
24#include <algorithm>
25#include <functional>
26#include <sstream>
27
29}
30
31Ideal::Ideal(size_t varCount):
32 _varCount(varCount),
33 _allocator(varCount) {
34}
35
36Ideal::Ideal(const Term& term):
37 _varCount(term.getVarCount()),
38 _allocator(term.getVarCount()) {
39 insert(term);
40}
41
42Ideal::Ideal(const Ideal& ideal):
43 _varCount(ideal.getVarCount()),
44 _allocator(ideal.getVarCount()) {
45 insert(ideal);
46}
47
48bool Ideal::isIncomparable(const Exponent* term) const {
49 const_iterator stop = _terms.end();
50 for (const_iterator it = _terms.begin(); it != stop; ++it)
51 if (Term::dominates(term, *it, _varCount) ||
52 Term::divides(term, *it, _varCount))
53 return false;
54 return true;
55}
56
57bool Ideal::contains(const Exponent* term) const {
58 const_iterator stop = _terms.end();
59 for (const_iterator it = _terms.begin(); it != stop; ++it)
60 if (Term::dominates(term, *it, _varCount))
61 return true;
62 return false;
63}
64
66 const_iterator stop = _terms.end();
67 for (const_iterator it = _terms.begin(); it != stop; ++it)
69 return true;
70 return false;
71}
72
73bool Ideal::strictlyContains(const Exponent* term) const {
74 const_iterator stop = _terms.end();
75 for (const_iterator it = _terms.begin(); it != stop; ++it)
76 if (Term::strictlyDivides(*it, term, _varCount))
77 return true;
78 return false;
79}
80
82 Minimizer minimizer(_varCount);
83 return minimizer.isMinimallyGenerated(_terms.begin(), _terms.end());
84}
85
86bool Ideal::isZeroIdeal() const {
87 return _terms.empty();
88}
89
91 const_iterator stop = _terms.end();
92 for (const_iterator it = _terms.begin(); it != stop; ++it)
93 if (Term::getSizeOfSupport(*it, _varCount) != 1)
94 return false;
95 return true;
96}
97
98bool Ideal::isSquareFree() const {
99 const_iterator stop = _terms.end();
100 for (const_iterator it = _terms.begin(); it != stop; ++it)
101 if (!Term::isSquareFree(*it, _varCount))
102 return false;
103 return true;
104}
105
107 for (size_t var = 0; var < _varCount; ++var) {
108 singleDegreeSort(var);
109
110 Exponent lastExponent = 0;
111 const_iterator stop = _terms.end();
112 for (const_iterator it = _terms.begin(); it != stop; ++it) {
113 if (lastExponent != 0 && lastExponent == (*it)[var])
114 return false;
115 lastExponent = (*it)[var];
116 }
117 }
118 return true;
119}
120
123
124 const_iterator stop = _terms.end();
125 for (const_iterator itA = _terms.begin(); itA != stop; ++itA) {
126 for (const_iterator itB = itA + 1; itB != stop; ++itB) {
127 if (!Term::sharesNonZeroExponent(*itA, *itB, _varCount))
128 continue;
129
130 lcm.lcm(*itA, *itB);
131 for (const_iterator itC = _terms.begin(); itC != stop; ++itC)
133 goto foundStrictDivisor;
134 return false;
135
136 foundStrictDivisor:;
137 }
138 }
139 return true;
140}
141
143 for (size_t var = 0; var < getVarCount(); ++var) {
144 bool seen = false;
145 for (const_iterator it = _terms.begin(); it != _terms.end(); ++it) {
146 if ((*it)[var] > 0) {
147 if (seen)
148 return false;
149 else
150 seen = true;
151 }
152 }
153 }
154 return true;
155}
156
159 const_iterator stop = _terms.end();
160 for (const_iterator it = _terms.begin(); it != stop; ++it)
161 Term::lcm(lcm, lcm, *it, _varCount);
162}
163
165 if (_terms.empty()) {
167 return;
168 }
169
170 copy(_terms[0], _terms[0] + _varCount, gcd);
171 const_iterator stop = _terms.end();
172 const_iterator it = _terms.begin();
173 for (++it; it != stop; ++it)
174 Term::gcd(gcd, gcd, *it, _varCount);
175}
176
178 bool first = true;
179
180 const_iterator stop = _terms.end();
181 const_iterator it = _terms.begin();
182 for (; it != stop; ++it) {
183 Exponent* m = *it;
184 if (m[var] == exp) {
185 if (first) {
186 first = false;
187 copy(m, m + _varCount, gcd);
188 } else
190 }
191 }
192
193 if (first)
195}
196
198 bool first = true;
199
200 const_iterator stop = _terms.end();
201 const_iterator it = _terms.begin();
202 for (; it != stop; ++it) {
203 Exponent* m = *it;
204 if (Term::divides(divisor, m, _varCount)) {
205 if (first) {
206 first = false;
207 copy(m, m + _varCount, gcd);
208 } else
210 }
211 }
212
213 if (first)
215}
216
219
220 const_iterator stop = _terms.end();
221 for (const_iterator it = _terms.begin(); it != stop; ++it)
222 for (size_t var = 0; var < _varCount; ++var)
223 if (least[var] == 0 || ((*it)[var] < least[var] && (*it)[var] > 0))
224 least[var] = (*it)[var];
225}
226
229 const_iterator stop = _terms.end();
230 for (const_iterator it = begin(); it != stop; ++it)
231 for (size_t var = 0; var < _varCount; ++var)
232 if ((*it)[var] > 0)
233 counts[var] += 1;
234}
235
237getTypicalExponent(size_t& typicalVar, Exponent& typicalExponent) {
238 size_t maxCount = 0;
239 typicalVar = 0;
240 typicalExponent = 0;
241
242 for (size_t var = 0; var < _varCount; ++var) {
243 singleDegreeSort(var);
244
245 Exponent lastExponent = 0;
246 size_t count = 0;
247 const_iterator stop = _terms.end();
248 for (const_iterator it = _terms.begin(); it != stop; ++it) {
249 Exponent exponent = (*it)[var];
250 if (exponent == 0)
251 continue;
252
253 if (lastExponent == exponent)
254 ++count;
255 else
256 count = 1;
257
258 if (count > maxCount) {
259 maxCount = count;
260 typicalVar = var;
261 typicalExponent = exponent;
262 }
263
264 lastExponent = exponent;
265 }
266 }
267
268 return maxCount;
269}
270
272(size_t& mostNGVar, Exponent& mostNGExponent) {
274
275 size_t maxCount = 0;
276 mostNGVar = 0;
277 mostNGExponent = 0;
278
279 for (size_t var = 0; var < _varCount; ++var) {
280 singleDegreeSort(var);
281
282 const_iterator blockBegin = _terms.begin();
283 const_iterator stop = _terms.end();
284 while (blockBegin != stop) {
285 Exponent blockExponent = (*blockBegin)[var];
286 const_iterator blockEnd = blockBegin;
287 do {
288 ++blockEnd;
289 } while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
290
291 // At this point the range [blockBegin, blockEnd) contains every
292 // generator that raises var to blockExponent. Each pair of
293 // these is potentially non-generic, and we count the number
294 // that actually are non-generic.
295
296 size_t span = blockEnd - blockBegin;
297 if (blockExponent == 0 || (span * (span + 1)) / 2 <= maxCount) {
298 blockBegin = blockEnd;
299 continue;
300 }
301
302 size_t nonGenericCount = 0;
303 for (; blockBegin != blockEnd; ++blockBegin) {
304 const_iterator it = blockBegin;
305 for (++it; it != blockEnd; ++it) {
306 lcm.lcm(*blockBegin, *it);
307 if (!strictlyContains(lcm)) {
308 // The pair (*blockBegin, *it) is non-generic.
309 ++nonGenericCount;
310 }
311 }
312 }
313
314 if (nonGenericCount > maxCount) {
315 maxCount = nonGenericCount;
316 mostNGVar = var;
317 mostNGExponent = blockExponent;
318 }
319 }
320 }
321
322 return maxCount;
323}
324
326(size_t& typicalVar, Exponent& typicalExponent) {
328
329 size_t maxCount = 0;
330 typicalVar = 0;
331 typicalExponent = 0;
332
333 for (size_t var = 0; var < _varCount; ++var) {
334 singleDegreeSort(var);
335
336 const_iterator blockBegin = _terms.begin();
337 const_iterator stop = _terms.end();
338 while (blockBegin != stop) {
339 Exponent blockExponent = (*blockBegin)[var];
340 const_iterator blockEnd = blockBegin;
341 do {
342 ++blockEnd;
343 } while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
344
345 // At this point the range [blockBegin, blockEnd) contains every
346 // generator that raises var to blockExponent. Each pair of
347 // these is potentially non-generic, and we count the number
348 // that actually are non-generic.
349
350 size_t count = blockEnd - blockBegin;
351 if (blockExponent == 0 || count <= maxCount) {
352 blockBegin = blockEnd;
353 continue;
354 }
355
356 for (; blockBegin != blockEnd; ++blockBegin) {
357 const_iterator it = blockBegin;
358 for (++it; it != blockEnd; ++it) {
359 lcm.lcm(*blockBegin, *it);
360 if (!strictlyContains(lcm)) {
361 // The pair (*blockBegin, *it) is non-generic.
362 ASSERT(maxCount < count);
363 maxCount = count;
364 typicalVar = var;
365 typicalExponent = blockExponent;
366 blockBegin = blockEnd;
367 goto blockDone;
368 }
369 }
370 }
371 blockDone:;
372 }
373 }
374
375 return maxCount;
376}
377
379(size_t& ngVar, Exponent& ngExponent) {
381
382 ngVar = 0;
383 ngExponent = 0;
384
385 for (size_t var = 0; var < _varCount; ++var) {
386 singleDegreeSort(var);
387
388 const_iterator blockBegin = _terms.begin();
389 const_iterator stop = _terms.end();
390 while (blockBegin != stop) {
391 Exponent blockExponent = (*blockBegin)[var];
392 const_iterator blockEnd = blockBegin;
393 do {
394 ++blockEnd;
395 } while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
396
397 // At this point the range [blockBegin, blockEnd) contains every
398 // generator that raises var to blockExponent. Each pair of
399 // these is potentially non-generic.
400
401 if (blockExponent == 0) {
402 blockBegin = blockEnd;
403 continue;
404 }
405
406 for (; blockBegin != blockEnd; ++blockBegin) {
407 const_iterator it = blockBegin;
408 for (++it; it != blockEnd; ++it) {
409 lcm.lcm(*blockBegin, *it);
410 if (!strictlyContains(lcm)) {
411 // The pair (*blockBegin, *it) is non-generic.
412 ngVar = var;
413 ngExponent = blockExponent;
414 return true;
415 }
416 }
417 }
418 }
419 }
420
421 return false;
422}
423
424bool Ideal::operator==(const Ideal& ideal) const {
425 if (getVarCount() != ideal.getVarCount())
426 return false;
427 if (getGeneratorCount() != ideal.getGeneratorCount())
428 return false;
429
430 const_iterator stop = _terms.end();
431 const_iterator it = begin();
432 const_iterator it2 = ideal.begin();
433 for (; it != stop; ++it, ++it2)
434 if (!equals(*it, *it2, getVarCount()))
435 return false;
436
437 return true;
438}
439
440void Ideal::print(FILE* file) const {
441 ostringstream out;
442 print(out);
443 fputs(out.str().c_str(), file);
444}
445
446void Ideal::print(ostream& out) const {
447 out << "//------------ Ideal:\n";
448 for (const_iterator it = _terms.begin(); it != _terms.end(); ++it) {
449 Term::print(out, *it, _varCount);
450 out << '\n';
451 }
452 out << "------------\\\\\n";
453}
454
455void Ideal::insert(const Exponent* exponents) {
456 Exponent* term = _allocator.allocate();
457 IF_DEBUG(if (_varCount > 0)) // avoid copy asserting on null pointer
458 copy(exponents, exponents + _varCount, term);
459
460 // push_back could throw bad_alloc, but the allocator is already
461 // keeping track of the allocated memory, so there is not a memory
462 // leak.
463 _terms.push_back(term);
464}
465
466void Ideal::insert(const Ideal& ideal) {
467 _terms.reserve(_terms.size() + ideal._terms.size());
468 Ideal::const_iterator stop = ideal.end();
469 for (Ideal::const_iterator it = ideal.begin(); it != stop; ++it)
470 insert(*it);
471}
472
473void Ideal::insert(size_t var, Exponent e) {
474 Exponent* term = _allocator.allocate();
475 fill_n(term, _varCount, 0);
476 term[var] = e;
477
478 // push_back could throw bad_alloc, but the allocator is already
479 // keeping track of the allocated memory, so there is not a memory
480 // leak.
481 _terms.push_back(term);
482}
483
486 if (contains(term))
487 return;
488
489 removeMultiples(term);
490 insert(term);
492}
493
496 removeMultiples(var, e);
497 insert(var, e);
499}
500
502 if (_terms.empty())
503 return;
504
505 Minimizer minimizer(_varCount);
506 _terms.erase(minimizer.minimize(_terms.begin(), _terms.end()), _terms.end());
508}
509
511 std::sort(_terms.begin(), _terms.end(), ReverseLexComparator(_varCount));
512}
513
515 std::sort(_terms.begin(), _terms.end(), LexComparator(_varCount));
516}
517
518void Ideal::singleDegreeSort(size_t var) {
519 ASSERT(var < _varCount);
520 std::sort(_terms.begin(),
521 _terms.end(),
523}
524
525void Ideal::product(const Exponent* by) {
526 iterator stop = _terms.end();
527 for (iterator it = _terms.begin(); it != stop; ++it)
528 Term::product(*it, *it, by, _varCount);
529}
530
531void Ideal::colon(const Exponent* by) {
532 iterator stop = _terms.end();
533 for (iterator it = _terms.begin(); it != stop; ++it)
534 Term::colon(*it, *it, by, _varCount);
535}
536
537void Ideal::colon(size_t var, Exponent e) {
538 iterator stop = _terms.end();
539 for (iterator it = _terms.begin(); it != stop; ++it) {
540 Exponent& ite = (*it)[var];
541 if (ite != 0) {
542 if (ite > e)
543 ite -= e;
544 else
545 ite = 0;
546 }
547 }
548}
549
552
553 Minimizer minimizer(_varCount);
554 pair<iterator, bool> pair =
555 minimizer.colonReminimize(_terms.begin(), _terms.end(), by);
556
557 _terms.erase(pair.first, _terms.end());
558
560 return pair.second;
561}
562
563bool Ideal::colonReminimize(size_t var, Exponent e) {
565
566 Minimizer minimizer(_varCount);
567 pair<iterator, bool> pair =
568 minimizer.colonReminimize(_terms.begin(), _terms.end(), var, e);
569
570 _terms.erase(pair.first, _terms.end());
571
573 return pair.second;
574}
575
577 ASSERT(begin() <= it);
578 ASSERT(it < end());
579 std::swap(const_cast<Exponent*&>(*it), *(_terms.end() - 1));
580 _terms.pop_back();
581}
582
583
585 iterator newEnd = _terms.begin();
586 iterator stop = _terms.end();
587 for (iterator it = _terms.begin(); it != stop; ++it) {
588 if (!Term::divides(term, *it, _varCount)) {
589 *newEnd = *it;
590 ++newEnd;
591 }
592 }
593 _terms.erase(newEnd, stop);
594}
595
596void Ideal::removeMultiples(size_t var, Exponent e) {
597 iterator newEnd = _terms.begin();
598 iterator stop = _terms.end();
599 for (iterator it = _terms.begin(); it != stop; ++it) {
600 if ((*it)[var] < e) {
601 *newEnd = *it;
602 ++newEnd;
603 }
604 }
605 _terms.erase(newEnd, stop);
606}
607
608void Ideal::insertNonMultiples(const Exponent* term, const Ideal& ideal) {
609 const_iterator stop = ideal.end();
610 for (const_iterator it = ideal.begin(); it != stop; ++it)
611 if (!Term::divides(term, *it, _varCount))
612 insert(*it);
613}
614
615void Ideal::insertNonMultiples(size_t var, Exponent e, const Ideal& ideal) {
616 const_iterator stop = ideal.end();
617 for (const_iterator it = ideal.begin(); it != stop; ++it)
618 if ((*it)[var] < e)
619 insert(*it);
620}
621
623 iterator newEnd = _terms.begin();
624 iterator stop = _terms.end();
625 for (iterator it = _terms.begin(); it != stop; ++it) {
626 if (!Term::strictlyDivides(term, *it, _varCount)) {
627 *newEnd = *it;
628 ++newEnd;
629 }
630 }
631 _terms.erase(newEnd, stop);
632}
633
635 std::sort(_terms.begin(), _terms.end(), LexComparator(_varCount));
636 iterator newEnd =
637 unique(_terms.begin(), _terms.end(), EqualsPredicate(_varCount));
638 _terms.erase(newEnd, _terms.end());
639}
640
642 _terms.clear();
644}
645
646void Ideal::clearAndSetVarCount(size_t varCount) {
647 _varCount = varCount;
648 _terms.clear();
649 _allocator.reset(varCount);
650}
651
652void Ideal::mapExponentsToZeroNoMinimize(const Term& zeroExponents) {
653 iterator stop = _terms.end();
654 for (iterator it = _terms.begin(); it != stop; ++it)
655 for (size_t var = 0; var < _varCount; ++var)
656 if ((*it)[var] == zeroExponents[var])
657 (*it)[var] = 0;
658}
659
661 iterator stop = _terms.end();
662 for (iterator it = _terms.begin(); it != stop; ++it)
663 for (size_t var = 0; var < _varCount; ++var)
664 if ((*it)[var] > 1)
665 (*it)[var] = 1;
666}
667
669 const_iterator stop = _terms.end();
670 for (const_iterator it = _terms.begin(); it != stop; ++it)
671 if ((*it)[var] > 0)
672 return it;
673 return stop;
674}
675
678 insert(ideal);
679
680 return *this;
681}
682
683void Ideal::swap(Ideal& ideal) {
685 _terms.swap(ideal._terms);
687}
688
689
690
691
692// ---------------------***************
693
694
695
696
697
698
699
700const int ExponentsPerChunk = 1024;
701const int MinTermsPerChunk = 2;
702
704public:
706 if (_chunks.empty())
707 return new Exponent[ExponentsPerChunk];
708
709 Exponent* chunk = _chunks.back();
710 _chunks.pop_back();
711 return chunk;
712 }
713
714 void deallocate(Exponent* chunk) {
715 // deallocate can be called from a destructor, so no exceptions
716 // can be allowed to escape from it.
717 try {
718 _chunks.push_back(chunk);
719 } catch (const bad_alloc&) {
720 delete[] chunk;
721 }
722 }
723
724 void clear() {
725 for (size_t i = 0; i < _chunks.size(); ++i)
726 delete[] _chunks[i];
727 _chunks.clear();
728 }
729
731 clear();
732 }
733
734private:
735 vector<Exponent*> _chunks;
737
739 _varCount(varCount),
740 _chunkIterator(0),
741 _chunkEnd(0) {
742 if (_varCount == 0)
743 _varCount = 1;
744}
745
747 reset(0);
748}
749
751 if (_chunkIterator + _varCount > _chunkEnd) {
752 if (useSingleChunking()) {
753 Exponent* term = new Exponent[_varCount];
754 try {
755 _chunks.push_back(term);
756 } catch (...) {
757 delete[] term;
758 throw;
759 }
760 return term;
761 }
762
763 _chunkIterator = globalChunkPool.allocate();
764 _chunkEnd = _chunkIterator + ExponentsPerChunk;
765
766 try {
767 _chunks.push_back(_chunkIterator);
768 } catch (...) {
769 globalChunkPool.deallocate(_chunkIterator);
770 throw;
771 }
772 }
773
774 Exponent* term = _chunkIterator;
775 _chunkIterator += _varCount;
776 ASSERT(_chunkIterator <= _chunkEnd);
777
778 return term;
779}
780
781void Ideal::ExponentAllocator::reset(size_t newVarCount) {
782 _varCount = newVarCount;
783
784 if (useSingleChunking()) {
785 for (size_t i = 0; i < _chunks.size(); ++i)
786 delete[] _chunks[i];
787 _chunks.clear();
788 } else {
789 _chunkIterator = 0;
790 _chunkEnd = 0;
791
792 for (size_t i = 0; i < _chunks.size(); ++i)
793 globalChunkPool.deallocate(_chunks[i]);
794 _chunks.clear();
795 }
796}
797
799 std::swap(_varCount, allocator._varCount);
800 std::swap(_chunkIterator, allocator._chunkIterator);
801 std::swap(_chunkEnd, allocator._chunkEnd);
802
803 _chunks.swap(allocator._chunks);
804}
805
808}
809
812}
const int ExponentsPerChunk
Definition: Ideal.cpp:700
class ChunkPool globalChunkPool
const int MinTermsPerChunk
Definition: Ideal.cpp:701
~ChunkPool()
Definition: Ideal.cpp:730
void clear()
Definition: Ideal.cpp:724
void deallocate(Exponent *chunk)
Definition: Ideal.cpp:714
vector< Exponent * > _chunks
Definition: Ideal.cpp:735
Exponent * allocate()
Definition: Ideal.cpp:705
A predicate that compares for equality.
Exponent * _chunkIterator
Definition: Ideal.h:309
void reset(size_t newVarCount)
Definition: Ideal.cpp:781
void swap(ExponentAllocator &allocator)
Definition: Ideal.cpp:798
Exponent * _chunkEnd
Definition: Ideal.h:310
vector< Exponent * > _chunks
Definition: Ideal.h:312
bool useSingleChunking() const
Definition: Ideal.cpp:806
Exponent * allocate()
Definition: Ideal.cpp:750
ExponentAllocator(size_t varCount)
Definition: Ideal.cpp:738
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void getGcdOfMultiplesOf(Exponent *gcd, const Exponent *divisor)
Sets gcd to the greatest common divisor of those generators that are divisible by divisor.
Definition: Ideal.cpp:197
void removeStrictMultiples(const Exponent *term)
Definition: Ideal.cpp:622
void removeDuplicates()
Definition: Ideal.cpp:634
void singleDegreeSort(size_t var)
Definition: Ideal.cpp:518
void minimize()
Definition: Ideal.cpp:501
bool isSquareFree() const
Definition: Ideal.cpp:98
void product(const Exponent *term)
Definition: Ideal.cpp:525
bool isZeroIdeal() const
Definition: Ideal.cpp:86
void remove(const_iterator it)
Definition: Ideal.cpp:576
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
Definition: Ideal.cpp:164
void insertNonMultiples(const Exponent *term, const Ideal &ideal)
Definition: Ideal.cpp:608
size_t getGeneratorCount() const
Definition: Ideal.h:57
ExponentAllocator _allocator
Definition: Ideal.h:317
size_t getMostNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the most non-generic degree.
Definition: Ideal.cpp:272
~Ideal()
Definition: Ideal.cpp:28
const_iterator getMultiple(size_t var) const
Definition: Ideal.cpp:668
bool containsIdentity() const
Definition: Ideal.cpp:65
void colon(const Exponent *by)
Definition: Ideal.cpp:531
void clearAndSetVarCount(size_t varCount)
Definition: Ideal.cpp:646
void getLcm(Exponent *lcm) const
Sets lcm to the least common multiple of all generators.
Definition: Ideal.cpp:157
void takeRadicalNoMinimize()
Replaces all generators with their support and does not remove any non-minimal generators this may pr...
Definition: Ideal.cpp:660
bool getNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is some non-generic degree.
Definition: Ideal.cpp:379
bool isIncomparable(const Exponent *term) const
Definition: Ideal.cpp:48
Cont::const_iterator const_iterator
Definition: Ideal.h:43
static void clearStaticCache()
Ideal caches memory allocated with new internally and reuses it to avoid calling new all the time.
Definition: Ideal.cpp:810
void sortReverseLex()
Definition: Ideal.cpp:510
vector< Exponent * > _terms
Definition: Ideal.h:316
void clear()
Definition: Ideal.cpp:641
void mapExponentsToZeroNoMinimize(const Term &zeroExponents)
Replaces the exponents from zeroExponents with zero and does not remove any non-minimal generators th...
Definition: Ideal.cpp:652
bool contains(const Exponent *term) const
Definition: Ideal.cpp:57
void sortLex()
Definition: Ideal.cpp:514
size_t getTypicalExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-zero exponent.
Definition: Ideal.cpp:237
void insert(const Exponent *term)
Definition: Ideal.cpp:455
bool strictlyContains(const Exponent *term) const
Definition: Ideal.cpp:73
void insertReminimize(const Exponent *term)
Definition: Ideal.cpp:484
void getLeastExponents(Exponent *least) const
Definition: Ideal.cpp:217
bool disjointSupport() const
Returns true if all pairs of generators have disjoint support.
Definition: Ideal.cpp:142
const_iterator end() const
Definition: Ideal.h:49
Ideal & operator=(const Ideal &ideal)
Definition: Ideal.cpp:676
void print(FILE *file) const
Definition: Ideal.cpp:440
void swap(Ideal &ideal)
Definition: Ideal.cpp:683
const_iterator begin() const
Definition: Ideal.h:48
void getSupportCounts(Exponent *counts) const
counts[var] will be the number of generators divisible by var.
Definition: Ideal.cpp:227
Ideal(size_t varCount=0)
Initialize this object to the zero ideal in varCount variables.
Definition: Ideal.cpp:31
bool isIrreducible() const
Definition: Ideal.cpp:90
void removeMultiples(const Exponent *term)
Definition: Ideal.cpp:584
bool isWeaklyGeneric() const
Definition: Ideal.cpp:121
size_t getTypicalNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-generic degree.
Definition: Ideal.cpp:326
bool isStronglyGeneric()
Definition: Ideal.cpp:106
Cont::iterator iterator
Definition: Ideal.h:44
bool colonReminimize(const Exponent *colon)
Definition: Ideal.cpp:550
bool isMinimallyGenerated() const
Definition: Ideal.cpp:81
size_t _varCount
Definition: Ideal.h:315
void getGcdAtExponent(Exponent *gcd, size_t var, Exponent exp)
Sets gcd to the greatest common divisor of those generators that raise the variable var to the power ...
Definition: Ideal.cpp:177
bool operator==(const Ideal &ideal) const
Rereturns true if *this equals ideal.
Definition: Ideal.cpp:424
size_t getVarCount() const
Definition: Ideal.h:56
A predicate that sorts terms according to lexicographic order.
Definition: TermPredicate.h:97
bool isMinimallyGenerated(const_iterator begin, const_iterator end)
Definition: Minimizer.cpp:308
pair< iterator, bool > colonReminimize(iterator begin, iterator end, const Exponent *colon)
Definition: Minimizer.cpp:257
iterator minimize(iterator begin, iterator end) const
Definition: Minimizer.cpp:239
A predicate that sorts according to reverse lexicographic order.
A predicate that sorts terms in weakly ascending order according to degree of the specified variable.
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
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
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
void setToIdentity()
Definition: Term.h:310
bool isSquareFree() const
Definition: Term.h:339
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 void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
Definition: Term.h:476
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
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
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
Definition: Term.h:416
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
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
unsigned int Exponent
Definition: stdinc.h:89
#define IF_DEBUG(X)
Definition: stdinc.h:85
#define ASSERT(X)
Definition: stdinc.h:86