Changeset 68ec38 in git for Singular/Minor.cc
- Timestamp:
- Feb 2, 2010, 2:22:24 PM (14 years ago)
- Branches:
- (u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
- Children:
- 13e38971987d79bd6f926205a82e193ea34b07bd
- Parents:
- 13d171b75aff221780f5e6852dfb845024c5771b
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/Minor.cc
r13d171b r68ec38 5 5 #include "febase.h" 6 6 7 void MinorKey::reset() { 8 _numberOfRowBlocks = 0; 9 _numberOfColumnBlocks = 0; 10 delete [] _rowKey; 11 delete [] _columnKey; 12 _rowKey = 0; 13 _columnKey = 0; 14 } 15 16 MinorKey::MinorKey (const MinorKey& mk) { 17 _numberOfRowBlocks = mk.getNumberOfRowBlocks(); 18 _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();; 19 20 // allocate memory for new entries in _rowKey and _columnKey; 21 _rowKey = new unsigned int[_numberOfRowBlocks]; 22 _columnKey = new unsigned int[_numberOfColumnBlocks]; 23 24 // copying values from parameter arrays to private arrays 25 for (int r = 0; r < _numberOfRowBlocks; r++) 26 _rowKey[r] = mk.getRowKey(r); 27 for (int c = 0; c < _numberOfColumnBlocks; c++) 28 _columnKey[c] = mk.getColumnKey(c); 29 } 30 31 MinorKey& MinorKey::operator=(const MinorKey& mk) { 32 if (_numberOfRowBlocks != 0) delete [] _rowKey; 33 if (_numberOfColumnBlocks != 0) delete [] _columnKey; 34 _numberOfRowBlocks = 0; 35 _numberOfColumnBlocks = 0; 36 _rowKey = 0; 37 _columnKey = 0; 38 39 _numberOfRowBlocks = mk.getNumberOfRowBlocks(); 40 _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();; 41 42 // allocate memory for new entries in _rowKey and _columnKey; 43 _rowKey = new unsigned int[_numberOfRowBlocks]; 44 _columnKey = new unsigned int[_numberOfColumnBlocks]; 45 46 // copying values from parameter arrays to private arrays 47 for (int r = 0; r < _numberOfRowBlocks; r++) 48 _rowKey[r] = mk.getRowKey(r); 49 for (int c = 0; c < _numberOfColumnBlocks; c++) 50 _columnKey[c] = mk.getColumnKey(c); 51 52 return *this; 7 void MinorKey::reset() 8 { 9 _numberOfRowBlocks = 0; 10 _numberOfColumnBlocks = 0; 11 delete [] _rowKey; 12 delete [] _columnKey; 13 _rowKey = 0; 14 _columnKey = 0; 15 } 16 17 MinorKey::MinorKey (const MinorKey& mk) 18 { 19 _numberOfRowBlocks = mk.getNumberOfRowBlocks(); 20 _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();; 21 22 /* allocate memory for new entries in _rowKey and _columnKey */ 23 _rowKey = new unsigned int[_numberOfRowBlocks]; 24 _columnKey = new unsigned int[_numberOfColumnBlocks]; 25 26 /* copying values from parameter arrays to private arrays */ 27 for (int r = 0; r < _numberOfRowBlocks; r++) 28 _rowKey[r] = mk.getRowKey(r); 29 for (int c = 0; c < _numberOfColumnBlocks; c++) 30 _columnKey[c] = mk.getColumnKey(c); 31 } 32 33 MinorKey& MinorKey::operator=(const MinorKey& mk) 34 { 35 if (_numberOfRowBlocks != 0) delete [] _rowKey; 36 if (_numberOfColumnBlocks != 0) delete [] _columnKey; 37 _numberOfRowBlocks = 0; 38 _numberOfColumnBlocks = 0; 39 _rowKey = 0; 40 _columnKey = 0; 41 42 _numberOfRowBlocks = mk.getNumberOfRowBlocks(); 43 _numberOfColumnBlocks = mk.getNumberOfColumnBlocks();; 44 45 /* allocate memory for new entries in _rowKey and _columnKey */ 46 _rowKey = new unsigned int[_numberOfRowBlocks]; 47 _columnKey = new unsigned int[_numberOfColumnBlocks]; 48 49 /* copying values from parameter arrays to private arrays */ 50 for (int r = 0; r < _numberOfRowBlocks; r++) 51 _rowKey[r] = mk.getRowKey(r); 52 for (int c = 0; c < _numberOfColumnBlocks; c++) 53 _columnKey[c] = mk.getColumnKey(c); 54 55 return *this; 53 56 } 54 57 55 58 void MinorKey::set(const int lengthOfRowArray, const unsigned int* rowKey, 56 const int lengthOfColumnArray, const unsigned int* columnKey) { 57 // free memory of _rowKey and _columnKey 58 if (_numberOfRowBlocks > 0) { delete [] _rowKey; } 59 if (_numberOfColumnBlocks > 0) { delete [] _columnKey; } 60 61 _numberOfRowBlocks = lengthOfRowArray; 62 _numberOfColumnBlocks = lengthOfColumnArray; 63 64 // allocate memory for new entries in _rowKey and _columnKey; 65 _rowKey = new unsigned int[_numberOfRowBlocks]; 66 _columnKey = new unsigned int[_numberOfColumnBlocks]; 67 68 // copying values from parameter arrays to private arrays 69 for (int r = 0; r < _numberOfRowBlocks; r++) 70 _rowKey[r] = rowKey[r]; 71 for (int c = 0; c < _numberOfColumnBlocks; c++) 72 _columnKey[c] = columnKey[c]; 73 } 74 75 MinorKey::MinorKey(const int lengthOfRowArray, const unsigned int* const rowKey, 76 const int lengthOfColumnArray, const unsigned int* const columnKey) { 77 _numberOfRowBlocks = lengthOfRowArray; 78 _numberOfColumnBlocks = lengthOfColumnArray; 79 80 // allocate memory for new entries in _rowKey and _columnKey; 81 _rowKey = new unsigned int[_numberOfRowBlocks]; 82 _columnKey = new unsigned int[_numberOfColumnBlocks]; 83 84 // copying values from parameter arrays to private arrays 85 for (int r = 0; r < _numberOfRowBlocks; r++) 86 _rowKey[r] = rowKey[r]; 87 88 for (int c = 0; c < _numberOfColumnBlocks; c++) 89 _columnKey[c] = columnKey[c]; 90 } 91 92 MinorKey::~MinorKey() { 93 // free memory of _rowKey and _columnKey 94 delete [] _rowKey; 95 delete [] _columnKey; 96 } 97 98 void MinorKey::print() const { 99 cout << this->toString(); 100 } 101 102 int MinorKey::getAbsoluteRowIndex(const int i) const { 103 // This method is to return the absolute (0-based) index of the i-th row encoded in \a this. 104 // Example: bit-pattern of rows: "10010001101", i = 3: 105 // This should yield the 0-based absolute index of the 3-rd bit (counted from the right), i.e. 7. 106 107 int matchedBits = -1; // counter for matched bits; this needs to reach i, then we're done 108 for (int block = 0; block < getNumberOfRowBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 109 unsigned int blockBits = getRowKey(block); // the bits in this block of 32 bits 110 unsigned int shiftedBit = 1; 111 int exponent = 0; 112 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 113 while (exponent < 32) { 114 if (shiftedBit & blockBits) matchedBits++; 115 if (matchedBits == i) return exponent + (32 * block); 116 shiftedBit = shiftedBit << 1; 117 exponent++; 118 } 119 } 120 // We should never reach this line of code. 121 assert(false); 122 } 123 124 int MinorKey::getAbsoluteColumnIndex(const int i) const { 125 // This method is to return the absolute (0-based) index of the i-th column encoded in \a this. 126 // Example: bit-pattern of columns: "10010001101", i = 3: 127 // This should yield the 0-based absolute index of the 3-rd bit (counted from the right), i.e. 7. 128 129 int matchedBits = -1; // counter for matched bits; this needs to reach i, then we're done 130 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 131 unsigned int blockBits = getColumnKey(block); // the bits in this block of 32 bits 132 unsigned int shiftedBit = 1; 133 int exponent = 0; 134 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 135 while (exponent < 32) { 136 if (shiftedBit & blockBits) matchedBits++; 137 if (matchedBits == i) return exponent + (32 * block); 138 shiftedBit = shiftedBit << 1; 139 exponent++; 140 } 141 } 142 // We should never reach this line of code. 143 assert(false); 144 } 145 146 void MinorKey::getAbsoluteRowIndices(int* const target) const { 147 int i = 0; // index for filling the target array 148 for (int block = 0; block < getNumberOfRowBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 149 unsigned int blockBits = getRowKey(block); // the bits in this block of 32 bits 150 unsigned int shiftedBit = 1; 151 int exponent = 0; 152 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 153 while (exponent < 32) { 154 if (shiftedBit & blockBits) target[i++] = exponent + (32 * block); 155 shiftedBit = shiftedBit << 1; 156 exponent++; 157 } 158 } 159 return; 160 } 161 162 void MinorKey::getAbsoluteColumnIndices(int* const target) const { 163 int i = 0; // index for filling the target array 164 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 165 unsigned int blockBits = getColumnKey(block); // the bits in this block of 32 bits 166 unsigned int shiftedBit = 1; 167 int exponent = 0; 168 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 169 while (exponent < 32) { 170 if (shiftedBit & blockBits) target[i++] = exponent + (32 * block); 171 shiftedBit = shiftedBit << 1; 172 exponent++; 173 } 174 } 175 return; 176 } 177 178 int MinorKey::getRelativeRowIndex(const int i) const { 179 // This method is to return the relative (0-based) index of the row with absolute index \c i. 180 // Example: bit-pattern of rows: "10010001101", i = 7: 181 // This should yield the 0-based relative index of the bit corresponding to row no. 7, 182 // i.e. 3. 183 184 int matchedBits = -1; // counter for matched bits; this is going to contain our return value 185 for (int block = 0; block < getNumberOfRowBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 186 unsigned int blockBits = getRowKey(block); // the bits in this block of 32 bits 187 unsigned int shiftedBit = 1; 188 int exponent = 0; 189 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 190 while (exponent < 32) { 191 if (shiftedBit & blockBits) matchedBits++; 192 if (exponent + (32 * block) == i) return matchedBits; 193 shiftedBit = shiftedBit << 1; 194 exponent++; 195 } 196 } 197 // We should never reach this line of code. 198 assert(false); 199 } 200 201 int MinorKey::getRelativeColumnIndex(const int i) const { 202 // This method is to return the relative (0-based) index of the column with absolute index \c i. 203 // Example: bit-pattern of columns: "10010001101", i = 7: 204 // This should yield the 0-based relative index of the bit corresponding to column no. 7, 205 // i.e. 3. 206 207 int matchedBits = -1; // counter for matched bits; this is going to contain our return value 208 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) { // start with lowest bits, i.e. in block No. 0 209 unsigned int blockBits = getColumnKey(block); // the bits in this block of 32 bits 210 unsigned int shiftedBit = 1; 211 int exponent = 0; 212 // The invariant "shiftedBit = 2^exponent" will hold throughout the entire while loop. 213 while (exponent < 32) { 214 if (shiftedBit & blockBits) matchedBits++; 215 if (exponent + (32 * block) == i) return matchedBits; 216 shiftedBit = shiftedBit << 1; 217 exponent++; 218 } 219 } 220 // We should never reach this line of code. 221 assert(false); 222 } 223 224 unsigned int MinorKey::getRowKey(const int blockIndex) const { 225 return _rowKey[blockIndex]; 226 } 227 228 unsigned int MinorKey::getColumnKey(const int blockIndex) const { 229 return _columnKey[blockIndex]; 230 } 231 232 int MinorKey::getNumberOfRowBlocks() const { 233 return _numberOfRowBlocks; 234 } 235 236 int MinorKey::getNumberOfColumnBlocks() const { 237 return _numberOfColumnBlocks; 238 } 239 240 int MinorKey::getSetBits(const int a) const { 241 int b = 0; 242 if (a == 1) { // rows 243 for (int i = 0; i < _numberOfRowBlocks; i++) { 244 unsigned int m = _rowKey[i]; 245 unsigned int k = 1; 246 for (int j = 0; j < 32; j++) { 247 // k = 2^j 248 if (m & k) b++; 249 k = k << 1; 250 } 251 } 252 } 253 else { // columns 254 for (int i = 0; i < _numberOfColumnBlocks; i++) { 255 unsigned int m = _columnKey[i]; 256 unsigned int k = 1; 257 for (int j = 0; j < 32; j++) { 258 // k = 2^j 259 if (m & k) b++; 260 k = k << 1; 261 } 262 } 263 } 264 return b; 59 const int lengthOfColumnArray, 60 const unsigned int* columnKey) 61 { 62 /* free memory of _rowKey and _columnKey */ 63 if (_numberOfRowBlocks > 0) { delete [] _rowKey; } 64 if (_numberOfColumnBlocks > 0) { delete [] _columnKey; } 65 66 _numberOfRowBlocks = lengthOfRowArray; 67 _numberOfColumnBlocks = lengthOfColumnArray; 68 69 /* allocate memory for new entries in _rowKey and _columnKey; */ 70 _rowKey = new unsigned int[_numberOfRowBlocks]; 71 _columnKey = new unsigned int[_numberOfColumnBlocks]; 72 73 /* copying values from parameter arrays to private arrays */ 74 for (int r = 0; r < _numberOfRowBlocks; r++) 75 _rowKey[r] = rowKey[r]; 76 for (int c = 0; c < _numberOfColumnBlocks; c++) 77 _columnKey[c] = columnKey[c]; 78 } 79 80 MinorKey::MinorKey(const int lengthOfRowArray, 81 const unsigned int* const rowKey, 82 const int lengthOfColumnArray, 83 const unsigned int* const columnKey) 84 { 85 _numberOfRowBlocks = lengthOfRowArray; 86 _numberOfColumnBlocks = lengthOfColumnArray; 87 88 /* allocate memory for new entries in _rowKey and _columnKey */ 89 _rowKey = new unsigned int[_numberOfRowBlocks]; 90 _columnKey = new unsigned int[_numberOfColumnBlocks]; 91 92 /* copying values from parameter arrays to private arrays */ 93 for (int r = 0; r < _numberOfRowBlocks; r++) 94 _rowKey[r] = rowKey[r]; 95 96 for (int c = 0; c < _numberOfColumnBlocks; c++) 97 _columnKey[c] = columnKey[c]; 98 } 99 100 MinorKey::~MinorKey() 101 { 102 /* free memory of _rowKey and _columnKey */ 103 delete [] _rowKey; 104 delete [] _columnKey; 105 } 106 107 void MinorKey::print() const 108 { 109 cout << this->toString(); 110 } 111 112 int MinorKey::getAbsoluteRowIndex(const int i) const 113 { 114 /* This method is to return the absolute (0-based) index of the i-th 115 row encoded in \a this. 116 Example: bit-pattern of rows: "10010001101", i = 3: 117 This should yield the 0-based absolute index of the 3-rd bit 118 (counted from the right), i.e. 7. */ 119 120 int matchedBits = -1; /* counter for matched bits; 121 this needs to reach i, then we're done */ 122 for (int block = 0; block < getNumberOfRowBlocks(); block ++) 123 { 124 /* start with lowest bits, i.e. in block No. 0 */ 125 /* the bits in this block of 32 bits: */ 126 unsigned int blockBits = getRowKey(block); 127 unsigned int shiftedBit = 1; 128 int exponent = 0; 129 /* The invariant "shiftedBit = 2^exponent" will hold throughout the 130 entire while loop. */ 131 while (exponent < 32) 132 { 133 if (shiftedBit & blockBits) matchedBits++; 134 if (matchedBits == i) return exponent + (32 * block); 135 shiftedBit = shiftedBit << 1; 136 exponent++; 137 } 138 } 139 /* We should never reach this line of code. */ 140 assert(false); 141 } 142 143 int MinorKey::getAbsoluteColumnIndex(const int i) const 144 { 145 /* This method is to return the absolute (0-based) index of the i-th 146 column encoded in \a this. 147 Example: bit-pattern of columns: "10010001101", i = 3: 148 This should yield the 0-based absolute index of the 3-rd bit 149 (counted from the right), i.e. 7. */ 150 151 int matchedBits = -1; /* counter for matched bits; this needs to reach i, 152 then we're done */ 153 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) 154 { 155 /* start with lowest bits, i.e. in block No. 0 */ 156 /* the bits in this block of 32 bits: */ 157 unsigned int blockBits = getColumnKey(block); 158 unsigned int shiftedBit = 1; 159 int exponent = 0; 160 /* The invariant "shiftedBit = 2^exponent" will hold throughout the 161 entire while loop. */ 162 while (exponent < 32) 163 { 164 if (shiftedBit & blockBits) matchedBits++; 165 if (matchedBits == i) return exponent + (32 * block); 166 shiftedBit = shiftedBit << 1; 167 exponent++; 168 } 169 } 170 /* We should never reach this line of code. */ 171 assert(false); 172 } 173 174 void MinorKey::getAbsoluteRowIndices(int* const target) const 175 { 176 int i = 0; /* index for filling the target array */ 177 for (int block = 0; block < getNumberOfRowBlocks(); block ++) 178 { 179 /* start with lowest bits, i.e. in block No. 0 */ 180 /* the bits in this block of 32 bits: */ 181 unsigned int blockBits = getRowKey(block); 182 unsigned int shiftedBit = 1; 183 int exponent = 0; 184 /* The invariant "shiftedBit = 2^exponent" will hold throughout the 185 entire while loop. */ 186 while (exponent < 32) 187 { 188 if (shiftedBit & blockBits) target[i++] = exponent + (32 * block); 189 shiftedBit = shiftedBit << 1; 190 exponent++; 191 } 192 } 193 return; 194 } 195 196 void MinorKey::getAbsoluteColumnIndices(int* const target) const 197 { 198 int i = 0; /* index for filling the target array */ 199 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) 200 { 201 /* start with lowest bits, i.e. in block No. 0 */ 202 /* the bits in this block of 32 bits: */ 203 unsigned int blockBits = getColumnKey(block); 204 unsigned int shiftedBit = 1; 205 int exponent = 0; 206 /* The invariant "shiftedBit = 2^exponent" will hold throughout the 207 entire while loop. */ 208 while (exponent < 32) 209 { 210 if (shiftedBit & blockBits) target[i++] = exponent + (32 * block); 211 shiftedBit = shiftedBit << 1; 212 exponent++; 213 } 214 } 215 return; 216 } 217 218 int MinorKey::getRelativeRowIndex(const int i) const 219 { 220 /* This method is to return the relative (0-based) index of the row 221 with absolute index \c i. 222 Example: bit-pattern of rows: "10010001101", i = 7: 223 This should yield the 0-based relative index of the bit 224 corresponding to row no. 7, i.e. 3. */ 225 226 int matchedBits = -1; /* counter for matched bits; this is going to 227 contain our return value */ 228 for (int block = 0; block < getNumberOfRowBlocks(); block ++) 229 { 230 /* start with lowest bits, i.e. in block No. 0 */ 231 /* the bits in this block of 32 bits: */ 232 unsigned int blockBits = getRowKey(block); 233 unsigned int shiftedBit = 1; 234 int exponent = 0; 235 /* The invariant "shiftedBit = 2^exponent" will hold throughout the 236 entire while loop. */ 237 while (exponent < 32) 238 { 239 if (shiftedBit & blockBits) matchedBits++; 240 if (exponent + (32 * block) == i) return matchedBits; 241 shiftedBit = shiftedBit << 1; 242 exponent++; 243 } 244 } 245 /* We should never reach this line of code. */ 246 assert(false); 247 } 248 249 int MinorKey::getRelativeColumnIndex(const int i) const 250 { 251 /* This method is to return the relative (0-based) index 252 of the column with absolute index \c i. 253 Example: bit-pattern of columns: "10010001101", i = 7: 254 This should yield the 0-based relative index of the bit 255 corresponding to column no. 7, i.e. 3. */ 256 257 int matchedBits = -1; /* counter for matched bits; this is going 258 to contain our return value */ 259 for (int block = 0; block < getNumberOfColumnBlocks(); block ++) 260 { 261 /* start with lowest bits, i.e. in block No. 0 */ 262 /* the bits in this block of 32 bits: */ 263 unsigned int blockBits = getColumnKey(block); 264 unsigned int shiftedBit = 1; 265 int exponent = 0; 266 /* The invariant "shiftedBit = 2^exponent" will hold 267 throughout the entire while loop. */ 268 while (exponent < 32) 269 { 270 if (shiftedBit & blockBits) matchedBits++; 271 if (exponent + (32 * block) == i) return matchedBits; 272 shiftedBit = shiftedBit << 1; 273 exponent++; 274 } 275 } 276 /* We should never reach this line of code. */ 277 assert(false); 278 } 279 280 unsigned int MinorKey::getRowKey(const int blockIndex) const 281 { 282 return _rowKey[blockIndex]; 283 } 284 285 unsigned int MinorKey::getColumnKey(const int blockIndex) const 286 { 287 return _columnKey[blockIndex]; 288 } 289 290 int MinorKey::getNumberOfRowBlocks() const 291 { 292 return _numberOfRowBlocks; 293 } 294 295 int MinorKey::getNumberOfColumnBlocks() const 296 { 297 return _numberOfColumnBlocks; 298 } 299 300 int MinorKey::getSetBits(const int a) const 301 { 302 int b = 0; 303 if (a == 1) 304 { /* rows */ 305 for (int i = 0; i < _numberOfRowBlocks; i++) 306 { 307 unsigned int m = _rowKey[i]; 308 unsigned int k = 1; 309 for (int j = 0; j < 32; j++) 310 { 311 /* k = 2^j */ 312 if (m & k) b++; 313 k = k << 1; 314 } 315 } 316 } 317 else 318 { /* columns */ 319 for (int i = 0; i < _numberOfColumnBlocks; i++) 320 { 321 unsigned int m = _columnKey[i]; 322 unsigned int k = 1; 323 for (int j = 0; j < 32; j++) 324 { 325 /* k = 2^j */ 326 if (m & k) b++; 327 k = k << 1; 328 } 329 } 330 } 331 return b; 265 332 } 266 333 267 334 MinorKey MinorKey::getSubMinorKey (const int absoluteEraseRowIndex, 268 const int absoluteEraseColumnIndex) const { 269 int rowBlock = absoluteEraseRowIndex / 32; 270 int exponent = absoluteEraseRowIndex % 32; 271 unsigned int newRowBits = getRowKey(rowBlock) - (1 << exponent); 272 int highestRowBlock = getNumberOfRowBlocks() - 1; 273 // highestRowBlock will finally contain the highest block index with non-zero bit pattern 274 if ((newRowBits == 0) && (rowBlock == highestRowBlock)) { 275 // we have thus nullified the highest block; 276 // we can now forget about the highest block... 277 highestRowBlock -= 1; 278 while (getRowKey(highestRowBlock) == 0) // ...and maybe even some more zero-blocks 279 highestRowBlock -= 1; 280 } 281 // highestRowBlock now contains the highest row block index with non-zero bit pattern 282 283 int columnBlock = absoluteEraseColumnIndex / 32; 284 exponent = absoluteEraseColumnIndex % 32; 285 unsigned int newColumnBits = getColumnKey(columnBlock) - (1 << exponent); 286 int highestColumnBlock = getNumberOfColumnBlocks() - 1; 287 // highestColumnBlock will finally contain the highest block index with non-zero bit pattern 288 if ((newColumnBits == 0) && (columnBlock == highestColumnBlock)) { 289 // we have thus nullified the highest block; 290 // we can now forget about the highest block... 291 highestColumnBlock -= 1; 292 while (getColumnKey(highestColumnBlock) == 0) // ...and maybe even some more zero-blocks 293 highestColumnBlock -= 1; 294 } 295 // highestColumnBlock now contains the highest column block index with non-zero bit pattern 296 297 MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1, _columnKey); 298 // This is just a copy with maybe some leading bit blocks omitted. We still need to re-define 299 // the row block at index 'rowBlock' and the column block at index 'columnBlock': 300 if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1)) result.setRowKey(rowBlock, newRowBits); 301 if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1)) result.setColumnKey(columnBlock, newColumnBits); 302 303 if (result.getSetBits(1) != result.getSetBits(2)) { // asserts that the number of selected rows and columns are equal 304 cout << endl; 305 this->print(); 306 cout << endl; 307 result.print(); 308 cout << endl; 309 cout << "rows: " << result.getSetBits(1) << " / columns: " << result.getSetBits(2); 310 cout << endl; 311 cout << "row to be erased: " << absoluteEraseRowIndex << " / column to be erased: " << absoluteEraseColumnIndex << endl; 312 assert(false); 313 } 314 315 return result; 316 } 317 318 void MinorKey::setRowKey (const int blockIndex, const unsigned int rowKey) { 335 const int absoluteEraseColumnIndex) const 336 { 337 int rowBlock = absoluteEraseRowIndex / 32; 338 int exponent = absoluteEraseRowIndex % 32; 339 unsigned int newRowBits = getRowKey(rowBlock) - (1 << exponent); 340 int highestRowBlock = getNumberOfRowBlocks() - 1; 341 /* highestRowBlock will finally contain the highest block index with 342 non-zero bit pattern */ 343 if ((newRowBits == 0) && (rowBlock == highestRowBlock)) 344 { 345 /* we have thus nullified the highest block; 346 we can now forget about the highest block... */ 347 highestRowBlock -= 1; 348 while (getRowKey(highestRowBlock) == 0) /* ...and maybe even some more 349 zero-blocks */ 350 highestRowBlock -= 1; 351 } 352 /* highestRowBlock now contains the highest row block index with non-zero 353 bit pattern */ 354 355 int columnBlock = absoluteEraseColumnIndex / 32; 356 exponent = absoluteEraseColumnIndex % 32; 357 unsigned int newColumnBits = getColumnKey(columnBlock) - (1 << exponent); 358 int highestColumnBlock = getNumberOfColumnBlocks() - 1; 359 /* highestColumnBlock will finally contain the highest block index with 360 non-zero bit pattern */ 361 if ((newColumnBits == 0) && (columnBlock == highestColumnBlock)) 362 { 363 /* we have thus nullified the highest block; 364 we can now forget about the highest block... */ 365 highestColumnBlock -= 1; 366 while (getColumnKey(highestColumnBlock) == 0) /* ...and maybe even some 367 more zero-blocks */ 368 highestColumnBlock -= 1; 369 } 370 /* highestColumnBlock now contains the highest column block index with 371 non-zero bit pattern */ 372 373 MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1, 374 _columnKey); 375 /* This is just a copy with maybe some leading bit blocks omitted. We still 376 need to re-define the row block at index 'rowBlock' and the column block 377 at index 'columnBlock': */ 378 if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1)) 379 result.setRowKey(rowBlock, newRowBits); 380 if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1)) 381 result.setColumnKey(columnBlock, newColumnBits); 382 383 /* let's check that the number of selected rows and columns are equal; 384 (this check is only performed in the debug version) */ 385 assume(result.getSetBits(1) != result.getSetBits(2)); 386 387 return result; 388 } 389 390 void MinorKey::setRowKey (const int blockIndex, const unsigned int rowKey) 391 { 319 392 _rowKey[blockIndex] = rowKey; 320 393 } 321 394 322 void MinorKey::setColumnKey (const int blockIndex, const unsigned int columnKey) { 395 void MinorKey::setColumnKey (const int blockIndex, 396 const unsigned int columnKey) 397 { 323 398 _columnKey[blockIndex] = columnKey; 324 399 } 325 400 326 int MinorKey::compare (const MinorKey& that) const { 327 // compare by rowKeys first; in case of equality, use columnKeys 328 if (this->getNumberOfRowBlocks() < that.getNumberOfRowBlocks()) 329 return -1; 330 if (this->getNumberOfRowBlocks() > that.getNumberOfRowBlocks()) 331 return 1; 332 // Here, numbers of rows are equal. 333 for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--) { 334 if (this->getRowKey(r) < that.getRowKey(r)) return -1; 335 if (this->getRowKey(r) > that.getRowKey(r)) return 1; 336 } 337 // Here, this and that encode ecaxtly the same sets of rows. 338 // Now, we take a look at the columns. 339 if (this->getNumberOfColumnBlocks() < that.getNumberOfColumnBlocks()) 340 return -1; 341 if (this->getNumberOfColumnBlocks() > that.getNumberOfColumnBlocks()) 342 return 1; 343 // Here, numbers of columns are equal. 344 for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--) { 345 if (this->getColumnKey(c) < that.getColumnKey(c)) return -1; 346 if (this->getColumnKey(c) > that.getColumnKey(c)) return 1; 347 } 348 // Here, this and that encode exactly the same sets of rows and columns. 349 return 0; 350 } 351 352 // just to make the compiler happy; 353 // this method should never be called 354 bool MinorKey::operator==(const MinorKey& mk) const { 355 assert(false); 356 return this->compare(mk) == 0; 357 } 358 359 // just to make the compiler happy; 360 // this method should never be called 361 bool MinorKey::operator<(const MinorKey& mk) const { 362 assert(false); 363 return this->compare(mk) == -1; 364 } 365 366 void MinorKey::selectFirstRows (const int k, const MinorKey& mk) { 367 int hitBits = 0; // the number of bits we have hit; in the end, this has to be equal to k, 368 // the dimension of the minor 369 int blockIndex = -1; // the index of the current int in mk 370 unsigned int highestInt = 0; // the new highest block of this MinorKey 371 // We determine which ints of mk we can copy. Their indices will be 0, 1, ..., blockIndex - 1. 372 // And highestInt is going to capture the highest int (which may be only a portion of 373 // the corresponding int in mk. We loop until hitBits = k: 374 while (hitBits < k) { 375 blockIndex++; 376 highestInt = 0; 377 unsigned int currentInt = mk.getRowKey(blockIndex); 378 unsigned int shiftedBit = 1; 379 int exponent = 0; 380 // invariant in the loop: shiftedBit = 2^exponent 381 while (exponent < 32 && hitBits < k) { 382 if (shiftedBit & currentInt) { 383 highestInt += shiftedBit; 384 hitBits++; 385 } 386 shiftedBit = shiftedBit << 1; 387 exponent++; 388 } 389 } 390 // free old memory 391 delete [] _rowKey; _rowKey = 0; 392 _numberOfRowBlocks = blockIndex + 1; 393 // allocate memory for new entries in _rowKey; 394 _rowKey = new unsigned int[_numberOfRowBlocks]; 395 // copying values from mk to this MinorKey 396 for (int r = 0; r < blockIndex; r++) 397 _rowKey[r] = mk.getRowKey(r); 398 _rowKey[blockIndex] = highestInt; 399 } 400 401 void MinorKey::selectFirstColumns (const int k, const MinorKey& mk) { 402 int hitBits = 0; // the number of bits we have hit; in the end, this has to be equal to k, 403 // the dimension of the minor 404 int blockIndex = -1; // the index of the current int in mk 405 unsigned int highestInt = 0; // the new highest block of this MinorKey 406 // We determine which ints of mk we can copy. Their indices will be 0, 1, ..., blockIndex - 1. 407 // And highestInt is going to capture the highest int (which may be only a portion of 408 // the corresponding int in mk. We loop until hitBits = k: 409 while (hitBits < k) { 410 blockIndex++; 411 highestInt = 0; 412 unsigned int currentInt = mk.getColumnKey(blockIndex); 413 unsigned int shiftedBit = 1; 414 int exponent = 0; 415 // invariant in the loop: shiftedBit = 2^exponent 416 while (exponent < 32 && hitBits < k) { 417 if (shiftedBit & currentInt) { 418 highestInt += shiftedBit; 419 hitBits++; 420 } 421 shiftedBit = shiftedBit << 1; 422 exponent++; 423 } 424 } 425 // free old memory 426 delete [] _columnKey; _columnKey = 0; 427 _numberOfColumnBlocks = blockIndex + 1; 428 // allocate memory for new entries in _columnKey; 429 _columnKey = new unsigned int[_numberOfColumnBlocks]; 430 // copying values from mk to this MinorKey 431 for (int c = 0; c < blockIndex; c++) 432 _columnKey[c] = mk.getColumnKey(c); 433 _columnKey[blockIndex] = highestInt; 434 } 435 436 bool MinorKey::selectNextRows (const int k, const MinorKey& mk) { 437 // We need to compute the set of k rows which must all be contained in mk. 438 // AND: This set must be the least possible of this kind which is larger 439 // than the currently encoded set of rows. (Here, '<' is w.r.t. to the natural 440 // ordering on multi-indices. 441 // Example: mk encodes the rows according to the bit pattern 11010111, k = 3, this 442 // MinorKey encodes 10010100. Then, the method must shift the set of rows in 443 // this MinorKey to 11000001 (, and return true). 444 445 // The next two variables will finally name a row which is 446 // (1) currently not yet among the rows in this MinorKey, but 447 // (2) among the rows in mk, and 448 // (3) which is "higher" than the lowest row in this MinorKey, and 449 // (4) which is the lowest possible choice such that (1) - (3) hold. 450 // If we should not be able to find such a row, then there is no next subset of rows. 451 // In this case, the method will return false; otherwise always true. 452 int newBitBlockIndex = 0; // the block index of the bit 453 unsigned int newBitToBeSet = 0; // the bit as 2^e, where 0 <= e <= 31 454 455 int blockCount = this->getNumberOfRowBlocks(); // number of ints (representing rows) in this MinorKey 456 int mkBlockIndex = mk.getNumberOfRowBlocks(); // for iterating along the blocks of mk 457 458 int hitBits = 0; // the number of bits we have hit 459 int bitCounter = 0; // for storing the number of bits hit before a specific moment; see below 460 461 while (hitBits < k) { 462 mkBlockIndex--; 463 unsigned int currentInt = mk.getRowKey(mkBlockIndex); 464 unsigned int shiftedBit = 1 << 31; // initially, this equals 2^31, i.e. the highest bit 465 while (hitBits < k && shiftedBit > 0) { 466 if ((blockCount - 1 >= mkBlockIndex) && 467 (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++; 468 else if (shiftedBit & currentInt) { 469 newBitToBeSet = shiftedBit; 470 newBitBlockIndex = mkBlockIndex; 471 bitCounter = hitBits; // So, whenever we set newBitToBeSet, we want to remember the momentary 472 // number of hit bits. This will later be needed; see below. 473 } 474 shiftedBit = shiftedBit >> 1; 475 } 476 } 477 478 if (newBitToBeSet == 0) { 479 return false; 480 } 481 else { 482 // Note that the following must hold when reaching this line of code: 483 // (1) The row with bit newBitToBeSet in this->getRowKey(newBitBlockIndex) is currently 484 // not among the rows in this MinorKey, but 485 // (2) it is among the rows in mk, and 486 // (3) it is higher than the lowest row in this MinorKey, and 487 // (4) it is the lowest possible choice such that (1) - (3) hold. 488 // In the above example, we would reach this line with 489 // newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7). 490 491 if (blockCount - 1 < newBitBlockIndex) { // In this case, _rowKey is to small. 492 // free old memory 493 delete [] _rowKey; _rowKey = 0; 494 _numberOfRowBlocks = newBitBlockIndex + 1; 495 // allocate memory for new entries in _rowKey; 496 _rowKey = new unsigned int[_numberOfRowBlocks]; 497 } 498 else { 499 // We need to delete all bits in _rowKey[newBitBlockIndex] that are below newBitToBeSet: 500 unsigned int anInt = this->getRowKey(newBitBlockIndex); 501 unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5 502 while (deleteBit > 0) { 503 if (anInt & deleteBit) anInt -= deleteBit; 504 deleteBit = deleteBit >> 1; 505 }; 506 _rowKey[newBitBlockIndex] = anInt; 507 // ...and we delete all entries in _rowKey[i] for 0 <= i < newBitBlockIndex 508 for (int i = 0; i < newBitBlockIndex; i++) 509 _rowKey[i] = 0; 510 } 511 512 // We have now deleted all bits from _rowKey[...] below the bit 2^newBitToBeSet. 513 // In the example we shall have at this point: _rowKey[...] = 10000000. 514 // Now let's set the new bit: 515 _rowKey[newBitBlockIndex] += newBitToBeSet; // _rowKey[newBitBlockIndex] = 11000000 516 bitCounter++; // This is now the number of correct bits in _rowKey[...]; i.e. in the 517 // example this will be equal to 2. 518 519 // Now we only need to fill _rowKey[...] with the lowest possible bits until it 520 // consists of exactly k bits. (We know that we need to set exactly (k - bitCounter) 521 // additional bits.) 522 mkBlockIndex = -1; 523 while (bitCounter < k) { 524 mkBlockIndex++; 525 unsigned int currentInt = mk.getRowKey(mkBlockIndex); 526 unsigned int shiftedBit = 1; 527 int exponent = 0; 528 // invariant: shiftedBit = 2^exponent 529 while (bitCounter < k && exponent < 32) { 530 if (shiftedBit & currentInt) { 531 _rowKey[mkBlockIndex] += shiftedBit; 532 bitCounter++; 533 }; 534 shiftedBit = shiftedBit << 1; 535 exponent++; 536 } 401 int MinorKey::compare (const MinorKey& that) const 402 { 403 /* compare by rowKeys first; in case of equality, use columnKeys */ 404 if (this->getNumberOfRowBlocks() < that.getNumberOfRowBlocks()) 405 return -1; 406 if (this->getNumberOfRowBlocks() > that.getNumberOfRowBlocks()) 407 return 1; 408 /* Here, numbers of rows are equal. */ 409 for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--) 410 { 411 if (this->getRowKey(r) < that.getRowKey(r)) return -1; 412 if (this->getRowKey(r) > that.getRowKey(r)) return 1; 413 } 414 /* Here, this and that encode ecaxtly the same sets of rows. 415 Now, we take a look at the columns. */ 416 if (this->getNumberOfColumnBlocks() < that.getNumberOfColumnBlocks()) 417 return -1; 418 if (this->getNumberOfColumnBlocks() > that.getNumberOfColumnBlocks()) 419 return 1; 420 /* Here, numbers of columns are equal. */ 421 for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--) 422 { 423 if (this->getColumnKey(c) < that.getColumnKey(c)) return -1; 424 if (this->getColumnKey(c) > that.getColumnKey(c)) return 1; 425 } 426 /* Here, this and that encode exactly the same sets of rows and columns. */ 427 return 0; 428 } 429 430 /* just to make the compiler happy; 431 this method should never be called */ 432 bool MinorKey::operator==(const MinorKey& mk) const 433 { 434 assert(false); 435 return this->compare(mk) == 0; 436 } 437 438 /* just to make the compiler happy; 439 this method should never be called */ 440 bool MinorKey::operator<(const MinorKey& mk) const 441 { 442 assert(false); 443 return this->compare(mk) == -1; 444 } 445 446 void MinorKey::selectFirstRows (const int k, const MinorKey& mk) 447 { 448 int hitBits = 0; /* the number of bits we have hit; in the end, this 449 has to be equal to k, the dimension of the minor */ 450 int blockIndex = -1; /* the index of the current int in mk */ 451 unsigned int highestInt = 0; /* the new highest block of this MinorKey */ 452 /* We determine which ints of mk we can copy. Their indices will be 453 0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest 454 int (which may be only a portion of the corresponding int in mk. 455 We loop until hitBits = k: */ 456 while (hitBits < k) 457 { 458 blockIndex++; 459 highestInt = 0; 460 unsigned int currentInt = mk.getRowKey(blockIndex); 461 unsigned int shiftedBit = 1; 462 int exponent = 0; 463 /* invariant in the loop: shiftedBit = 2^exponent */ 464 while (exponent < 32 && hitBits < k) 465 { 466 if (shiftedBit & currentInt) 467 { 468 highestInt += shiftedBit; 469 hitBits++; 470 } 471 shiftedBit = shiftedBit << 1; 472 exponent++; 473 } 474 } 475 /* free old memory */ 476 delete [] _rowKey; _rowKey = 0; 477 _numberOfRowBlocks = blockIndex + 1; 478 /* allocate memory for new entries in _rowKey; */ 479 _rowKey = new unsigned int[_numberOfRowBlocks]; 480 /* copying values from mk to this MinorKey */ 481 for (int r = 0; r < blockIndex; r++) 482 _rowKey[r] = mk.getRowKey(r); 483 _rowKey[blockIndex] = highestInt; 484 } 485 486 void MinorKey::selectFirstColumns (const int k, const MinorKey& mk) 487 { 488 int hitBits = 0; /* the number of bits we have hit; in the end, this 489 has to be equal to k, the dimension of the minor */ 490 int blockIndex = -1; /* the index of the current int in mk */ 491 unsigned int highestInt = 0; /* the new highest block of this MinorKey */ 492 /* We determine which ints of mk we can copy. Their indices will be 493 0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest 494 int (which may be only a portion of the corresponding int in mk. 495 We loop until hitBits = k: */ 496 while (hitBits < k) 497 { 498 blockIndex++; 499 highestInt = 0; 500 unsigned int currentInt = mk.getColumnKey(blockIndex); 501 unsigned int shiftedBit = 1; 502 int exponent = 0; 503 /* invariant in the loop: shiftedBit = 2^exponent */ 504 while (exponent < 32 && hitBits < k) 505 { 506 if (shiftedBit & currentInt) 507 { 508 highestInt += shiftedBit; 509 hitBits++; 510 } 511 shiftedBit = shiftedBit << 1; 512 exponent++; 513 } 514 } 515 /* free old memory */ 516 delete [] _columnKey; _columnKey = 0; 517 _numberOfColumnBlocks = blockIndex + 1; 518 /* allocate memory for new entries in _columnKey; */ 519 _columnKey = new unsigned int[_numberOfColumnBlocks]; 520 /* copying values from mk to this MinorKey */ 521 for (int c = 0; c < blockIndex; c++) 522 _columnKey[c] = mk.getColumnKey(c); 523 _columnKey[blockIndex] = highestInt; 524 } 525 526 bool MinorKey::selectNextRows (const int k, const MinorKey& mk) 527 { 528 /* We need to compute the set of k rows which must all be contained in mk. 529 AND: This set must be the least possible of this kind which is larger 530 than the currently encoded set of rows. (Here, '<' is w.r.t. to the 531 natural ordering on multi-indices. 532 Example: mk encodes the rows according to the bit pattern 11010111, 533 k = 3, this MinorKey encodes 10010100. Then, the method must 534 shift the set of rows in this MinorKey to 11000001 (, and 535 return true). */ 536 537 /* The next two variables will finally name a row which is 538 (1) currently not yet among the rows in this MinorKey, but 539 (2) among the rows in mk, and 540 (3) which is "higher" than the lowest row in this MinorKey, and 541 (4) which is the lowest possible choice such that (1) - (3) hold. 542 If we should not be able to find such a row, then there is no next 543 subset of rows. In this case, the method will return false; otherwise 544 always true. */ 545 int newBitBlockIndex = 0; /* the block index of the bit */ 546 unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */ 547 548 /* number of ints (representing rows) in this MinorKey: */ 549 int blockCount = this->getNumberOfRowBlocks(); 550 /* for iterating along the blocks of mk: */ 551 int mkBlockIndex = mk.getNumberOfRowBlocks(); 552 553 int hitBits = 0; /* the number of bits we have hit */ 554 int bitCounter = 0; /* for storing the number of bits hit before a 555 specific moment; see below */ 556 557 while (hitBits < k) 558 { 559 mkBlockIndex--; 560 unsigned int currentInt = mk.getRowKey(mkBlockIndex); 561 unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e. 562 the highest bit */ 563 while (hitBits < k && shiftedBit > 0) 564 { 565 if ((blockCount - 1 >= mkBlockIndex) && 566 (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++; 567 else if (shiftedBit & currentInt) 568 { 569 newBitToBeSet = shiftedBit; 570 newBitBlockIndex = mkBlockIndex; 571 bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want 572 to remember the momentary number of hit 573 bits. This will later be needed; see below. */ 574 } 575 shiftedBit = shiftedBit >> 1; 576 } 577 } 578 579 if (newBitToBeSet == 0) 580 { 581 return false; 582 } 583 else 584 { 585 /* Note that the following must hold when reaching this line of code: 586 (1) The row with bit newBitToBeSet in this->getRowKey(newBitBlockIndex) 587 is currently not among the rows in this MinorKey, but 588 (2) it is among the rows in mk, and 589 (3) it is higher than the lowest row in this MinorKey, and 590 (4) it is the lowest possible choice such that (1) - (3) hold. 591 In the above example, we would reach this line with 592 newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7). 593 */ 594 595 if (blockCount - 1 < newBitBlockIndex) 596 { /* In this case, _rowKey is too small. */ 597 /* free old memory */ 598 delete [] _rowKey; _rowKey = 0; 599 _numberOfRowBlocks = newBitBlockIndex + 1; 600 /* allocate memory for new entries in _rowKey; */ 601 _rowKey = new unsigned int[_numberOfRowBlocks]; 602 } 603 else 604 { 605 /* We need to delete all bits in _rowKey[newBitBlockIndex] that are 606 below newBitToBeSet: */ 607 unsigned int anInt = this->getRowKey(newBitBlockIndex); 608 unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5 609 while (deleteBit > 0) 610 { 611 if (anInt & deleteBit) anInt -= deleteBit; 612 deleteBit = deleteBit >> 1; 613 }; 614 _rowKey[newBitBlockIndex] = anInt; 615 /* ...and we delete all entries in _rowKey[i] for 616 0 <= i < newBitBlockIndex */ 617 for (int i = 0; i < newBitBlockIndex; i++) 618 _rowKey[i] = 0; 619 } 620 621 /* We have now deleted all bits from _rowKey[...] below the bit 622 2^newBitToBeSet. 623 In the example we shall have at this point: _rowKey[...] = 10000000. 624 Now let's set the new bit: */ 625 _rowKey[newBitBlockIndex] += newBitToBeSet; 626 /* in the example: _rowKey[newBitBlockIndex] = 11000000 */ 627 bitCounter++; /* This is now the number of correct bits in _rowKey[...]; 628 i.e. in the example this will be equal to 2. */ 629 630 /* Now we only need to fill _rowKey[...] with the lowest possible bits 631 until it consists of exactly k bits. (We know that we need to set 632 exactly (k - bitCounter) additional bits.) */ 633 mkBlockIndex = -1; 634 while (bitCounter < k) 635 { 636 mkBlockIndex++; 637 unsigned int currentInt = mk.getRowKey(mkBlockIndex); 638 unsigned int shiftedBit = 1; 639 int exponent = 0; 640 /* invariant: shiftedBit = 2^exponent */ 641 while (bitCounter < k && exponent < 32) 642 { 643 if (shiftedBit & currentInt) 644 { 645 _rowKey[mkBlockIndex] += shiftedBit; 646 bitCounter++; 537 647 }; 538 // in the example, we shall obtain _rowKey[...] = 11000001 539 540 return true; 541 } 542 } 543 544 bool MinorKey::selectNextColumns (const int k, const MinorKey& mk) { 545 // We need to compute the set of k columns which must all be contained in mk. 546 // AND: This set must be the least possible of this kind which is larger 547 // than the currently encoded set of columns. (Here, '<' is w.r.t. to the natural 548 // ordering on multi-indices. 549 // Example: mk encodes the columns according to the bit pattern 11010111, k = 3, this 550 // MinorKey encodes 10010100. Then, the method must shift the set of columns in 551 // this MinorKey to 11000001 (, and return true). 552 553 // The next two variables will finally name a columns which is 554 // (1) currently not yet among the columns in this MinorKey, but 555 // (2) among the columns in mk, and 556 // (3) which is "higher" than the lowest columns in this MinorKey, and 557 // (4) which is the lowest possible choice such that (1) - (3) hold. 558 // If we should not be able to find such a columns, then there is no next subset of columns. 559 // In this case, the method will return false; otherwise always true. 560 int newBitBlockIndex = 0; // the block index of the bit 561 unsigned int newBitToBeSet = 0; // the bit as 2^e, where 0 <= e <= 31 562 563 int blockCount = this->getNumberOfColumnBlocks(); // number of ints (representing columns) in this MinorKey 564 int mkBlockIndex = mk.getNumberOfColumnBlocks(); // for iterating along the blocks of mk 565 566 int hitBits = 0; // the number of bits we have hit 567 int bitCounter = 0; // for storing the number of bits hit before a specific moment; see below 568 569 while (hitBits < k) { 570 mkBlockIndex--; 571 unsigned int currentInt = mk.getColumnKey(mkBlockIndex); 572 unsigned int shiftedBit = 1 << 31; // initially, this equals 2^31, i.e. the highest bit 573 while (hitBits < k && shiftedBit > 0) { 574 if ((blockCount - 1 >= mkBlockIndex) && 575 (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++; 576 else if (shiftedBit & currentInt) { 577 newBitToBeSet = shiftedBit; 578 newBitBlockIndex = mkBlockIndex; 579 bitCounter = hitBits; // So, whenever we set newBitToBeSet, we want to remember the momentary 580 // number of hit bits. This will later be needed; see below. 581 } 582 shiftedBit = shiftedBit >> 1; 583 } 584 } 585 586 if (newBitToBeSet == 0) { 587 return false; 588 } 589 else { 590 // Note that the following must hold when reaching this line of code: 591 // (1) The columns with bit newBitToBeSet in this->getColumnKey(newBitBlockIndex) is currently 592 // not among the columns in this MinorKey, but 593 // (2) it is among the columns in mk, and 594 // (3) it is higher than the lowest columns in this MinorKey, and 595 // (4) it is the lowest possible choice such that (1) - (3) hold. 596 // In the above example, we would reach this line with 597 // newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7). 598 599 if (blockCount - 1 < newBitBlockIndex) { // In this case, _columnKey is to small. 600 // free old memory 601 delete [] _columnKey; _columnKey = 0; 602 _numberOfColumnBlocks = newBitBlockIndex + 1; 603 // allocate memory for new entries in _columnKey; 604 _columnKey = new unsigned int[_numberOfColumnBlocks]; 605 } 606 else { 607 // We need to delete all bits in _columnKey[newBitBlockIndex] that are below newBitToBeSet: 608 unsigned int anInt = this->getColumnKey(newBitBlockIndex); 609 unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5 610 while (deleteBit > 0) { 611 if (anInt & deleteBit) anInt -= deleteBit; 612 deleteBit = deleteBit >> 1; 613 }; 614 _columnKey[newBitBlockIndex] = anInt; 615 // ...and we delete all entries in _columnKey[i] for 0 <= i < newBitBlockIndex 616 for (int i = 0; i < newBitBlockIndex; i++) 617 _columnKey[i] = 0; 618 } 619 620 // We have now deleted all bits from _columnKey[...] below the bit 2^newBitToBeSet. 621 // In the example we shall have at this point: _columnKey[...] = 10000000. 622 // Now let's set the new bit: 623 _columnKey[newBitBlockIndex] += newBitToBeSet; // _columnKey[newBitBlockIndex] = 11000000 624 bitCounter++; // This is now the number of correct bits in _columnKey[...]; i.e. in the 625 // example this will be equal to 2. 626 627 // Now we only need to fill _columnKey[...] with the lowest possible bits until it 628 // consists of exactly k bits. (We know that we need to set exactly (k - bitCounter) 629 // additional bits.) 630 mkBlockIndex = -1; 631 while (bitCounter < k) { 632 mkBlockIndex++; 633 unsigned int currentInt = mk.getColumnKey(mkBlockIndex); 634 unsigned int shiftedBit = 1; 635 int exponent = 0; 636 // invariant: shiftedBit = 2^exponent 637 while (bitCounter < k && exponent < 32) { 638 if (shiftedBit & currentInt) { 639 _columnKey[mkBlockIndex] += shiftedBit; 640 bitCounter++; 641 }; 642 shiftedBit = shiftedBit << 1; 643 exponent++; 644 } 648 shiftedBit = shiftedBit << 1; 649 exponent++; 650 } 651 }; 652 /* in the example, we shall obtain _rowKey[...] = 11000001 */ 653 654 return true; 655 } 656 } 657 658 bool MinorKey::selectNextColumns (const int k, const MinorKey& mk) 659 { 660 /* We need to compute the set of k columns which must all be contained in mk. 661 AND: This set must be the least possible of this kind which is larger 662 than the currently encoded set of columns. (Here, '<' is w.r.t. to 663 the natural ordering on multi-indices. 664 Example: mk encodes the columns according to the bit pattern 11010111, 665 k = 3, this MinorKey encodes 10010100. Then, the method must 666 shift the set of columns in this MinorKey to 11000001 (, and 667 return true). */ 668 669 /* The next two variables will finally name a columns which is 670 (1) currently not yet among the columns in this MinorKey, but 671 (2) among the columns in mk, and 672 (3) which is "higher" than the lowest columns in this MinorKey, and 673 (4) which is the lowest possible choice such that (1) - (3) hold. 674 If we should not be able to find such a columns, then there is no next 675 subset of columns. In this case, the method will return false; otherwise 676 always true. */ 677 int newBitBlockIndex = 0; /* the block index of the bit */ 678 unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */ 679 680 /* number of ints (representing columns) in this MinorKey: */ 681 int blockCount = this->getNumberOfColumnBlocks(); 682 /* for iterating along the blocks of mk: */ 683 int mkBlockIndex = mk.getNumberOfColumnBlocks(); 684 685 int hitBits = 0; /* the number of bits we have hit */ 686 int bitCounter = 0; /* for storing the number of bits hit before a specific 687 moment; see below */ 688 689 while (hitBits < k) 690 { 691 mkBlockIndex--; 692 unsigned int currentInt = mk.getColumnKey(mkBlockIndex); 693 unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e. 694 the highest bit */ 695 while (hitBits < k && shiftedBit > 0) 696 { 697 if ((blockCount - 1 >= mkBlockIndex) && 698 (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++; 699 else if (shiftedBit & currentInt) 700 { 701 newBitToBeSet = shiftedBit; 702 newBitBlockIndex = mkBlockIndex; 703 bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want to 704 remember the momentary number of hit bits. 705 This will later be needed; see below. */ 706 } 707 shiftedBit = shiftedBit >> 1; 708 } 709 } 710 711 if (newBitToBeSet == 0) 712 { 713 return false; 714 } 715 else 716 { 717 /* Note that the following must hold when reaching this line of code: 718 (1) The columns with bit newBitToBeSet in 719 this->getColumnKey(newBitBlockIndex) is currently not among the 720 columns in this MinorKey, but 721 (2) it is among the columns in mk, and 722 (3) it is higher than the lowest columns in this MinorKey, and 723 (4) it is the lowest possible choice such that (1) - (3) hold. 724 In the above example, we would reach this line with 725 newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7). 726 */ 727 728 if (blockCount - 1 < newBitBlockIndex) 729 { /* In this case, _columnKey is too small. */ 730 /* free old memory */ 731 delete [] _columnKey; _columnKey = 0; 732 _numberOfColumnBlocks = newBitBlockIndex + 1; 733 /* allocate memory for new entries in _columnKey; */ 734 _columnKey = new unsigned int[_numberOfColumnBlocks]; 735 } 736 else 737 { 738 /* We need to delete all bits in _columnKey[newBitBlockIndex] that are 739 below newBitToBeSet: */ 740 unsigned int anInt = this->getColumnKey(newBitBlockIndex); 741 unsigned int deleteBit = newBitToBeSet >> 1; /* in example: = 2^5 */ 742 while (deleteBit > 0) 743 { 744 if (anInt & deleteBit) anInt -= deleteBit; 745 deleteBit = deleteBit >> 1; 746 }; 747 _columnKey[newBitBlockIndex] = anInt; 748 /* ...and we delete all entries in _columnKey[i] fo 749 0 <= i < newBitBlockIndex */ 750 for (int i = 0; i < newBitBlockIndex; i++) 751 _columnKey[i] = 0; 752 } 753 754 /* We have now deleted all bits from _columnKey[...] below the bit 755 2^newBitToBeSet. In the example we shall have at this point: 756 _columnKey[...] = 10000000. Now let's set the new bit: */ 757 _columnKey[newBitBlockIndex] += newBitToBeSet; 758 /* in the example: _columnKey[newBitBlockIndex] = 11000000 */ 759 bitCounter++; /* This is now the number of correct bits in 760 _columnKey[...]; i.e. in the example this will be equal 761 to 2. */ 762 763 /* Now we only need to fill _columnKey[...] with the lowest possible bits 764 until it consists of exactly k bits. (We know that we need to set 765 exactly (k - bitCounter) additional bits.) */ 766 mkBlockIndex = -1; 767 while (bitCounter < k) 768 { 769 mkBlockIndex++; 770 unsigned int currentInt = mk.getColumnKey(mkBlockIndex); 771 unsigned int shiftedBit = 1; 772 int exponent = 0; 773 /* invariant: shiftedBit = 2^exponent */ 774 while (bitCounter < k && exponent < 32) 775 { 776 if (shiftedBit & currentInt) 777 { 778 _columnKey[mkBlockIndex] += shiftedBit; 779 bitCounter++; 645 780 }; 646 // in the example, we shall obtain _columnKey[...] = 11000001 647 648 return true; 649 } 650 } 651 652 string MinorKey::toString() const { 653 char h[32]; 654 string t = ""; 655 string s = "("; 656 unsigned int z = 0; 657 for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--) { 658 z = this->getRowKey(r); 659 while (z != 0) 660 { 661 if ((z % 2) != 0) t = "1" + t; else t = "0" + t; 662 z = z / 2; 663 } 664 if (r < this->getNumberOfRowBlocks() - 1) 665 t = string(32 - t.length(), '0') + t; 666 s += t; 667 } 668 s += ", "; 669 t = ""; 670 for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--) { 671 z = this->getColumnKey(c); 672 while (z != 0) 673 { 674 if ((z % 2) != 0) t = "1" + t; else t = "0" + t; 675 z = z / 2; 676 } 677 if (c < this->getNumberOfColumnBlocks() - 1) 678 t = string(32 - t.length(), '0') + t; 679 s += t; 680 } 681 s += ")"; 682 return s; 781 shiftedBit = shiftedBit << 1; 782 exponent++; 783 } 784 }; 785 /* in the example, we shall obtain _columnKey[...] = 11000001 */ 786 787 return true; 788 } 789 } 790 791 string MinorKey::toString() const 792 { 793 char h[32]; 794 string t = ""; 795 string s = "("; 796 unsigned int z = 0; 797 for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--) 798 { 799 z = this->getRowKey(r); 800 while (z != 0) 801 { 802 if ((z % 2) != 0) t = "1" + t; else t = "0" + t; 803 z = z / 2; 804 } 805 if (r < this->getNumberOfRowBlocks() - 1) 806 t = string(32 - t.length(), '0') + t; 807 s += t; 808 } 809 s += ", "; 810 t = ""; 811 for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--) 812 { 813 z = this->getColumnKey(c); 814 while (z != 0) 815 { 816 if ((z % 2) != 0) t = "1" + t; else t = "0" + t; 817 z = z / 2; 818 } 819 if (c < this->getNumberOfColumnBlocks() - 1) 820 t = string(32 - t.length(), '0') + t; 821 s += t; 822 } 823 s += ")"; 824 return s; 683 825 } 684 826 … … 687 829 int MinorValue::getWeight () const 688 830 { 689 assert(false); / / must be overridden in derived classes831 assert(false); /* must be overridden in derived classes */ 690 832 return 0; 691 833 } 692 834 693 // just to make the compiler happy; 694 // this method should never be called 695 bool MinorValue::operator==(const MinorValue& mv) const { 696 assert(false); 697 return (this == &mv); // compare addresses of both objects 835 /* just to make the compiler happy; 836 this method should never be called */ 837 bool MinorValue::operator==(const MinorValue& mv) const 838 { 839 assert(false); 840 return (this == &mv); /* compare addresses of both objects */ 698 841 } 699 842 700 843 string MinorValue::toString () const 701 844 { 702 assert(false); / / must be overridden in derived classes845 assert(false); /* must be overridden in derived classes */ 703 846 return ""; 704 847 } 705 848 706 // just to make the compiler happy; 707 // this method should never be called 708 bool MinorValue::operator<(const MinorValue& mv) const { 709 assert(false); 710 return (this < &mv); // compare addresses of both objects 711 } 712 713 int MinorValue::getRetrievals() const { 714 return _retrievals; 715 } 716 717 void MinorValue::incrementRetrievals() { 718 _retrievals++; 719 } 720 721 int MinorValue::getPotentialRetrievals() const { 722 return _potentialRetrievals; 723 } 724 725 int MinorValue::getMultiplications() const { 726 return _multiplications; 727 } 728 729 int MinorValue::getAdditions() const { 730 return _additions; 731 } 732 733 int MinorValue::getAccumulatedMultiplications() const { 734 return _accumulatedMult; 735 } 736 737 int MinorValue::getAccumulatedAdditions() const { 738 return _accumulatedSum; 739 } 740 741 void MinorValue::print() const { 742 cout << this->toString(); 743 } 744 745 746 void MinorValue::SetRankingStrategy(const int rankingStrategy) { 747 _RankingStrategy = rankingStrategy; 748 if (_RankingStrategy == 6) { 749 // initialize the random generator with system time 750 srand ( time(NULL) ); 751 } 752 } 753 754 int MinorValue::GetRankingStrategy() { 755 return _RankingStrategy; 756 } 757 758 // this is for generically accessing the rank measure regardless of 759 // which strategy has been set 760 int MinorValue::getUtility () const { 761 switch (this->GetRankingStrategy()) { 762 case 1: return this->rankMeasure1(); 763 case 2: return this->rankMeasure2(); 764 case 3: return this->rankMeasure3(); 765 case 4: return this->rankMeasure4(); 766 case 5: return this->rankMeasure5(); 767 default: return this->rankMeasure1(); 768 } 769 } 770 771 // here are some sensible caching strategies: 772 int MinorValue::rankMeasure1 () const { 773 // number of actually performed multiplications 774 return this->getMultiplications(); 775 } 776 777 int MinorValue::rankMeasure2 () const { 778 // accumulated number of performed multiplications, i.e. all including nested multiplications 779 return this->getAccumulatedMultiplications(); 780 } 781 782 int MinorValue::rankMeasure3 () const { 783 // number of performed multiplications, weighted with the ratio of 784 // not yet performed retrievals over the maximal number of retrievals 785 return this->getMultiplications() * (this->getPotentialRetrievals() - this->getRetrievals()) 786 / this->getPotentialRetrievals(); 787 } 788 789 int MinorValue::rankMeasure4 () const { 790 // number of performed multiplications, 791 // multiplied with the number of not yet performed retrievals 792 return this->getMultiplications() * (this->getPotentialRetrievals() - this->getRetrievals()); 793 } 794 795 int MinorValue::rankMeasure5 () const { 796 // number of not yet performed retrievals; 797 // tends to cache entries longer when they are going to be retrieved more often in the future 798 return this->getPotentialRetrievals() - this->getRetrievals(); 799 } 800 801 int IntMinorValue::getWeight () const { 802 // put measure for size of MinorValue here, i.e. number of monomials in polynomial; 803 // so far, we use the accumulated number of multiplications (i.e., including all nested ones) 804 // to simmulate the size of a polynomial 805 return _accumulatedMult; 806 } 807 808 IntMinorValue::IntMinorValue (const int result, const int multiplications, const int additions, 809 const int accumulatedMultiplications, const int accumulatedAdditions, 810 const int retrievals, const int potentialRetrievals) { 811 _result = result; 812 _multiplications = multiplications; 813 _additions = additions; 814 _accumulatedMult = accumulatedMultiplications; 815 _accumulatedSum = accumulatedAdditions; 816 _potentialRetrievals = potentialRetrievals; 817 _retrievals = retrievals; 818 } 819 820 IntMinorValue::IntMinorValue () { 821 _result = -1; 822 _multiplications = -1; 823 _additions = -1; 824 _accumulatedMult = -1; 825 _accumulatedSum = -1; 826 _potentialRetrievals = -1; 827 _retrievals = -1; 849 /* just to make the compiler happy; 850 this method should never be called */ 851 bool MinorValue::operator<(const MinorValue& mv) const 852 { 853 assert(false); 854 return (this < &mv); /* compare addresses of both objects */ 855 } 856 857 int MinorValue::getRetrievals() const 858 { 859 return _retrievals; 860 } 861 862 void MinorValue::incrementRetrievals() 863 { 864 _retrievals++; 865 } 866 867 int MinorValue::getPotentialRetrievals() const 868 { 869 return _potentialRetrievals; 870 } 871 872 int MinorValue::getMultiplications() const 873 { 874 return _multiplications; 875 } 876 877 int MinorValue::getAdditions() const 878 { 879 return _additions; 880 } 881 882 int MinorValue::getAccumulatedMultiplications() const 883 { 884 return _accumulatedMult; 885 } 886 887 int MinorValue::getAccumulatedAdditions() const 888 { 889 return _accumulatedSum; 890 } 891 892 void MinorValue::print() const 893 { 894 cout << this->toString(); 895 } 896 897 898 void MinorValue::SetRankingStrategy (const int rankingStrategy) 899 { 900 _RankingStrategy = rankingStrategy; 901 if (_RankingStrategy == 6) 902 { 903 /* initialize the random generator with system time */ 904 srand ( time(NULL) ); 905 } 906 } 907 908 int MinorValue::GetRankingStrategy() 909 { 910 return _RankingStrategy; 911 } 912 913 /* this is for generically accessing the rank measure regardless of 914 which strategy has been set */ 915 int MinorValue::getUtility () const 916 { 917 switch (this->GetRankingStrategy()) 918 { 919 case 1: return this->rankMeasure1(); 920 case 2: return this->rankMeasure2(); 921 case 3: return this->rankMeasure3(); 922 case 4: return this->rankMeasure4(); 923 case 5: return this->rankMeasure5(); 924 default: return this->rankMeasure1(); 925 } 926 } 927 928 /* here are some sensible caching strategies: */ 929 int MinorValue::rankMeasure1 () const 930 { 931 /* number of actually performed multiplications */ 932 return this->getMultiplications(); 933 } 934 935 int MinorValue::rankMeasure2 () const 936 { 937 /* accumulated number of performed multiplications, i.e. all including 938 nested multiplications */ 939 return this->getAccumulatedMultiplications(); 940 } 941 942 int MinorValue::rankMeasure3 () const 943 { 944 /* number of performed multiplications, weighted with the ratio of 945 not yet performed retrievals over the maximal number of retrievals */ 946 return this->getMultiplications() 947 * (this->getPotentialRetrievals() 948 - this->getRetrievals()) 949 / this->getPotentialRetrievals(); 950 } 951 952 int MinorValue::rankMeasure4 () const 953 { 954 /* number of performed multiplications, 955 multiplied with the number of not yet performed retrievals */ 956 return this->getMultiplications() 957 * (this->getPotentialRetrievals() 958 - this->getRetrievals()); 959 } 960 961 int MinorValue::rankMeasure5 () const 962 { 963 /* number of not yet performed retrievals; 964 tends to cache entries longer when they are going to be retrieved more 965 often in the future */ 966 return this->getPotentialRetrievals() - this->getRetrievals(); 967 } 968 969 int IntMinorValue::getWeight () const 970 { 971 /* put measure for size of MinorValue here, i.e. number of monomials in 972 polynomial; so far, we use the accumulated number of multiplications 973 (i.e., including all nested ones) to simmulate the size of a polynomial */ 974 return _accumulatedMult; 975 } 976 977 IntMinorValue::IntMinorValue (const int result, const int multiplications, 978 const int additions, 979 const int accumulatedMultiplications, 980 const int accumulatedAdditions, 981 const int retrievals, 982 const int potentialRetrievals) 983 { 984 _result = result; 985 _multiplications = multiplications; 986 _additions = additions; 987 _accumulatedMult = accumulatedMultiplications; 988 _accumulatedSum = accumulatedAdditions; 989 _potentialRetrievals = potentialRetrievals; 990 _retrievals = retrievals; 991 } 992 993 IntMinorValue::IntMinorValue () 994 { 995 _result = -1; 996 _multiplications = -1; 997 _additions = -1; 998 _accumulatedMult = -1; 999 _accumulatedSum = -1; 1000 _potentialRetrievals = -1; 1001 _retrievals = -1; 828 1002 } 829 1003 … … 832 1006 } 833 1007 834 int IntMinorValue::getResult() const { 835 return _result; 836 } 837 838 string IntMinorValue::toString () const { 839 char h[10]; 840 841 // Let's see whether a cache has been used to compute this MinorValue: 842 bool cacheHasBeenUsed = true; 843 if (this->getRetrievals() == -1) cacheHasBeenUsed = false; 844 845 sprintf(h, "%d", this->getResult()); 846 string s = h; 847 s += " [retrievals: "; 848 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; } 849 else s += "/"; 850 s += " (of "; 851 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getPotentialRetrievals()); s += h; } 852 else s += "/"; 853 s += "), *: "; 854 sprintf(h, "%d", this->getMultiplications()); s += h; 855 s += " (accumulated: "; 856 sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h; 857 s += "), +: "; 858 sprintf(h, "%d", this->getAdditions()); s += h; 859 s += " (accumulated: "; 860 sprintf(h, "%d", this->getAccumulatedAdditions()); s += h; 861 s += "), rank: "; 862 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; } 863 else s += "/"; 864 s += "]"; 865 return s; 866 } 867 868 IntMinorValue::IntMinorValue (const IntMinorValue& mv) { 869 _result = mv.getResult(); 870 _retrievals = mv.getRetrievals(); 871 _potentialRetrievals = mv.getPotentialRetrievals(); 872 _multiplications = mv.getMultiplications(); 873 _additions = mv.getAdditions(); 874 _accumulatedMult = mv.getAccumulatedMultiplications(); 875 _accumulatedSum = mv.getAccumulatedAdditions(); 876 } 877 878 PolyMinorValue::PolyMinorValue (const poly result, const int multiplications, const int additions, 879 const int accumulatedMultiplications, const int accumulatedAdditions, 880 const int retrievals, const int potentialRetrievals) { 881 _result = pCopy(result); 882 _multiplications = multiplications; 883 _additions = additions; 884 _accumulatedMult = accumulatedMultiplications; 885 _accumulatedSum = accumulatedAdditions; 886 _potentialRetrievals = potentialRetrievals; 887 _retrievals = retrievals; 888 } 889 890 PolyMinorValue::PolyMinorValue () { 891 _result = NULL; 892 _multiplications = -1; 893 _additions = -1; 894 _accumulatedMult = -1; 895 _accumulatedSum = -1; 896 _potentialRetrievals = -1; 897 _retrievals = -1; 1008 int IntMinorValue::getResult() const 1009 { 1010 return _result; 1011 } 1012 1013 string IntMinorValue::toString () const 1014 { 1015 char h[10]; 1016 1017 /* Let's see whether a cache has been used to compute this MinorValue: */ 1018 bool cacheHasBeenUsed = true; 1019 if (this->getRetrievals() == -1) cacheHasBeenUsed = false; 1020 1021 sprintf(h, "%d", this->getResult()); 1022 string s = h; 1023 s += " [retrievals: "; 1024 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; } 1025 else s += "/"; 1026 s += " (of "; 1027 if (cacheHasBeenUsed) 1028 { 1029 sprintf(h, "%d", this->getPotentialRetrievals()); 1030 s += h; 1031 } 1032 else s += "/"; 1033 s += "), *: "; 1034 sprintf(h, "%d", this->getMultiplications()); s += h; 1035 s += " (accumulated: "; 1036 sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h; 1037 s += "), +: "; 1038 sprintf(h, "%d", this->getAdditions()); s += h; 1039 s += " (accumulated: "; 1040 sprintf(h, "%d", this->getAccumulatedAdditions()); s += h; 1041 s += "), rank: "; 1042 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; } 1043 else s += "/"; 1044 s += "]"; 1045 return s; 1046 } 1047 1048 IntMinorValue::IntMinorValue (const IntMinorValue& mv) 1049 { 1050 _result = mv.getResult(); 1051 _retrievals = mv.getRetrievals(); 1052 _potentialRetrievals = mv.getPotentialRetrievals(); 1053 _multiplications = mv.getMultiplications(); 1054 _additions = mv.getAdditions(); 1055 _accumulatedMult = mv.getAccumulatedMultiplications(); 1056 _accumulatedSum = mv.getAccumulatedAdditions(); 1057 } 1058 1059 PolyMinorValue::PolyMinorValue (const poly result, const int multiplications, 1060 const int additions, 1061 const int accumulatedMultiplications, 1062 const int accumulatedAdditions, 1063 const int retrievals, 1064 const int potentialRetrievals) 1065 { 1066 _result = pCopy(result); 1067 _multiplications = multiplications; 1068 _additions = additions; 1069 _accumulatedMult = accumulatedMultiplications; 1070 _accumulatedSum = accumulatedAdditions; 1071 _potentialRetrievals = potentialRetrievals; 1072 _retrievals = retrievals; 1073 } 1074 1075 PolyMinorValue::PolyMinorValue () 1076 { 1077 _result = NULL; 1078 _multiplications = -1; 1079 _additions = -1; 1080 _accumulatedMult = -1; 1081 _accumulatedSum = -1; 1082 _potentialRetrievals = -1; 1083 _retrievals = -1; 898 1084 } 899 1085 900 1086 PolyMinorValue::~PolyMinorValue() 901 1087 { 902 p_Delete(&_result, currRing); 903 } 904 905 poly PolyMinorValue::getResult() const { 906 return _result; 907 } 908 909 int PolyMinorValue::getWeight () const { 910 // put measure for size of PolyMinorValue here, e.g. the number of monomials 911 // in the cached polynomial 912 return pLength(_result); // the number of monomials in the polynomial 913 } 914 915 string PolyMinorValue::toString () const { 916 char h[20]; 917 918 // Let's see whether a cache has been used to compute this MinorValue: 919 bool cacheHasBeenUsed = true; 920 if (this->getRetrievals() == -1) cacheHasBeenUsed = false; 921 922 string s = pString(_result); 923 s += " [retrievals: "; 924 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; } 925 else s += "/"; 926 s += " (of "; 927 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getPotentialRetrievals()); s += h; } 928 else s += "/"; 929 s += "), *: "; 930 sprintf(h, "%d", this->getMultiplications()); s += h; 931 s += " (accumulated: "; 932 sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h; 933 s += "), +: "; 934 sprintf(h, "%d", this->getAdditions()); s += h; 935 s += " (accumulated: "; 936 sprintf(h, "%d", this->getAccumulatedAdditions()); s += h; 937 s += "), rank: "; 938 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; } 939 else s += "/"; 940 s += "]"; 941 return s; 942 } 943 944 PolyMinorValue::PolyMinorValue (const PolyMinorValue& mv) { 945 _result = pCopy(mv.getResult()); 946 _retrievals = mv.getRetrievals(); 947 _potentialRetrievals = mv.getPotentialRetrievals(); 948 _multiplications = mv.getMultiplications(); 949 _additions = mv.getAdditions(); 950 _accumulatedMult = mv.getAccumulatedMultiplications(); 951 _accumulatedSum = mv.getAccumulatedAdditions(); 1088 p_Delete(&_result, currRing); 1089 } 1090 1091 poly PolyMinorValue::getResult() const 1092 { 1093 return _result; 1094 } 1095 1096 int PolyMinorValue::getWeight () const 1097 { 1098 /* put measure for size of PolyMinorValue here, e.g. the number of monomials 1099 in the cached polynomial */ 1100 return pLength(_result); // the number of monomials in the polynomial 1101 } 1102 1103 string PolyMinorValue::toString () const 1104 { 1105 char h[20]; 1106 1107 /* Let's see whether a cache has been used to compute this MinorValue: */ 1108 bool cacheHasBeenUsed = true; 1109 if (this->getRetrievals() == -1) cacheHasBeenUsed = false; 1110 1111 string s = pString(_result); 1112 s += " [retrievals: "; 1113 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getRetrievals()); s += h; } 1114 else s += "/"; 1115 s += " (of "; 1116 if (cacheHasBeenUsed) 1117 { 1118 sprintf(h, "%d", this->getPotentialRetrievals()); 1119 s += h; 1120 } 1121 else s += "/"; 1122 s += "), *: "; 1123 sprintf(h, "%d", this->getMultiplications()); s += h; 1124 s += " (accumulated: "; 1125 sprintf(h, "%d", this->getAccumulatedMultiplications()); s += h; 1126 s += "), +: "; 1127 sprintf(h, "%d", this->getAdditions()); s += h; 1128 s += " (accumulated: "; 1129 sprintf(h, "%d", this->getAccumulatedAdditions()); s += h; 1130 s += "), rank: "; 1131 if (cacheHasBeenUsed) { sprintf(h, "%d", this->getUtility()); s += h; } 1132 else s += "/"; 1133 s += "]"; 1134 return s; 1135 } 1136 1137 PolyMinorValue::PolyMinorValue (const PolyMinorValue& mv) 1138 { 1139 _result = pCopy(mv.getResult()); 1140 _retrievals = mv.getRetrievals(); 1141 _potentialRetrievals = mv.getPotentialRetrievals(); 1142 _multiplications = mv.getMultiplications(); 1143 _additions = mv.getAdditions(); 1144 _accumulatedMult = mv.getAccumulatedMultiplications(); 1145 _accumulatedSum = mv.getAccumulatedAdditions(); 952 1146 } 953 1147 954 1148 void PolyMinorValue::operator= (const PolyMinorValue& mv) 955 1149 { 956 957 958 959 960 961 962 963 964 } 1150 if (_result != mv.getResult()) pDelete(&_result); 1151 _result = pCopy(mv.getResult()); 1152 _retrievals = mv.getRetrievals(); 1153 _potentialRetrievals = mv.getPotentialRetrievals(); 1154 _multiplications = mv.getMultiplications(); 1155 _additions = mv.getAdditions(); 1156 _accumulatedMult = mv.getAccumulatedMultiplications(); 1157 _accumulatedSum = mv.getAccumulatedAdditions(); 1158 }
Note: See TracChangeset
for help on using the changeset viewer.