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]) {
110 for (
size_t var = 0; var <
_varCount; ++var)
111 if (
lcm[var] >
lcm[maxVar])
113 if (
lcm[maxVar] == 0) {
124 while (left != right) {
125 while ((*left)[
_var] <=
_pivot && left != right)
127 while ((*right)[
_var] >
_pivot && left != 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);
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;
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);