29 typedef vector<Exponent*>::iterator TermIterator;
32 TermIterator
simpleMinimize(TermIterator begin, TermIterator end,
size_t varCount) {
38 TermIterator newEnd = begin;
40 TermIterator dominator = newEnd;
41 for (; dominator != end; ++dominator) {
43 for (TermIterator divisor = begin; divisor != newEnd; ++divisor) {
64 TermIterator last = begin;
65 TermIterator it = begin;
67 for (; it != end; ++it) {
68 if ((*it)[1] < (*last)[1]) {
82 TreeNode(iterator begin, iterator end,
size_t varCount):
110 for (
size_t var = 0; var <
_varCount; ++var)
111 if (lcm[var] > lcm[maxVar])
113 if (lcm[maxVar] == 0) {
123 iterator right =
_end - 1;
124 while (left != right) {
125 while ((*left)[
_var] <=
_pivot && left != right)
127 while ((*right)[
_var] >
_pivot && left != right)
135 iterator middle = right;
136 while ((*middle)[maxVar] >
_pivot)
187 size_t oldSize = terms.size();
189 for (
size_t i = oldSize; i < terms.size();) {
191 swap(terms[i], terms.back());
205 fprintf(out,
"NODE (pivot=%lu^%lu, varCount = %lu\n",
209 fputs(
"-lessOrEqual: ", out);
211 fputs(
"-greater: ", out);
218 fprintf(out,
"NODE (_varCount = %lu terms:\n", (
unsigned long)
_varCount);
219 for (iterator it =
_begin; it !=
_end; ++it) {
222 fprintf(out,
" %p\n", (
void*)*it);
242 if (distance(begin, end) < 1000 ||
_varCount == 0)
245 vector<Exponent*> terms;
247 terms.reserve(distance(begin, end));
253 return copy(terms.begin(), terms.end(), begin);
258 ASSERT(isMinimallyGenerated(begin, end));
262 return colonReminimize(begin, end, var, colon[var]);
266 for (
iterator it = begin; it != blockBegin;) {
268 bool strictDivision =
true;
269 for (
size_t var = 0; var < _varCount; ++var) {
270 if (colon[var] >= (*it)[var]) {
274 strictDivision =
false;
277 (*it)[var] -= colon[var];
280 if (strictDivision) {
286 swap(*it, *blockBegin);
291 if (begin == blockBegin)
292 return make_pair(end,
false);
294 iterator newEnd = minimize(begin, blockBegin);
296 for (
iterator it = blockBegin; it != end; ++it) {
297 if (!dominatesAny(begin, blockBegin, *it)) {
303 ASSERT(isMinimallyGenerated(begin, newEnd));
304 return make_pair(newEnd,
true);
309 if (distance(begin, end) < 1000 || _varCount == 0) {
311 for (
const_iterator dominator = begin; dominator != end; ++dominator)
313 divisor != dominator)
318 vector<Exponent*> terms(begin, end);
319 TreeNode node(terms.begin(), terms.end(), _varCount);
322 vector<Exponent*> terms2;
323 node.collect(terms2);
325 return terms.size() == terms2.size();
330 for (; begin != end; ++begin)
338 for (; begin != end; ++begin)
356 for (
iterator it = begin; it != zeroBegin;) {
357 if ((*it)[var] > exponent) {
358 (*it)[var] -= exponent;
362 }
else if ((*it)[var] == 0) {
365 swap(*it, *zeroBegin);
370 if (begin == zeroBegin)
371 return make_pair(end,
false);
374 std::sort(begin, zeroBegin,
383 for (
iterator it = begin; it != end; ++it) {
385 if ((*it)[var] != block) {
387 previousBlockEnd = newEnd;
390 ASSERT((*it)[var] <= exponent);
395 for (
iterator divisor = begin; divisor != previousBlockEnd; ++divisor) {
408 return make_pair(newEnd,
true);
vector< Exponent * >::iterator iterator
bool dividesAny(iterator begin, iterator end, const Exponent *term)
TreeNode(iterator begin, iterator end, size_t varCount)
bool isRedundant(const Exponent *term)
iterator minimize(iterator begin, iterator end) const
bool dominatesAny(iterator begin, iterator end, const Exponent *term)
TermIterator simpleMinimize(TermIterator begin, TermIterator end, size_t varCount)
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
TermIterator twoVarMinimize(TermIterator begin, TermIterator end)
A predicate that sorts terms in weakly descending order according to degree of the specified variable...
size_t getSizeOfSupport() const
void collect(vector< Exponent * > &terms)
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
vector< Exponent * >::const_iterator const_iterator
static bool dominates(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a dominates b, i.e. whether b divides a.
vector< Exponent * >::iterator iterator
bool isMinimallyGenerated(const_iterator begin, const_iterator end)
size_t getFirstNonZeroExponent() const
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.
Term represents a product of variables which does not include a coefficient.
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
A predicate that sorts terms according to lexicographic order.
pair< iterator, bool > colonReminimize(iterator begin, iterator end, const Exponent *colon)