15 _numberOfRowBlocks = 0;
16 _numberOfColumnBlocks = 0;
29 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
30 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
33 for (
int r = 0; r < _numberOfRowBlocks; r++)
35 for (
int c = 0; c < _numberOfColumnBlocks; c++)
43 _numberOfRowBlocks = 0;
44 _numberOfColumnBlocks = 0;
50 _rowKey = (
unsigned*)
omalloc(_numberOfRowBlocks*
sizeof(
unsigned));
51 _columnKey = (
unsigned*)
omalloc(_numberOfColumnBlocks*
sizeof(
unsigned));
54 for (
int r = 0; r < _numberOfRowBlocks; r++)
56 for (
int c = 0; c < _numberOfColumnBlocks; c++)
62 void MinorKey::set(
const int lengthOfRowArray,
const unsigned int* rowKey,
63 const int lengthOfColumnArray,
64 const unsigned int* columnKey)
67 if (_numberOfRowBlocks > 0) {
omFree(_rowKey); }
68 if (_numberOfColumnBlocks > 0) {
omFree(_columnKey); }
70 _numberOfRowBlocks = lengthOfRowArray;
71 _numberOfColumnBlocks = lengthOfColumnArray;
74 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
75 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
78 for (
int r = 0; r < _numberOfRowBlocks; r++)
79 _rowKey[r] = rowKey[r];
80 for (
int c = 0; c < _numberOfColumnBlocks; c++)
81 _columnKey[c] = columnKey[c];
85 const unsigned int*
const rowKey,
86 const int lengthOfColumnArray,
87 const unsigned int*
const columnKey)
89 _numberOfRowBlocks = lengthOfRowArray;
90 _numberOfColumnBlocks = lengthOfColumnArray;
93 _rowKey = (
unsigned*)
omalloc(_numberOfRowBlocks*
sizeof(
unsigned));
94 _columnKey = (
unsigned*)
omalloc(_numberOfColumnBlocks*
sizeof(
unsigned));
97 for (
int r = 0; r < _numberOfRowBlocks; r++)
98 _rowKey[r] = rowKey[r];
100 for (
int c = 0; c < _numberOfColumnBlocks; c++)
101 _columnKey[c] = columnKey[c];
106 _numberOfRowBlocks = 0;
107 _numberOfColumnBlocks = 0;
125 int matchedBits = -1;
131 unsigned int blockBits = getRowKey(
block);
132 unsigned int shiftedBit = 1;
136 while (exponent < 32)
138 if (shiftedBit & blockBits) matchedBits++;
139 if (matchedBits == i)
return exponent + (32 *
block);
140 shiftedBit = shiftedBit << 1;
157 int matchedBits = -1;
163 unsigned int blockBits = getColumnKey(
block);
164 unsigned int shiftedBit = 1;
168 while (exponent < 32)
170 if (shiftedBit & blockBits) matchedBits++;
171 if (matchedBits == i)
return exponent + (32 *
block);
172 shiftedBit = shiftedBit << 1;
188 unsigned int blockBits = getRowKey(
block);
189 unsigned int shiftedBit = 1;
193 while (exponent < 32)
195 if (shiftedBit & blockBits) target[i++] = exponent + (32 *
block);
196 shiftedBit = shiftedBit << 1;
209 unsigned int blockBits = getColumnKey(
block);
210 unsigned int shiftedBit = 1;
214 while (exponent < 32)
216 if (shiftedBit & blockBits) target[i++] = exponent + (32 *
block);
217 shiftedBit = shiftedBit << 1;
231 int matchedBits = -1;
237 unsigned int blockBits = getRowKey(
block);
238 unsigned int shiftedBit = 1;
242 while (exponent < 32)
244 if (shiftedBit & blockBits) matchedBits++;
245 if (exponent + (32 *
block) == i)
return matchedBits;
246 shiftedBit = shiftedBit << 1;
263 int matchedBits = -1;
269 unsigned int blockBits = getColumnKey(
block);
270 unsigned int shiftedBit = 1;
274 while (exponent < 32)
276 if (shiftedBit & blockBits) matchedBits++;
277 if (exponent + (32 *
block) == i)
return matchedBits;
278 shiftedBit = shiftedBit << 1;
289 return _rowKey[blockIndex];
294 return _columnKey[blockIndex];
299 return _numberOfRowBlocks;
304 return _numberOfColumnBlocks;
308 int MinorKey::getSetBits(
const int a)
const 313 for (
int i = 0;
i < _numberOfRowBlocks;
i++)
315 unsigned int m = _rowKey[
i];
317 for (
int j = 0;
j < 32;
j++)
327 for (
int i = 0;
i < _numberOfColumnBlocks;
i++)
329 unsigned int m = _columnKey[
i];
331 for (
int j = 0;
j < 32;
j++)
344 const int absoluteEraseColumnIndex)
const 346 int rowBlock = absoluteEraseRowIndex / 32;
347 int exponent = absoluteEraseRowIndex % 32;
348 unsigned int newRowBits = getRowKey(rowBlock) - (1 <<
exponent);
349 int highestRowBlock = getNumberOfRowBlocks() - 1;
352 if ((newRowBits == 0) && (rowBlock == highestRowBlock))
356 highestRowBlock -= 1;
357 while (getRowKey(highestRowBlock) == 0)
359 highestRowBlock -= 1;
364 int columnBlock = absoluteEraseColumnIndex / 32;
365 exponent = absoluteEraseColumnIndex % 32;
366 unsigned int newColumnBits = getColumnKey(columnBlock) - (1 <<
exponent);
367 int highestColumnBlock = getNumberOfColumnBlocks() - 1;
370 if ((newColumnBits == 0) && (columnBlock == highestColumnBlock))
374 highestColumnBlock -= 1;
375 while (getColumnKey(highestColumnBlock) == 0)
377 highestColumnBlock -= 1;
382 MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1,
387 if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1))
389 if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
395 assume(result.getSetBits(1) == result.getSetBits(2));
403 _rowKey[blockIndex] = rowKey;
407 const unsigned int columnKey)
409 _columnKey[blockIndex] = columnKey;
420 for (
int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--)
422 if (this->getRowKey(r) < that.
getRowKey(r))
return -1;
423 if (this->getRowKey(r) > that.
getRowKey(r))
return 1;
432 for (
int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
434 if (this->getColumnKey(c) < that.
getColumnKey(c))
return -1;
435 if (this->getColumnKey(c) > that.
getColumnKey(c))
return 1;
446 return this->compare(mk) == 0;
454 return this->compare(mk) == -1;
462 unsigned int highestInt = 0;
471 unsigned int currentInt = mk.
getRowKey(blockIndex);
472 unsigned int shiftedBit = 1;
475 while (exponent < 32 && hitBits < k)
477 if (shiftedBit & currentInt)
479 highestInt += shiftedBit;
482 shiftedBit = shiftedBit << 1;
489 _numberOfRowBlocks = blockIndex + 1;
491 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
493 for (
int r = 0; r < blockIndex; r++)
495 _rowKey[blockIndex] = highestInt;
503 unsigned int highestInt = 0;
513 unsigned int shiftedBit = 1;
516 while (exponent < 32 && hitBits < k)
518 if (shiftedBit & currentInt)
520 highestInt += shiftedBit;
523 shiftedBit = shiftedBit << 1;
529 _numberOfColumnBlocks = blockIndex + 1;
531 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
533 for (
int c = 0; c < blockIndex; c++)
535 _columnKey[blockIndex] = highestInt;
557 int newBitBlockIndex = 0;
558 unsigned int newBitToBeSet = 0;
561 int blockCount = this->getNumberOfRowBlocks();
571 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
572 unsigned int shiftedBit = 1 << 31;
574 while (hitBits < k && shiftedBit > 0)
576 if ((blockCount - 1 >= mkBlockIndex) &&
577 (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
578 else if (shiftedBit & currentInt)
580 newBitToBeSet = shiftedBit;
581 newBitBlockIndex = mkBlockIndex;
582 bitCounter = hitBits;
586 shiftedBit = shiftedBit >> 1;
589 if (newBitToBeSet == 0)
605 if (blockCount - 1 < newBitBlockIndex)
609 _numberOfRowBlocks = newBitBlockIndex + 1;
611 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
613 for (
int r = 0; r < _numberOfRowBlocks; r++) _rowKey[r] = 0;
619 unsigned int anInt = this->getRowKey(newBitBlockIndex);
620 unsigned int deleteBit = newBitToBeSet >> 1;
621 while (deleteBit > 0)
623 if (anInt & deleteBit) anInt -= deleteBit;
624 deleteBit = deleteBit >> 1;
626 _rowKey[newBitBlockIndex] = anInt;
629 for (
int i = 0;
i < newBitBlockIndex;
i++)
637 _rowKey[newBitBlockIndex] += newBitToBeSet;
646 while (bitCounter < k)
649 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
650 unsigned int shiftedBit = 1;
653 while (bitCounter < k && exponent < 32)
655 if (shiftedBit & currentInt)
657 _rowKey[mkBlockIndex] += shiftedBit;
660 shiftedBit = shiftedBit << 1;
688 int newBitBlockIndex = 0;
689 unsigned int newBitToBeSet = 0;
692 int blockCount = this->getNumberOfColumnBlocks();
702 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
703 unsigned int shiftedBit = 1 << 31;
705 while (hitBits < k && shiftedBit > 0)
707 if ((blockCount - 1 >= mkBlockIndex) &&
708 (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
709 else if (shiftedBit & currentInt)
711 newBitToBeSet = shiftedBit;
712 newBitBlockIndex = mkBlockIndex;
713 bitCounter = hitBits;
717 shiftedBit = shiftedBit >> 1;
720 if (newBitToBeSet == 0)
737 if (blockCount - 1 < newBitBlockIndex)
741 _numberOfColumnBlocks = newBitBlockIndex + 1;
743 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
745 for (
int c = 0; c < _numberOfColumnBlocks; c++) _columnKey[c] = 0;
751 unsigned int anInt = this->getColumnKey(newBitBlockIndex);
752 unsigned int deleteBit = newBitToBeSet >> 1;
753 while (deleteBit > 0)
755 if (anInt & deleteBit) anInt -= deleteBit;
756 deleteBit = deleteBit >> 1;
758 _columnKey[newBitBlockIndex] = anInt;
761 for (
int i = 0;
i < newBitBlockIndex;
i++)
767 _columnKey[newBitBlockIndex] += newBitToBeSet;
777 while (bitCounter < k)
780 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
781 unsigned int shiftedBit = 1;
784 while (bitCounter < k && exponent < 32)
786 if (shiftedBit & currentInt)
788 _columnKey[mkBlockIndex] += shiftedBit;
791 shiftedBit = shiftedBit << 1;
851 return (
this == &mv);
880 return _potentialRetrievals;
885 return _multiplications;
895 return _accumulatedMult;
900 return _accumulatedSum;
911 g_rankingStrategy = rankingStrategy;
921 return g_rankingStrategy;
928 switch (this->GetRankingStrategy())
930 case 1:
return this->rankMeasure1();
931 case 2:
return this->rankMeasure2();
932 case 3:
return this->rankMeasure3();
933 case 4:
return this->rankMeasure4();
934 case 5:
return this->rankMeasure5();
935 default:
return this->rankMeasure1();
943 return this->getMultiplications();
950 return this->getAccumulatedMultiplications();
957 return this->getMultiplications()
958 * (this->getPotentialRetrievals()
959 - this->getRetrievals())
960 / this->getPotentialRetrievals();
967 return this->getMultiplications()
968 * (this->getPotentialRetrievals()
969 - this->getRetrievals());
977 return this->getPotentialRetrievals() - this->getRetrievals();
985 return _accumulatedMult;
990 const int accumulatedMultiplications,
991 const int accumulatedAdditions,
992 const int retrievals,
993 const int potentialRetrievals)
996 _multiplications = multiplications;
997 _additions = additions;
998 _accumulatedMult = accumulatedMultiplications;
999 _accumulatedSum = accumulatedAdditions;
1000 _potentialRetrievals = potentialRetrievals;
1001 _retrievals = retrievals;
1007 _multiplications = -1;
1009 _accumulatedMult = -1;
1010 _accumulatedSum = -1;
1011 _potentialRetrievals = -1;
1029 bool cacheHasBeenUsed =
true;
1030 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1032 sprintf(h,
"%d", this->getResult());
1034 s +=
" [retrievals: ";
1035 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1038 if (cacheHasBeenUsed)
1040 sprintf(h,
"%d", this->getPotentialRetrievals());
1045 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1046 s +=
" (accumulated: ";
1047 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1049 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1050 s +=
" (accumulated: ";
1051 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1053 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getUtility()); s +=
h; }
1071 const int additions,
1072 const int accumulatedMultiplications,
1073 const int accumulatedAdditions,
1074 const int retrievals,
1075 const int potentialRetrievals)
1077 _result =
pCopy(result);
1078 _multiplications = multiplications;
1079 _additions = additions;
1080 _accumulatedMult = accumulatedMultiplications;
1081 _accumulatedSum = accumulatedAdditions;
1082 _potentialRetrievals = potentialRetrievals;
1083 _retrievals = retrievals;
1089 _multiplications = -1;
1091 _accumulatedMult = -1;
1092 _accumulatedSum = -1;
1093 _potentialRetrievals = -1;
1119 bool cacheHasBeenUsed =
true;
1120 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1123 s +=
" [retrievals: ";
1124 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1127 if (cacheHasBeenUsed)
1129 sprintf(h,
"%d", this->getPotentialRetrievals());
1134 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1135 s +=
" (accumulated: ";
1136 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1138 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1139 s +=
" (accumulated: ";
1140 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1142 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getUtility()); s +=
h; }
const CanonicalForm int s
PolyMinorValue()
just to make the compiler happy
int getRelativeColumnIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.
int getAdditions() const
A method for accessing the additions performed while computing this minor.
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 getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
int getResult() const
Accessor for the private field _result.
virtual ~PolyMinorValue()
Destructor.
bool operator==(const MinorValue &mv) const
just to make the compiler happy
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey. ...
std::string toString() const
A method for providing a printable version of the represented MinorKey.
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
static int g_rankingStrategy
private store for the current value ranking strategy; This member can be set using MinorValue::SetRan...
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...
bool operator<(const MinorValue &mv) const
just to make the compiler happy
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
int rankMeasure4() const
A method for obtaining a rank measure for the given MinorValue.
poly getResult() const
Accessor for the private field _result.
virtual std::string toString() const
A method for providing a printable version of the represented MinorValue.
IntMinorValue()
just to make the compiler happy
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
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.
void print() const
A method for printing a string representation of the given MinorValue to std::cout.
int getWeight() const
Accessor for the current weight of this class instance.
void selectFirstRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
int getPotentialRetrievals() const
A method for accessing the maximum number of potential retrievals of this minor.
bool operator==(const MinorKey &) const
just to make the compiler happy
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 getUtility() const
A method for obtaining a rank measure for theiven MinorValue.
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
void PrintS(const char *s)
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...
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...
void operator=(const PolyMinorValue &mv)
Assignment operator which creates a deep copy.
MinorKey(const int lengthOfRowArray=0, const unsigned int *const rowKey=NULL, const int lengthOfColumnArray=0, const unsigned int *const columnKey=NULL)
A constructor for class MinorKey.
static unsigned pLength(poly a)
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 getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
int rankMeasure2() const
A method for obtaining a rank measure for the given MinorValue.
static void p_Delete(poly *p, const ring r)
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
~MinorKey()
A destructor for deleting an instance.
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
virtual ~IntMinorValue()
Destructor.
bool operator<(const MinorKey &) const
just to make the compiler happy
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
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 )
virtual int getWeight() const
A method for retrieving the weight of a given MinorValue.
std::string toString() const
A method for providing a printable version of the represented MinorValue.
int getWeight() const
Accessor for the current weight of this class instance.
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...
void reset()
A method for deleting all entries of _rowKey and _columnKey.
int rankMeasure3() const
A method for obtaining a rank measure for the given MinorValue.
int getRetrievals() const
A method for accessing the number of retrievals of this minor.
int rankMeasure5() const
A method for obtaining a rank measure for the given MinorValue.
int rankMeasure1() const
A method for obtaining a rank measure for the given MinorValue.
#define pCopy(p)
return a copy of the poly
std::string toString() const
A method for providing a printable version of the represented MinorValue.