67 while ((*begin)[var] == 0) {
71 return (*(begin + (distance(begin, end) ) / 2))[var];
79 Term& co = coVariableForGetBestVar;
84 for (
size_t var = 0; var < slice.
getVarCount(); ++var)
91 for (
size_t var = 0; var < slice.
getVarCount(); ++var)
92 if (co[var] < maxCount)
112 ASSERT(!const_cast<Slice&>(slice).adjustMultiply());
113 ASSERT(!const_cast<Slice&>(slice).baseCase(
false));
123 for (
size_t var = 0; var < slice.
getVarCount(); ++var)
125 _oneCounts[var] += 1;
138 return staticGetName();
147 return _counts.getFirstMaxExponent();
155 return staticGetName();
164 for (
size_t var = 0; ; ++var) {
166 if (_oneCounts[var] > 0)
177 return staticGetName();
190 size_t mostGeneric = 0;
191 for (
size_t var = 1; var < slice.
getVarCount(); ++var)
192 if (mostGeneric == 0 ||
193 (mostGeneric > _oneCounts[var] && _oneCounts[var] > 0))
194 mostGeneric = _oneCounts[var];
195 for (
size_t var = 0; var < slice.
getVarCount(); ++var)
196 if (_oneCounts[var] != mostGeneric)
199 return _counts.getFirstMaxExponent();
213 return staticGetName();
221 size_t var = getBestVar(slice);
230 return staticGetName();
238 size_t var = getBestVar(slice);
241 pivot[var] = getMedianPositiveExponentOf(slice, var);
242 if (pivot[var] == slice.
getLcm()[var])
250 return staticGetName();
258 size_t var = getBestVar(slice);
260 pivot[var] = slice.
getLcm()[var] - 1;
267 return staticGetName();
280 for (
int attempts = 0; attempts < 10; ++attempts) {
293 if ((*it)[var1] == 0 || (*it)[var2] == 0)
299 for (
size_t var = 0; var < slice.
getVarCount(); ++var)
300 if (pivot[var] >= (*it)[var])
301 pivot[var] = (*it)[var] - 1;
316 return staticGetName();
324 size_t var = getBestVar(slice);
326 size_t nonDivisibleCount = 0;
333 for (
int i = 0; i < 3; ++i) {
334 size_t selected = rand() % nonDivisibleCount;
344 pivot.
gcd(pivot, *it);
358 return staticGetName();
366 size_t nonSquareFreeCount = 0;
371 ++nonSquareFreeCount;
373 size_t selected = rand() % nonSquareFreeCount;
393 return staticGetName();
410 size_t maxOffset = 0u;
411 for (
size_t var = 0; var < slice.
getVarCount(); ++var) {
428 ASSERT(_diff >= 0 || base == mid);
430 if (_diff > _maxDiff) {
437 pivot[maxOffset] = lcm[maxOffset] / 2;
461 (
"The split selection strategy \"frob\" is deprecated and will be " 462 "removed in a future version of Frobby. Use the name \"degree\" " 463 "to achieve the same thing.");
467 return staticGetName();
478 SplitFactory getSplitFactory() {
479 SplitFactory factory(
"Slice split strategy");
481 nameFactoryRegister<MaxLabelSplit>(factory);
482 nameFactoryRegister<MinLabelSplit>(factory);
483 nameFactoryRegister<VarLabelSplit>(factory);
484 nameFactoryRegister<MinimumSplit>(factory);
485 nameFactoryRegister<MedianSplit>(factory);
486 nameFactoryRegister<MaximumSplit>(factory);
487 nameFactoryRegister<MinGenSplit>(factory);
488 nameFactoryRegister<IndependencePivotSplit>(factory);
489 nameFactoryRegister<GcdSplit>(factory);
490 nameFactoryRegister<DegreeSplit>(factory);
491 nameFactoryRegister<DeprecatedFrobeniusSplit>(factory);
498 auto_ptr<SplitStrategy> split =
createWithPrefix(getSplitFactory(), prefix);
virtual bool isLabelSplit() const
If returns true, only call getLabelSplitVariable.
void getSupportCounts(Exponent *counts) const
counts[var] will be the number of generators divisible by var.
static const char * staticGetName()
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
Cont::const_iterator const_iterator
int getGradeSign(size_t var) const
Returns 1 if the grade strictly increases with the exponent of var, returns -1 if it strictly decreas...
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
size_t getVarCount() const
Returns the number of variables in the ambient ring.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
const Term & getLcm() const
Returns the least common multiple of the generators of getIdeal().
Term coVariableForGetBestVar
This class represents a slice, which is the central data structure of the Slice Algorithm.
This class is deprecated and is only here to create the alias "frob" for the degree split...
Exponent getMaxExponent(size_t var) const
virtual const char * getName() const
Returns the name of the strategy.
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice, const TermGrader &grader) const
Sets pivot to the pivot of a pivot split on slice.
void reset(size_t newVarCount)
const_iterator begin() const
virtual const char * getName() const
Returns the name of the strategy.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
const_iterator end() const
static const char * staticGetName()
static const char * staticGetName()
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
virtual bool isPivotSplit() const
If returns true, only call getPivot.
mpz_class _diff
This is member variable used by getPivot.
static const char * staticGetName()
A TermGrader assigns a value, the degree, to each monomial.
static const char * staticGetName()
virtual bool isPivotSplit() const
If returns true, only call getPivot.
This file contains functions for printing strings to standard error.
Term & getMultiply()
Returns for a slice .
void displayNote(const string &msg)
Display msg to standard error in a way that indicates that this is something that the user should tak...
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
static const char * staticGetName()
virtual const char * getName() const
Returns the name of the strategy.
static auto_ptr< SplitStrategy > createStrategy(const string &prefix)
Returns the strategy whose name has the given prefix.
size_t getSizeOfSupport() const
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
mpz_class _maxDiff
This is member variable used by getPivot.
virtual const char * getName() const
Returns the name of the strategy.
virtual const char * getName() const
Returns the name of the strategy.
auto_ptr< AbstractProduct > createWithPrefix(const NameFactory< AbstractProduct > &factory, const string &prefix)
Creates the unique product that has the indicated prefix, or create the actual product that has name ...
virtual bool isLabelSplit() const
If returns true, only call getLabelSplitVariable.
void setCounts(const Slice &slice) const
void reportInternalError(const string &errorMsg)
Exponent getMedianPositiveExponentOf(Slice &slice, size_t var) const
const Ideal & getIdeal() const
Returns for a slice .
static size_t getFirstMaxExponent(const Exponent *a, size_t varCount)
Returns a var such that a[var] >= a[i] for all i.
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.
void singleDegreeSortIdeal(size_t var)
Calls Ideal::singleDegreeSort on getIdeal().
bool isSquareFree() const
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.
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
This common base class provides code that is useful for writing pivot split strategies.
static const char * staticGetName()
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
virtual const char * getName() const
Returns the name of the strategy.
virtual const char * getName() const
Returns the name of the strategy.
virtual void getPivot(Term &pivot, Slice &slice) const =0
Sets pivot to the pivot of a pivot split on slice.
void setOneCounts(const Slice &slice) const
size_t getBestVar(const Slice &slice) const
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.
DeprecatedFrobeniusSplit()
static const char * staticGetName()
Term represents a product of variables which does not include a coefficient.
virtual void getPivot(Term &pivot, Slice &slice, const TermGrader &grader) const
Sets pivot to the pivot of a pivot split on slice.
virtual void getPivot(Term &pivot, Slice &slice) const
Sets pivot to the pivot of a pivot split on slice.
const mpz_class & getGrade(size_t var, Exponent exponent) const
virtual const char * getName() const
Returns the name of the strategy.
static const char * staticGetName()
virtual size_t getLabelSplitVariable(const Slice &slice) const
Returns the variable to perform a label split on.