15 _numberOfRowBlocks = 0;
16 _numberOfColumnBlocks = 0;
29 _rowKey =
new unsigned int[_numberOfRowBlocks];
30 _columnKey =
new unsigned int[_numberOfColumnBlocks];
33 for (
int r = 0;
r < _numberOfRowBlocks;
r++)
35 for (
int c = 0; c < _numberOfColumnBlocks; c++)
41 if (_numberOfRowBlocks != 0)
delete [] _rowKey;
42 if (_numberOfColumnBlocks != 0)
delete [] _columnKey;
43 _numberOfRowBlocks = 0;
44 _numberOfColumnBlocks = 0;
52 _rowKey =
new unsigned int[_numberOfRowBlocks];
53 _columnKey =
new unsigned int[_numberOfColumnBlocks];
56 for (
int r = 0;
r < _numberOfRowBlocks;
r++)
58 for (
int c = 0; c < _numberOfColumnBlocks; c++)
64 void MinorKey::set(
const int lengthOfRowArray,
const unsigned int* rowKey,
65 const int lengthOfColumnArray,
66 const unsigned int* columnKey)
69 if (_numberOfRowBlocks > 0) {
delete [] _rowKey; }
70 if (_numberOfColumnBlocks > 0) {
delete [] _columnKey; }
72 _numberOfRowBlocks = lengthOfRowArray;
73 _numberOfColumnBlocks = lengthOfColumnArray;
76 _rowKey =
new unsigned int[_numberOfRowBlocks];
77 _columnKey =
new unsigned int[_numberOfColumnBlocks];
80 for (
int r = 0;
r < _numberOfRowBlocks;
r++)
81 _rowKey[
r] = rowKey[
r];
82 for (
int c = 0; c < _numberOfColumnBlocks; c++)
83 _columnKey[c] = columnKey[c];
87 const unsigned int*
const rowKey,
88 const int lengthOfColumnArray,
89 const unsigned int*
const columnKey)
91 _numberOfRowBlocks = lengthOfRowArray;
92 _numberOfColumnBlocks = lengthOfColumnArray;
95 _rowKey =
new unsigned int[_numberOfRowBlocks];
96 _columnKey =
new unsigned int[_numberOfColumnBlocks];
99 for (
int r = 0;
r < _numberOfRowBlocks;
r++)
100 _rowKey[
r] = rowKey[
r];
102 for (
int c = 0; c < _numberOfColumnBlocks; c++)
103 _columnKey[c] = columnKey[c];
108 _numberOfRowBlocks = 0;
109 _numberOfColumnBlocks = 0;
111 delete [] _columnKey;
129 int matchedBits = -1;
135 unsigned int blockBits = getRowKey(
block);
136 unsigned int shiftedBit = 1;
140 while (exponent < 32)
142 if (shiftedBit & blockBits) matchedBits++;
143 if (matchedBits == i)
return exponent + (32 *
block);
144 shiftedBit = shiftedBit << 1;
161 int matchedBits = -1;
167 unsigned int blockBits = getColumnKey(
block);
168 unsigned int shiftedBit = 1;
172 while (exponent < 32)
174 if (shiftedBit & blockBits) matchedBits++;
175 if (matchedBits == i)
return exponent + (32 *
block);
176 shiftedBit = shiftedBit << 1;
192 unsigned int blockBits = getRowKey(
block);
193 unsigned int shiftedBit = 1;
197 while (exponent < 32)
199 if (shiftedBit & blockBits) target[i++] = exponent + (32 *
block);
200 shiftedBit = shiftedBit << 1;
213 unsigned int blockBits = getColumnKey(
block);
214 unsigned int shiftedBit = 1;
218 while (exponent < 32)
220 if (shiftedBit & blockBits) target[i++] = exponent + (32 *
block);
221 shiftedBit = shiftedBit << 1;
235 int matchedBits = -1;
241 unsigned int blockBits = getRowKey(
block);
242 unsigned int shiftedBit = 1;
246 while (exponent < 32)
248 if (shiftedBit & blockBits) matchedBits++;
249 if (exponent + (32 *
block) == i)
return matchedBits;
250 shiftedBit = shiftedBit << 1;
267 int matchedBits = -1;
273 unsigned int blockBits = getColumnKey(
block);
274 unsigned int shiftedBit = 1;
278 while (exponent < 32)
280 if (shiftedBit & blockBits) matchedBits++;
281 if (exponent + (32 *
block) == i)
return matchedBits;
282 shiftedBit = shiftedBit << 1;
293 return _rowKey[blockIndex];
298 return _columnKey[blockIndex];
303 return _numberOfRowBlocks;
308 return _numberOfColumnBlocks;
317 for (
int i = 0;
i < _numberOfRowBlocks;
i++)
319 unsigned int m = _rowKey[
i];
321 for (
int j = 0;
j < 32;
j++)
331 for (
int i = 0;
i < _numberOfColumnBlocks;
i++)
333 unsigned int m = _columnKey[
i];
335 for (
int j = 0;
j < 32;
j++)
348 const int absoluteEraseColumnIndex)
const 350 int rowBlock = absoluteEraseRowIndex / 32;
351 int exponent = absoluteEraseRowIndex % 32;
352 unsigned int newRowBits = getRowKey(rowBlock) - (1 <<
exponent);
353 int highestRowBlock = getNumberOfRowBlocks() - 1;
356 if ((newRowBits == 0) && (rowBlock == highestRowBlock))
360 highestRowBlock -= 1;
361 while (getRowKey(highestRowBlock) == 0)
363 highestRowBlock -= 1;
368 int columnBlock = absoluteEraseColumnIndex / 32;
369 exponent = absoluteEraseColumnIndex % 32;
370 unsigned int newColumnBits = getColumnKey(columnBlock) - (1 <<
exponent);
371 int highestColumnBlock = getNumberOfColumnBlocks() - 1;
374 if ((newColumnBits == 0) && (columnBlock == highestColumnBlock))
378 highestColumnBlock -= 1;
379 while (getColumnKey(highestColumnBlock) == 0)
381 highestColumnBlock -= 1;
386 MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1,
391 if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1))
393 if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
405 _rowKey[blockIndex] = rowKey;
409 const unsigned int columnKey)
411 _columnKey[blockIndex] = columnKey;
422 for (
int r = this->getNumberOfRowBlocks() - 1;
r >= 0;
r--)
424 if (this->getRowKey(
r) < that.
getRowKey(
r))
return -1;
425 if (this->getRowKey(
r) > that.
getRowKey(
r))
return 1;
434 for (
int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
436 if (this->getColumnKey(c) < that.
getColumnKey(c))
return -1;
437 if (this->getColumnKey(c) > that.
getColumnKey(c))
return 1;
448 return this->compare(mk) == 0;
456 return this->compare(mk) == -1;
464 unsigned int highestInt = 0;
473 unsigned int currentInt = mk.
getRowKey(blockIndex);
474 unsigned int shiftedBit = 1;
477 while (exponent < 32 && hitBits < k)
479 if (shiftedBit & currentInt)
481 highestInt += shiftedBit;
484 shiftedBit = shiftedBit << 1;
489 delete [] _rowKey; _rowKey = 0;
490 _numberOfRowBlocks = blockIndex + 1;
492 _rowKey =
new unsigned int[_numberOfRowBlocks];
494 for (
int r = 0;
r < blockIndex;
r++)
496 _rowKey[blockIndex] = highestInt;
504 unsigned int highestInt = 0;
514 unsigned int shiftedBit = 1;
517 while (exponent < 32 && hitBits < k)
519 if (shiftedBit & currentInt)
521 highestInt += shiftedBit;
524 shiftedBit = shiftedBit << 1;
529 delete [] _columnKey; _columnKey = 0;
530 _numberOfColumnBlocks = blockIndex + 1;
532 _columnKey =
new unsigned int[_numberOfColumnBlocks];
534 for (
int c = 0; c < blockIndex; c++)
536 _columnKey[blockIndex] = highestInt;
558 int newBitBlockIndex = 0;
559 unsigned int newBitToBeSet = 0;
562 int blockCount = this->getNumberOfRowBlocks();
572 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
573 unsigned int shiftedBit = 1 << 31;
575 while (hitBits < k && shiftedBit > 0)
577 if ((blockCount - 1 >= mkBlockIndex) &&
578 (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
579 else if (shiftedBit & currentInt)
581 newBitToBeSet = shiftedBit;
582 newBitBlockIndex = mkBlockIndex;
583 bitCounter = hitBits;
587 shiftedBit = shiftedBit >> 1;
590 if (newBitToBeSet == 0)
606 if (blockCount - 1 < newBitBlockIndex)
609 delete [] _rowKey; _rowKey = 0;
610 _numberOfRowBlocks = newBitBlockIndex + 1;
612 _rowKey =
new unsigned int[_numberOfRowBlocks];
614 for (
int r = 0;
r < _numberOfRowBlocks;
r++) _rowKey[
r] = 0;
620 unsigned int anInt = this->getRowKey(newBitBlockIndex);
621 unsigned int deleteBit = newBitToBeSet >> 1;
622 while (deleteBit > 0)
624 if (anInt & deleteBit) anInt -= deleteBit;
625 deleteBit = deleteBit >> 1;
627 _rowKey[newBitBlockIndex] = anInt;
630 for (
int i = 0;
i < newBitBlockIndex;
i++)
638 _rowKey[newBitBlockIndex] += newBitToBeSet;
647 while (bitCounter < k)
650 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
651 unsigned int shiftedBit = 1;
654 while (bitCounter < k && exponent < 32)
656 if (shiftedBit & currentInt)
658 _rowKey[mkBlockIndex] += shiftedBit;
661 shiftedBit = shiftedBit << 1;
689 int newBitBlockIndex = 0;
690 unsigned int newBitToBeSet = 0;
693 int blockCount = this->getNumberOfColumnBlocks();
703 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
704 unsigned int shiftedBit = 1 << 31;
706 while (hitBits < k && shiftedBit > 0)
708 if ((blockCount - 1 >= mkBlockIndex) &&
709 (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
710 else if (shiftedBit & currentInt)
712 newBitToBeSet = shiftedBit;
713 newBitBlockIndex = mkBlockIndex;
714 bitCounter = hitBits;
718 shiftedBit = shiftedBit >> 1;
721 if (newBitToBeSet == 0)
738 if (blockCount - 1 < newBitBlockIndex)
741 delete [] _columnKey; _columnKey = 0;
742 _numberOfColumnBlocks = newBitBlockIndex + 1;
744 _columnKey =
new unsigned int[_numberOfColumnBlocks];
746 for (
int c = 0; c < _numberOfColumnBlocks; c++) _columnKey[c] = 0;
752 unsigned int anInt = this->getColumnKey(newBitBlockIndex);
753 unsigned int deleteBit = newBitToBeSet >> 1;
754 while (deleteBit > 0)
756 if (anInt & deleteBit) anInt -= deleteBit;
757 deleteBit = deleteBit >> 1;
759 _columnKey[newBitBlockIndex] = anInt;
762 for (
int i = 0;
i < newBitBlockIndex;
i++)
768 _columnKey[newBitBlockIndex] += newBitToBeSet;
778 while (bitCounter < k)
781 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
782 unsigned int shiftedBit = 1;
785 while (bitCounter < k && exponent < 32)
787 if (shiftedBit & currentInt)
789 _columnKey[mkBlockIndex] += shiftedBit;
792 shiftedBit = shiftedBit << 1;
852 return (
this == &mv);
881 return _potentialRetrievals;
886 return _multiplications;
896 return _accumulatedMult;
901 return _accumulatedSum;
912 g_rankingStrategy = rankingStrategy;
922 return g_rankingStrategy;
929 switch (this->GetRankingStrategy())
931 case 1:
return this->rankMeasure1();
932 case 2:
return this->rankMeasure2();
933 case 3:
return this->rankMeasure3();
934 case 4:
return this->rankMeasure4();
935 case 5:
return this->rankMeasure5();
936 default:
return this->rankMeasure1();
944 return this->getMultiplications();
951 return this->getAccumulatedMultiplications();
958 return this->getMultiplications()
959 * (this->getPotentialRetrievals()
960 - this->getRetrievals())
961 / this->getPotentialRetrievals();
968 return this->getMultiplications()
969 * (this->getPotentialRetrievals()
970 - this->getRetrievals());
978 return this->getPotentialRetrievals() - this->getRetrievals();
986 return _accumulatedMult;
991 const int accumulatedMultiplications,
992 const int accumulatedAdditions,
993 const int retrievals,
994 const int potentialRetrievals)
997 _multiplications = multiplications;
998 _additions = additions;
999 _accumulatedMult = accumulatedMultiplications;
1000 _accumulatedSum = accumulatedAdditions;
1001 _potentialRetrievals = potentialRetrievals;
1002 _retrievals = retrievals;
1008 _multiplications = -1;
1010 _accumulatedMult = -1;
1011 _accumulatedSum = -1;
1012 _potentialRetrievals = -1;
1030 bool cacheHasBeenUsed =
true;
1031 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1033 sprintf(h,
"%d", this->getResult());
1035 s +=
" [retrievals: ";
1036 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1039 if (cacheHasBeenUsed)
1041 sprintf(h,
"%d", this->getPotentialRetrievals());
1046 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1047 s +=
" (accumulated: ";
1048 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1050 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1051 s +=
" (accumulated: ";
1052 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1054 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getUtility()); s +=
h; }
1072 const int additions,
1073 const int accumulatedMultiplications,
1074 const int accumulatedAdditions,
1075 const int retrievals,
1076 const int potentialRetrievals)
1078 _result =
pCopy(result);
1079 _multiplications = multiplications;
1080 _additions = additions;
1081 _accumulatedMult = accumulatedMultiplications;
1082 _accumulatedSum = accumulatedAdditions;
1083 _potentialRetrievals = potentialRetrievals;
1084 _retrievals = retrievals;
1090 _multiplications = -1;
1092 _accumulatedMult = -1;
1093 _accumulatedSum = -1;
1094 _potentialRetrievals = -1;
1120 bool cacheHasBeenUsed =
true;
1121 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1124 s +=
" [retrievals: ";
1125 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1128 if (cacheHasBeenUsed)
1130 sprintf(h,
"%d", this->getPotentialRetrievals());
1135 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1136 s +=
" (accumulated: ";
1137 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1139 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1140 s +=
" (accumulated: ";
1141 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1143 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getUtility()); s +=
h; }
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
const CanonicalForm int s
int getWeight() const
Accessor for the current weight of this class instance.
int rankMeasure2() const
A method for obtaining a rank measure for the given MinorValue.
PolyMinorValue()
just to make the compiler happy
bool operator==(const MinorKey &) const
just to make the compiler happy
bool operator<(const MinorKey &) const
just to make the compiler happy
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
int rankMeasure4() const
A method for obtaining a rank measure for the given MinorValue.
MinorKey(const int lengthOfRowArray=0, const unsigned int *const rowKey=0, const int lengthOfColumnArray=0, const unsigned int *const columnKey=0)
A constructor for class MinorKey.
void setColumnKey(const int blockIndex, const unsigned int columnKey)
A method for setting the blockIndex-th element of _columnKey.
Compatiblity layer for legacy polynomial operations (over currRing)
bool selectNextColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
int getAbsoluteRowIndex(const int i) const
A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in this...
virtual ~PolyMinorValue()
Destructor.
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
int rankMeasure3() const
A method for obtaining a rank measure for the given MinorValue.
static int g_rankingStrategy
private store for the current value ranking strategy; This member can be set using MinorValue::SetRan...
MinorKey getSubMinorKey(const int absoluteEraseRowIndex, const int absoluteEraseColumnIndex) const
A method for retrieving a sub-MinorKey resulting from omitting one row and one column of this MinorKe...
std::string toString() const
A method for providing a printable version of the represented MinorKey.
MinorKey & operator=(const MinorKey &)
just to make the compiler happy
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
static int pLength(poly a)
int getAdditions() const
A method for accessing the additions performed while computing this minor.
IntMinorValue()
just to make the compiler happy
void setRowKey(const int blockIndex, const unsigned int rowKey)
A method for setting the blockIndex-th element of _rowKey.
static int GetRankingStrategy()
Accessor for the static private field g_rankingStrategy.
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
poly getResult() const
Accessor for the private field _result.
virtual int getWeight() const
A method for retrieving the weight of a given MinorValue.
void selectFirstRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
void selectFirstColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
bool operator<(const MinorValue &mv) const
just to make the compiler happy
int getRetrievals() const
A method for accessing the number of retrievals of this minor.
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
int getAbsoluteColumnIndex(const int i) const
A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in this...
virtual std::string toString() const
A method for providing a printable version of the represented MinorValue.
void PrintS(const char *s)
int rankMeasure5() const
A method for obtaining a rank measure for the given MinorValue.
void operator=(const PolyMinorValue &mv)
Assignment operator which creates a deep copy.
bool selectNextRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
static void p_Delete(poly *p, const ring r)
int getUtility() const
A method for obtaining a rank measure for theiven MinorValue.
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
void print() const
A method for printing a string representation of the given MinorValue to std::cout.
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
~MinorKey()
A destructor for deleting an instance.
virtual ~IntMinorValue()
Destructor.
int getWeight() const
Accessor for the current weight of this class instance.
int getSetBits(const int a) const
A method for counting the number of set bits.
std::string toString(const gfan::ZCone *const c)
void set(const int lengthOfRowArray, const unsigned int *rowKey, const int lengthOfColumnArray, const unsigned int *columnKey)
A setter method for class MinorKey.
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey. ...
void reset()
A method for deleting all entries of _rowKey and _columnKey.
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
bool operator==(const MinorValue &mv) const
just to make the compiler happy
std::string toString() const
A method for providing a printable version of the represented MinorValue.
std::string toString() const
A method for providing a printable version of the represented MinorValue.
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
int getResult() const
Accessor for the private field _result.
int rankMeasure1() const
A method for obtaining a rank measure for the given MinorValue.
int getPotentialRetrievals() const
A method for accessing the maximum number of potential retrievals of this minor.
#define pCopy(p)
return a copy of the poly