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;
138 if (shiftedBit & blockBits) matchedBits++;
140 shiftedBit = shiftedBit << 1;
157 int matchedBits = -1;
163 unsigned int blockBits = getColumnKey(
block);
164 unsigned int shiftedBit = 1;
170 if (shiftedBit & blockBits) matchedBits++;
172 shiftedBit = shiftedBit << 1;
188 unsigned int blockBits = getRowKey(
block);
189 unsigned int shiftedBit = 1;
195 if (shiftedBit & blockBits) target[
i++] =
exponent + (32 *
block);
196 shiftedBit = shiftedBit << 1;
209 unsigned int blockBits = getColumnKey(
block);
210 unsigned int shiftedBit = 1;
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;
244 if (shiftedBit & blockBits) matchedBits++;
246 shiftedBit = shiftedBit << 1;
263 int matchedBits = -1;
269 unsigned int blockBits = getColumnKey(
block);
270 unsigned int shiftedBit = 1;
276 if (shiftedBit & blockBits) 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))
388 result.setRowKey(rowBlock, newRowBits);
389 if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
390 result.setColumnKey(columnBlock, newColumnBits);
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;
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;
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;
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;
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)
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; }
std::string toString(const gfan::ZCone *const c)
Class IntMinorValue is derived from MinorValue and can be used for representing values in a cache for...
int getResult() const
Accessor for the private field _result.
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.
virtual ~IntMinorValue()
Destructor.
IntMinorValue()
just to make the compiler happy
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.
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.
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
void getAbsoluteColumnIndices(int *const target) const
A method for retrieving the 0-based indices of all columns encoded in this MinorKey.
void selectFirstRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
bool selectNextColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
~MinorKey()
A destructor for deleting an instance.
bool operator==(const MinorKey &) const
just to make the compiler happy
bool operator<(const MinorKey &) const
just to make the compiler happy
void reset()
A method for deleting all entries of _rowKey and _columnKey.
void selectFirstColumns(const int k, const MinorKey &mk)
This method redefines the set of columns represented by this MinorKey.
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...
void setColumnKey(const int blockIndex, const unsigned int columnKey)
A method for setting the blockIndex-th element of _columnKey.
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 set(const int lengthOfRowArray, const unsigned int *rowKey, const int lengthOfColumnArray, const unsigned int *columnKey)
A setter method for class MinorKey.
void getAbsoluteRowIndices(int *const target) const
A method for retrieving the 0-based indices of all rows encoded in this MinorKey.
void setRowKey(const int blockIndex, const unsigned int rowKey)
A method for setting the blockIndex-th element of _rowKey.
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
int getRelativeRowIndex(const int i) const
A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.
bool selectNextRows(const int k, const MinorKey &mk)
This method redefines the set of rows represented by this MinorKey.
MinorKey & operator=(const MinorKey &)
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.
std::string toString() const
A method for providing a printable version of the represented MinorKey.
int compare(const MinorKey &mk) const
A comparator for two instances of 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.
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
int getPotentialRetrievals() const
A method for accessing the maximum number of potential retrievals of this minor.
int rankMeasure4() const
A method for obtaining a rank measure for the given MinorValue.
int getAdditions() const
A method for accessing the additions performed while computing this minor.
int rankMeasure2() const
A method for obtaining a rank measure for the given MinorValue.
int getAccumulatedAdditions() const
A method for accessing the additions performed while computing this minor, including all nested addit...
int rankMeasure5() const
A method for obtaining a rank measure for the given MinorValue.
STATIC_VAR int g_rankingStrategy
private store for the current value ranking strategy; This member can be set using MinorValue::SetRan...
int getMultiplications() const
A method for accessing the multiplications performed while computing this minor.
static void SetRankingStrategy(const int rankingStrategy)
A method for determining the value ranking strategy.
void incrementRetrievals()
A method for incrementing the number of performed retrievals of this instance of MinorValue.
bool operator==(const MinorValue &mv) const
just to make the compiler happy
int rankMeasure3() const
A method for obtaining a rank measure for the given MinorValue.
virtual int getWeight() const
A method for retrieving the weight of a given MinorValue.
int getUtility() const
A method for obtaining a rank measure for theiven MinorValue.
int getRetrievals() const
A method for accessing the number of retrievals of this minor.
int rankMeasure1() const
A method for obtaining a rank measure for the given MinorValue.
virtual std::string toString() const
A method for providing a printable version of the represented MinorValue.
static int GetRankingStrategy()
Accessor for the static private field g_rankingStrategy.
int getAccumulatedMultiplications() const
A method for accessing the multiplications performed while computing this minor, including all nested...
bool operator<(const MinorValue &mv) const
just to make the compiler happy
void print() const
A method for printing a string representation of the given MinorValue to std::cout.
Class PolyMinorValue is derived from MinorValue and can be used for representing values in a cache fo...
PolyMinorValue()
just to make the compiler happy
void operator=(const PolyMinorValue &mv)
Assignment operator which creates a deep copy.
virtual ~PolyMinorValue()
Destructor.
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.
poly getResult() const
Accessor for the private field _result.
const CanonicalForm int s
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
static void p_Delete(poly *p, const ring r)
static unsigned pLength(poly a)
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatiblity layer for legacy polynomial operations (over currRing)
#define pCopy(p)
return a copy of the poly
void PrintS(const char *s)