Frobby 0.9.5
PivotStrategy.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2011 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 "PivotStrategy.h"
19
20#include "EulerState.h"
21#include "NameFactory.h"
22#include "RawSquareFreeTerm.h"
23#include "ElementDeleter.h"
24#include "PivotEulerAlg.h"
25
26#include <sstream>
27#include <limits>
28
29namespace Ops = SquareFreeTermOps;
30
31namespace {
32 inline size_t getPopVar(const size_t* divCounts, const size_t varCount) {
34 }
35
36 inline size_t getRareVar(const size_t* divCounts, const size_t varCount) {
37 const size_t* end = divCounts + varCount;
38 const size_t* rare = divCounts;
39 while (*rare == 0) {
40 ++rare;
41 ASSERT(rare != end); // not all zero
42 }
43
44 const size_t* it = rare + 1;
45 for (; it != end; ++it)
46 if (*it > 0 && *it < *rare)
47 rare = it;
48
49 return rare - divCounts;
50 }
51
52 inline void makeRareVarsMask
53 (Word* mask, const size_t* divCounts, const size_t varCount) {
54 const size_t rareVar = getRareVar(divCounts, varCount);
55 ASSERT(rareVar < varCount); // not all zero
56 const size_t maxCount = divCounts[rareVar];
58 for (size_t var = 0; var < varCount; ++var)
59 if (divCounts[var] == maxCount)
60 Ops::setExponent(mask, var, true);
61 }
62
63 class RawSquareFreeTerm {
64 public:
65 RawSquareFreeTerm(): _term(0), _capacity(0) {}
66 ~RawSquareFreeTerm() {delete _term;}
67
68 operator Word*() {return _term;}
69 operator const Word*() const {return _term;}
70
71 void reserve(const size_t varCount) {
72 if (varCount > _capacity) {
73 Ops::deleteTerm(_term);
74 _term = Ops::newTerm(varCount);
75 _capacity = varCount;
76 }
77 }
78
79 private:
80 Word* _term;
81 size_t _capacity;
82 };
83
84 class WithPivotTerm : public PivotStrategy {
85 protected:
86 Word* termWithCapacity(const size_t varCount) {
87 _term.reserve(varCount);
88 return _term;
89 }
90
91 private:
92 RawSquareFreeTerm _term;
93 };
94
95 class StdStrategy : public WithPivotTerm {
96 public:
97 virtual Word* getPivot(const EulerState& state,
98 const size_t* divCounts) = 0;
99 virtual void computationCompleted(const PivotEulerAlg& alg) {}
100 virtual bool shouldTranspose(const EulerState& state) const {
101 return state.getVarCount() > state.getIdeal().getGeneratorCount();
102 }
103 };
104
105 class StdPopVar : public StdStrategy {
106 public:
107 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
108 const size_t varCount = state.getVarCount();
109 return state.inPlaceStdSplit(getPopVar(divCounts, varCount));
110 }
111
112 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
113 const size_t varCount = state.getVarCount();
117 return pivot;
118 }
119
120 static const char* staticGetName() {
121 return "popvar";
122 }
123
124 virtual void getName(ostream& out) const {
125 out << staticGetName();
126 }
127 };
128
129 class StdRareVar : public StdStrategy {
130 public:
131 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
132 const size_t varCount = state.getVarCount();
133 return state.inPlaceStdSplit(getRareVar(divCounts, varCount));
134 }
135
136 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
137 const size_t varCount = state.getVarCount();
141 return pivot;
142 }
143
144 static const char* staticGetName() {
145 return "rarevar";
146 }
147
148 virtual void getName(ostream& out) const {
149 out << staticGetName();
150 }
151 };
152
153 class StdPopGcd : public StdStrategy {
154 public:
155 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
156 return state.inPlaceStdSplit(getPivot(state, divCounts));
157 }
158
159 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
160 const size_t varCount = state.getVarCount();
161 const size_t popVar = getPopVar(divCounts, varCount);
163
164 if (divCounts[popVar] == 1) {
167 return pivot;
168 }
169
170 size_t seen = 0;
171 RawSquareFreeIdeal::const_iterator it = state.getIdeal().begin();
172 RawSquareFreeIdeal::const_iterator end = state.getIdeal().end();
173 for (; it != end; ++it) {
174 if (Ops::getExponent(*it, popVar) != 0) {
175 if (seen == 0)
177 else
179 ++seen;
180 if (seen == 3)
181 break;
182 }
183 }
184 ASSERT(seen > 1);
185 return pivot;
186 }
187
188 static const char* staticGetName() {
189 return "popgcd";
190 }
191
192 virtual void getName(ostream& out) const {
193 out << staticGetName();
194 }
195 };
196
197 class StdRandom : public StdStrategy {
198 public:
199 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
200 const size_t random = getRandomNotEliminatedVar(state);
201 return state.inPlaceStdSplit(random);
202 }
203
204 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
205 const size_t varCount = state.getVarCount();
206 const size_t random = getRandomNotEliminatedVar(state);
210 return pivot;
211 }
212
213 static const char* staticGetName() {
214 return "random";
215 }
216
217 virtual void getName(ostream& out) const {
218 out << staticGetName();
219 }
220
221 private:
223 while (true) {
224 size_t random = rand() % state.getVarCount();
225 if (Ops::getExponent(state.getEliminatedVars(), random) == 0)
226 return random;
227 }
228 }
229 };
230
231 class StdAny : public StdStrategy {
232 public:
233 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
234 const size_t any = getAnyNotEliminatedVar(state);
235 return state.inPlaceStdSplit(any);
236 }
237
238 virtual Word* getPivot(const EulerState& state, const size_t* divCounts) {
239 const size_t varCount = state.getVarCount();
240 const size_t any = getAnyNotEliminatedVar(state);
244 return pivot;
245 }
246
247 static const char* staticGetName() {
248 return "any";
249 }
250
251 virtual void getName(ostream& out) const {
252 out << staticGetName();
253 }
254
255 private:
257 for (size_t var = 0; ; ++var) {
258 ASSERT(var < state.getVarCount());
259 if (Ops::getExponent(state.getEliminatedVars(), var) == 0)
260 return var;
261 }
262 }
263 };
264
265 class StdWiden : public WithPivotTerm {
266 public:
268 _strat(strat) {
269 ASSERT(_strat.get() != 0);
270 }
271
272 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
273 const size_t varCount = state.getVarCount();
274 Word* narrow = _strat->getPivot(state, divCounts);
276 state.getIdeal().getGcdOfMultiples(wide, narrow);
277 return state.inPlaceStdSplit(wide);
278 }
279
280 virtual void getName(ostream& out) const {
281 out << "widen_";
282 _strat->getName(out);
283 }
284
285 virtual void computationCompleted(const PivotEulerAlg& alg) {
286 _strat->computationCompleted(alg);
287 }
288
289 virtual bool shouldTranspose(const EulerState& state) const {
290 return _strat->shouldTranspose(state);
291 }
292
293 private:
295 };
296
297 class GenStrategy : public WithPivotTerm {
298 public:
299 typedef RawSquareFreeIdeal::iterator iterator;
300
301 virtual iterator filter(iterator begin, iterator end,
302 const size_t* divCounts,
303 const size_t varCount) = 0;
304 virtual void computationCompleted(const PivotEulerAlg& alg) {}
305 virtual bool shouldTranspose(const EulerState& state) const {
306 return state.getVarCount() < state.getIdeal().getGeneratorCount();
307 }
308 };
309
310 class GenPopVar : public GenStrategy {
311 public:
312 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
313 const size_t varCount = state.getVarCount();
314 size_t pivotIndex =
315 state.getIdeal().getMultiple(getPopVar(divCounts, varCount));
316 return state.inPlaceGenSplit(pivotIndex);
317 }
318
319 virtual iterator filter(iterator begin, iterator end,
320 const size_t* divCounts,
321 const size_t varCount) {
325 for (size_t var = 0; var < varCount; ++var)
326 if (divCounts[var] == divCounts[popVar])
327 Ops::setExponent(term, var, 1);
328
329 iterator newEnd = begin;
330 for (iterator it = begin; it != end; ++it) {
332 continue;
334 ++newEnd;
335 }
336 return newEnd;
337 }
338
339 static const char* staticGetName() {
340 return "popvar";
341 }
342
343 virtual void getName(ostream& out) const {
344 out << staticGetName();
345 }
346 };
347
348 class GenRareMax : public GenStrategy {
349 public:
350 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
351 typedef RawSquareFreeIdeal::const_iterator const_iterator;
352 const RawSquareFreeIdeal& ideal = state.getIdeal();
353 const size_t varCount = state.getVarCount();
354 const size_t rareVar = getRareVar(divCounts, varCount);
355
356 const const_iterator end = ideal.end();
357 size_t bestSupport = 0;
358 const_iterator best = end;
359 for (const_iterator it = ideal.begin(); it != end; ++it) {
361 continue;
362 const size_t support = Ops::getSizeOfSupport(*it, varCount);
363 if (bestSupport < support) {
365 best = it;
366 }
367 }
368 ASSERT(best != end);
369 return state.inPlaceGenSplit(best - ideal.begin());
370 }
371
372 virtual iterator filter(iterator begin, iterator end,
373 const size_t* divCounts,
374 const size_t varCount) {
375 const size_t rareVar = getRareVar(divCounts, varCount);
376
377 size_t bestSupport = 0;
378 iterator newEnd = begin;
379 for (iterator it = begin; it != end; ++it) {
381 continue;
382 const size_t support = Ops::getSizeOfSupport(*it, varCount);
383 if (bestSupport > support)
384 continue;
385 if (bestSupport < support) {
386 newEnd = begin;
388 }
390 ++newEnd;
391 }
392 return newEnd;
393 }
394
395 static const char* staticGetName() {
396 return "raremax";
397 }
398
399 virtual void getName(ostream& out) const {
400 out << staticGetName();
401 }
402 };
403
404 class GenRareVar : public GenStrategy {
405 public:
406 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
407 const size_t varCount = state.getVarCount();
408 size_t pivotIndex =
409 state.getIdeal().getMultiple(getRareVar(divCounts, varCount));
410 return state.inPlaceGenSplit(pivotIndex);
411 }
412
413 virtual iterator filter(iterator begin, iterator end,
414 const size_t* divCounts,
415 const size_t varCount) {
417
418 iterator newEnd = begin;
419 for (iterator it = begin; it != end; ++it) {
420 if (Ops::getExponent(*it, rareVar) == 0)
421 continue;
423 ++newEnd;
424 }
425 return newEnd;
426 }
427
428 static const char* staticGetName() {
429 return "rarevar";
430 }
431
432 virtual void getName(ostream& out) const {
433 out << staticGetName();
434 }
435 };
436
437 class GenComposite : public PivotStrategy {
438 public:
439 GenComposite():
440 _filters(0),
441 _filtersDeleter(_filters) {
442 }
443
444 typedef RawSquareFreeIdeal::iterator iterator;
445
447 exceptionSafePushBack(_filters, strat);
448 }
449
450 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
451 const size_t varCount = state.getVarCount();
452 const iterator begin = state.getIdeal().begin();
453 iterator end = state.getIdeal().end();
454 ASSERT(end - begin > 0);
455
456 for (size_t i = 0; i < _filters.size(); ++i)
457 end = _filters[i]->filter(begin, end, divCounts, varCount);
458 ASSERT(end - begin > 0);
459
460 return state.inPlaceGenSplit(0);
461 }
462
463 virtual void getName(ostream& out) const {
464 for (size_t i = 0; i < _filters.size(); ++i) {
465 if (i > 0)
466 out << '_';
467 _filters[i]->getName(out);
468 }
469 }
470
471 virtual void computationCompleted(const PivotEulerAlg& alg) {
472 for (size_t i = 0; i < _filters.size(); ++i)
473 _filters[i]->computationCompleted(alg);
474 }
475
476 virtual bool shouldTranspose(const EulerState& state) const {
477 return _filters.front()->shouldTranspose(state);
478 }
479
480 private:
481 vector<GenStrategy*> _filters;
482 ElementDeleter<vector<GenStrategy*> > _filtersDeleter;
483 };
484
485 class GenRarestVars : public GenStrategy {
486 public:
487 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
488 const size_t varCount = state.getVarCount();
489 filter(state.getIdeal().begin(), state.getIdeal().end(),
491 return state.inPlaceGenSplit(0);
492 }
493
494 virtual iterator filter(iterator begin, iterator end,
495 const size_t* divCounts,
496 const size_t varCount) {
497 size_t lastDivCount = 0;
498 while (end - begin > 1) {
499 size_t minDivCount = numeric_limits<size_t>::max();
500 for (size_t var = 0; var < varCount; ++var)
501 if (divCounts[var] > lastDivCount && minDivCount > divCounts[var])
502 minDivCount = divCounts[var];
503 if (minDivCount == numeric_limits<size_t>::max())
504 break;
505
506 end = filter(begin, end, divCounts, varCount, minDivCount);
508 }
509 return end;
510 }
511
512 static const char* staticGetName() {
513 return "rarest";
514 }
515
516 virtual void getName(ostream& out) const {
517 out << staticGetName();
518 }
519
520 private:
521 iterator filter(iterator begin, iterator end,
522 const size_t* divCounts,
523 const size_t varCount,
524 size_t divCount) {
525 // Set the support of term to be the vars of the specified rarity
528 for (size_t var = 0; var < varCount; ++var)
529 if (divCounts[var] == divCount)
530 Ops::setExponent(term, var, 1);
531
532 // Select the generators that are divisible by the most vars with
533 // the specified rarity.
534 iterator newEnd = begin;
535 size_t maxRareCount = 0;
536 _tmp.reserve(varCount);
537 Word* tmp = _tmp;
538 for (iterator it = begin; it != end; ++it) {
540 continue; // no rare vars in *it
541
542 Ops::gcd(tmp, term, *it, varCount);
544
546 continue;
547 if (maxRareCount < rareCount) {
549 newEnd = begin;
550 }
552 ++newEnd;
553 }
554 if (newEnd != begin)
555 return newEnd;
556 else
557 return end; // no rare vars in any generator, so we can't discard any
558 }
559
560 size_t getRarest(const RawSquareFreeIdeal& ideal, const size_t* divCounts) {
561 const size_t varCount = ideal.getVarCount();
565
566 for (; it != stop; ++it)
567 if (rarer(*it, *rarest, divCounts, varCount))
568 rarest = it;
569 return rarest - ideal.begin();
570 }
571
575 pair<size_t, size_t> getRarity(const Word* const term,
576 const size_t* divCounts,
577 const size_t varCount,
578 size_t above) {
579 size_t rarity = varCount;
580 size_t multiplicity = 0;
581 for (size_t var = 0; var < varCount; ++var) {
582 const size_t co = divCounts[var];
583 if (Ops::getExponent(term, var) != 0 && co <= rarity && co > above) {
584 ASSERT(divCounts[var] != 0);
585 if (co == rarity)
586 ++multiplicity;
587 else {
588 rarity = divCounts[var];
589 multiplicity = 1;
590 }
591 }
592 }
594 }
595
596 bool rarer(const Word* const a, const Word* const b,
597 const size_t* divCounts,
598 const size_t varCount) {
599 size_t lookAbove = 0;
600 while (true) {
605
606 if (rarityA.first < rarityB.first)
607 return true;
608 if (rarityA.first > rarityB.first)
609 return false;
610
611 if (rarityA.second > rarityB.second)
612 return true;
613 if (rarityA.second < rarityB.second)
614 return false;
615
616 if (rarityA.second == 0)
617 return false; // a and b are equally rare
618
619 lookAbove = rarityA.first;
620 }
621 }
622
623 RawSquareFreeTerm _tmp;
624 };
625
626 class GenMaxSupport : public GenStrategy {
627 public:
628 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
629 return state.inPlaceGenSplit(state.getIdeal().getMaxSupportGen());
630 }
631
632 virtual iterator filter(iterator begin, iterator end,
633 const size_t* divCounts,
634 const size_t varCount) {
635 size_t maxSupp = 0;
636 iterator newEnd = begin;
637 for (iterator it = begin; it != end; ++it) {
638 const size_t supp = Ops::getSizeOfSupport(*it, varCount);
639 if (maxSupp > supp)
640 continue;
641 if (maxSupp < supp) {
642 maxSupp = supp;
643 newEnd = begin;
644 }
646 ++newEnd;
647 }
648 return newEnd;
649 }
650
651 static const char* staticGetName() {
652 return "maxsupp";
653 }
654
655 virtual void getName(ostream& out) const {
656 out << staticGetName();
657 }
658 };
659
660 class GenMinSupport : public GenStrategy {
661 public:
662 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
663 return state.inPlaceGenSplit(state.getIdeal().getMinSupportGen());
664 }
665
666 virtual iterator filter(iterator begin, iterator end,
667 const size_t* divCounts,
668 const size_t varCount) {
669 size_t minSupp = varCount;
670 iterator newEnd = begin;
671 for (iterator it = begin; it != end; ++it) {
672 const size_t supp = Ops::getSizeOfSupport(*it, varCount);
673 if (minSupp < supp)
674 continue;
675 if (minSupp > supp) {
676 minSupp = supp;
677 newEnd = begin;
678 }
680 ++newEnd;
681 }
682 return newEnd;
683 }
684
685 static const char* staticGetName() {
686 return "minsupp";
687 }
688
689 virtual void getName(ostream& out) const {
690 out << staticGetName();
691 }
692 };
693
694 class GenAny : public GenStrategy {
695 public:
696 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
697 return state.inPlaceGenSplit(0);
698 }
699
700 virtual iterator filter(iterator begin, iterator end,
701 const size_t* divCounts,
702 const size_t varCount) {
703 return ++begin;
704 }
705
706 static const char* staticGetName() {
707 return "any";
708 }
709
710 virtual void getName(ostream& out) const {
711 out << staticGetName();
712 }
713 };
714
715 class GenRandom : public GenStrategy {
716 public:
717 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
719 return state.inPlaceGenSplit(pivotIndex);
720 }
721
722 virtual iterator filter(iterator begin, iterator end,
723 const size_t* divCounts,
724 const size_t varCount) {
725 const size_t genCount = end - begin;
726 const size_t choice = rand() % genCount;
727 Ops::swap(*begin, *(begin + choice), varCount);
728 return ++begin;
729 }
730
731 static const char* staticGetName() {
732 return "random";
733 }
734
735 virtual void getName(ostream& out) const {
736 out << staticGetName();
737 }
738 };
739
740 class HybridPivotStrategy : public PivotStrategy {
741 public:
742 HybridPivotStrategy(auto_ptr<PivotStrategy> stdStrat,
744 _stdStrat(stdStrat), _genStrat(genStrat) {}
745
746 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
747 if (state.getNonEliminatedVarCount() <
748 state.getIdeal().getGeneratorCount())
749 return _stdStrat->doPivot(state, divCounts);
750 else
751 return _genStrat->doPivot(state, divCounts);
752 }
753
754 virtual void getName(ostream& out) const {
755 out << "hybrid (";
756 _stdStrat->getName(out);
757 out << ", ";
758 _genStrat->getName(out);
759 out << ')';
760 }
761
762 virtual void computationCompleted(const PivotEulerAlg& alg) {
763 _stdStrat->computationCompleted(alg);
764 _genStrat->computationCompleted(alg);
765 }
766
767 virtual bool shouldTranspose(const EulerState& state) const {
768 return false;
769 }
770
771 private:
772 auto_ptr<PivotStrategy> _stdStrat;
773 auto_ptr<PivotStrategy> _genStrat;
774 };
775
776 class DebugStrategy : public PivotStrategy {
777 public:
779 _strat(strat), _out(out) {}
780
781 virtual EulerState* doPivot(EulerState& state,
782 const size_t* divCounts) {
783 const char* str1 = "\n\n\n"
784 "********************************(debug output)********************************\n"
785 "********** Processing this simplified state that is not a base case **********\n";
786 fputs(str1, _out);
787 state.print(_out);
788
789 EulerState* subState = _strat->doPivot(state, divCounts);
790 ASSERT(subState != 0);
791
792 const char* str2 =
793 "<<<<<<<<<<<<<<<<<<<<<<<<<<<< Substate 1 of 2 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n";
794 fputs(str2, _out);
795 state.print(_out);
796
797 const char* str3 =
798 "<<<<<<<<<<<<<<<<<<<<<<<<<<<< Substate 2 of 2 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n";
799 fputs(str3, _out);
800 subState->print(_out);
801
802 return subState;
803 }
804
805 virtual void getName(ostream& out) const {
806 _strat->getName(out);
807 }
808
809 virtual void computationCompleted(const PivotEulerAlg& alg) {
810 _strat->computationCompleted(alg);
811 fputs("Debug: Euler characteristic computation completed.\n", _out);
812 gmp_fprintf(_out, "Debug: Computed Euler characteristics was %Zd.\n",
813 alg.getComputedEulerCharacteristic().get_mpz_t());
814 }
815
816 virtual bool shouldTranspose(const EulerState& state) const {
817 return _strat->shouldTranspose(state);
818 }
819
820 private:
822 FILE* _out;
823 };
824
825 class StatisticsStrategy : public PivotStrategy {
826 public:
827 StatisticsStrategy(auto_ptr<PivotStrategy> strat, FILE* out):
828 _strat(strat), _out(out), _statesSplit(0), _transposes(0) {}
829
830 virtual EulerState* doPivot(EulerState& state, const size_t* divCounts) {
831 ++_statesSplit;
832 return _strat->doPivot(state, divCounts);
833 }
834
835 virtual void getName(ostream& out) const {
836 _strat->getName(out);
837 }
838
839 virtual void computationCompleted(const PivotEulerAlg& alg) {
840 _strat->computationCompleted(alg);
841 fputs("******** Statistics for Euler characteristic computation *****\n", _out);
842 fprintf(_out, "* Using unique div simplify: %s\n",
843 alg.getUseUniqueDivSimplify() ? "yes" : "no");
844 fprintf(_out, "* Using many div simplify: %s\n",
845 alg.getUseManyDivSimplify() ? "yes" : "no");
846 fprintf(_out, "* Using implied div simplify: %s\n",
847 alg.getUseAllPairsSimplify() ? "yes" : "no");
848 fprintf(_out, "* Do initial autotranspose: %s\n",
849 alg.getInitialAutoTranspose() ? "yes" : "no");
850 fprintf(_out, "* Do autotranspose at each step: %s\n",
851 alg.getAutoTranspose() ? "yes" : "no");
853 getName(strategyName);
854 fprintf(_out, "* Pivot strategy: %s\n", strategyName.str().c_str());
855
856 // The computation is a binary tree and we only see the internal
857 // nodes that each generate two more nodes. The number of leaves
858 // in a binary tree is one plus the number of internal nodes.
859 unsigned long totalStates = 2 * _statesSplit + 1;
860 fprintf(_out, "* States processed: %lu\n", (unsigned long)totalStates);
861 fprintf(_out, "* Transposes taken: %lu\n", (unsigned long)_transposes);
862 fputs("********\n", _out);
863 }
864
865 virtual bool shouldTranspose(const EulerState& state) const {
866 const bool should = _strat->shouldTranspose(state);
867 if (should)
868 ++_transposes;
869 return should;
870 }
871
872 private:
874 FILE* _out;
875 unsigned long _statesSplit;
876 mutable unsigned long _transposes;
877 };
878
881 StdFactory factory("standard pivot strategy");
887 return factory;
888 }
889
892 GenFactory factory("generator pivot strategy");
901 return factory;
902 }
903}
904
906 if (name.compare(0, 6, "widen_") != 0) {
908 return auto_ptr<PivotStrategy>(strat.release());
909 }
910
912 getStdStratFactory().create(name.substr(6, name.size() - 6));
913 return auto_ptr<PivotStrategy>(new StdWiden(subStrat));
914}
915
918 if (name.find('_') == string::npos) {
920 return auto_ptr<PivotStrategy>(strat.release());
921 }
922
923 auto_ptr<GenComposite> composite(new GenComposite());
924
925 size_t pos = 0;
926 string part;
927 do {
928 size_t nextPos = name.find('_', pos);
929 if (nextPos == string::npos) {
930 part = name.substr(pos, string::npos);
931 pos = string::npos;
932 } else {
933 part = name.substr(pos, nextPos - pos);
934 pos = nextPos + 1;
935 }
936
938 composite->addStrategy(strat);
939 } while (pos != string::npos);
940 return auto_ptr<PivotStrategy>(composite.release());
941}
942
948
953
958
void exceptionSafePushBack(Container &container, auto_ptr< Element > pointer)
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
auto_ptr< PivotStrategy > newStdPivotStrategy(const string &name)
auto_ptr< PivotStrategy > newHybridPivotStrategy(auto_ptr< PivotStrategy > stdStrat, auto_ptr< PivotStrategy > genStrat)
auto_ptr< PivotStrategy > newStatisticsPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newDefaultPivotStrategy()
auto_ptr< PivotStrategy > newDebugPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newGenPivotStrategy(const string &name)
A wrapper for a SliceStrategy that prints out what is going out for debugging purposes,...
EulerState * inPlaceGenSplit(size_t pivotIndex)
RawSquareFreeIdeal & getIdeal()
Definition EulerState.h:49
size_t getVarCount() const
Definition EulerState.h:52
EulerState * inPlaceStdSplit(size_t pivotVar)
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition NameFactory.h:33
A pivot selection strategy for the Euler algorithm.
const_iterator doesn't have all it needs to be a proper STL iterator.
iterator doesn't have all it needs to be a proper STL iterator.
A bit packed square free ideal placed in a pre-allocated buffer.
size_t getVarCount() const
size_t getGeneratorCount() const
void setExponent(Word *a, size_t var, bool value)
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
size_t getSizeOfSupport(const Word *a, size_t varCount)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void swap(Word *a, Word *b, size_t varCount)
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToIdentity(Word *res, const Word *resEnd)
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93
#define ASSERT(X)
Definition stdinc.h:86