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;
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))
401 _rowKey[blockIndex] = rowKey;
405 const unsigned int columnKey)
407 _columnKey[blockIndex] = columnKey;
418 for (
int r = this->getNumberOfRowBlocks() - 1;
r >= 0;
r--)
420 if (this->getRowKey(
r) < that.
getRowKey(
r))
return -1;
421 if (this->getRowKey(
r) > that.
getRowKey(
r))
return 1;
430 for (
int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
432 if (this->getColumnKey(c) < that.
getColumnKey(c))
return -1;
433 if (this->getColumnKey(c) > that.
getColumnKey(c))
return 1;
444 return this->compare(mk) == 0;
452 return this->compare(mk) == -1;
460 unsigned int highestInt = 0;
469 unsigned int currentInt = mk.
getRowKey(blockIndex);
470 unsigned int shiftedBit = 1;
473 while (exponent < 32 && hitBits < k)
475 if (shiftedBit & currentInt)
477 highestInt += shiftedBit;
480 shiftedBit = shiftedBit << 1;
487 _numberOfRowBlocks = blockIndex + 1;
489 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
491 for (
int r = 0;
r < blockIndex;
r++)
493 _rowKey[blockIndex] = highestInt;
501 unsigned int highestInt = 0;
511 unsigned int shiftedBit = 1;
514 while (exponent < 32 && hitBits < k)
516 if (shiftedBit & currentInt)
518 highestInt += shiftedBit;
521 shiftedBit = shiftedBit << 1;
527 _numberOfColumnBlocks = blockIndex + 1;
529 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
531 for (
int c = 0; c < blockIndex; c++)
533 _columnKey[blockIndex] = highestInt;
555 int newBitBlockIndex = 0;
556 unsigned int newBitToBeSet = 0;
559 int blockCount = this->getNumberOfRowBlocks();
569 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
570 unsigned int shiftedBit = 1 << 31;
572 while (hitBits < k && shiftedBit > 0)
574 if ((blockCount - 1 >= mkBlockIndex) &&
575 (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
576 else if (shiftedBit & currentInt)
578 newBitToBeSet = shiftedBit;
579 newBitBlockIndex = mkBlockIndex;
580 bitCounter = hitBits;
584 shiftedBit = shiftedBit >> 1;
587 if (newBitToBeSet == 0)
603 if (blockCount - 1 < newBitBlockIndex)
607 _numberOfRowBlocks = newBitBlockIndex + 1;
609 _rowKey = (
unsigned*)
omAlloc(_numberOfRowBlocks*
sizeof(
unsigned));
611 for (
int r = 0;
r < _numberOfRowBlocks;
r++) _rowKey[
r] = 0;
617 unsigned int anInt = this->getRowKey(newBitBlockIndex);
618 unsigned int deleteBit = newBitToBeSet >> 1;
619 while (deleteBit > 0)
621 if (anInt & deleteBit) anInt -= deleteBit;
622 deleteBit = deleteBit >> 1;
624 _rowKey[newBitBlockIndex] = anInt;
627 for (
int i = 0;
i < newBitBlockIndex;
i++)
635 _rowKey[newBitBlockIndex] += newBitToBeSet;
644 while (bitCounter < k)
647 unsigned int currentInt = mk.
getRowKey(mkBlockIndex);
648 unsigned int shiftedBit = 1;
651 while (bitCounter < k && exponent < 32)
653 if (shiftedBit & currentInt)
655 _rowKey[mkBlockIndex] += shiftedBit;
658 shiftedBit = shiftedBit << 1;
686 int newBitBlockIndex = 0;
687 unsigned int newBitToBeSet = 0;
690 int blockCount = this->getNumberOfColumnBlocks();
700 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
701 unsigned int shiftedBit = 1 << 31;
703 while (hitBits < k && shiftedBit > 0)
705 if ((blockCount - 1 >= mkBlockIndex) &&
706 (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
707 else if (shiftedBit & currentInt)
709 newBitToBeSet = shiftedBit;
710 newBitBlockIndex = mkBlockIndex;
711 bitCounter = hitBits;
715 shiftedBit = shiftedBit >> 1;
718 if (newBitToBeSet == 0)
735 if (blockCount - 1 < newBitBlockIndex)
739 _numberOfColumnBlocks = newBitBlockIndex + 1;
741 _columnKey = (
unsigned*)
omAlloc(_numberOfColumnBlocks*
sizeof(
unsigned));
743 for (
int c = 0; c < _numberOfColumnBlocks; c++) _columnKey[c] = 0;
749 unsigned int anInt = this->getColumnKey(newBitBlockIndex);
750 unsigned int deleteBit = newBitToBeSet >> 1;
751 while (deleteBit > 0)
753 if (anInt & deleteBit) anInt -= deleteBit;
754 deleteBit = deleteBit >> 1;
756 _columnKey[newBitBlockIndex] = anInt;
759 for (
int i = 0;
i < newBitBlockIndex;
i++)
765 _columnKey[newBitBlockIndex] += newBitToBeSet;
775 while (bitCounter < k)
778 unsigned int currentInt = mk.
getColumnKey(mkBlockIndex);
779 unsigned int shiftedBit = 1;
782 while (bitCounter < k && exponent < 32)
784 if (shiftedBit & currentInt)
786 _columnKey[mkBlockIndex] += shiftedBit;
789 shiftedBit = shiftedBit << 1;
849 return (
this == &mv);
878 return _potentialRetrievals;
883 return _multiplications;
893 return _accumulatedMult;
898 return _accumulatedSum;
909 g_rankingStrategy = rankingStrategy;
919 return g_rankingStrategy;
926 switch (this->GetRankingStrategy())
928 case 1:
return this->rankMeasure1();
929 case 2:
return this->rankMeasure2();
930 case 3:
return this->rankMeasure3();
931 case 4:
return this->rankMeasure4();
932 case 5:
return this->rankMeasure5();
933 default:
return this->rankMeasure1();
941 return this->getMultiplications();
948 return this->getAccumulatedMultiplications();
955 return this->getMultiplications()
956 * (this->getPotentialRetrievals()
957 - this->getRetrievals())
958 / this->getPotentialRetrievals();
965 return this->getMultiplications()
966 * (this->getPotentialRetrievals()
967 - this->getRetrievals());
975 return this->getPotentialRetrievals() - this->getRetrievals();
983 return _accumulatedMult;
988 const int accumulatedMultiplications,
989 const int accumulatedAdditions,
990 const int retrievals,
991 const int potentialRetrievals)
994 _multiplications = multiplications;
995 _additions = additions;
996 _accumulatedMult = accumulatedMultiplications;
997 _accumulatedSum = accumulatedAdditions;
998 _potentialRetrievals = potentialRetrievals;
999 _retrievals = retrievals;
1005 _multiplications = -1;
1007 _accumulatedMult = -1;
1008 _accumulatedSum = -1;
1009 _potentialRetrievals = -1;
1027 bool cacheHasBeenUsed =
true;
1028 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1030 sprintf(h,
"%d", this->getResult());
1032 s +=
" [retrievals: ";
1033 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1036 if (cacheHasBeenUsed)
1038 sprintf(h,
"%d", this->getPotentialRetrievals());
1043 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1044 s +=
" (accumulated: ";
1045 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1047 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1048 s +=
" (accumulated: ";
1049 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1051 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getUtility()); s +=
h; }
1069 const int additions,
1070 const int accumulatedMultiplications,
1071 const int accumulatedAdditions,
1072 const int retrievals,
1073 const int potentialRetrievals)
1075 _result =
pCopy(result);
1076 _multiplications = multiplications;
1077 _additions = additions;
1078 _accumulatedMult = accumulatedMultiplications;
1079 _accumulatedSum = accumulatedAdditions;
1080 _potentialRetrievals = potentialRetrievals;
1081 _retrievals = retrievals;
1087 _multiplications = -1;
1089 _accumulatedMult = -1;
1090 _accumulatedSum = -1;
1091 _potentialRetrievals = -1;
1117 bool cacheHasBeenUsed =
true;
1118 if (this->getRetrievals() == -1) cacheHasBeenUsed =
false;
1121 s +=
" [retrievals: ";
1122 if (cacheHasBeenUsed) { sprintf(h,
"%d", this->getRetrievals()); s +=
h; }
1125 if (cacheHasBeenUsed)
1127 sprintf(h,
"%d", this->getPotentialRetrievals());
1132 sprintf(h,
"%d", this->getMultiplications()); s +=
h;
1133 s +=
" (accumulated: ";
1134 sprintf(h,
"%d", this->getAccumulatedMultiplications()); s +=
h;
1136 sprintf(h,
"%d", this->getAdditions()); s +=
h;
1137 s +=
" (accumulated: ";
1138 sprintf(h,
"%d", this->getAccumulatedAdditions()); s +=
h;
1140 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.
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
int getSetBits(const int a) const
A method for counting the number of set bits.
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...
~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.