Public Member Functions | Private Member Functions | Private Attributes | Friends
MinorKey Class Reference

Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache. More...

#include <Minor.h>

Public Member Functions

 MinorKey (const int lengthOfRowArray=0, const unsigned int *const rowKey=0, const int lengthOfColumnArray=0, const unsigned int *const columnKey=0)
 A constructor for class MinorKey. More...
 
void set (const int lengthOfRowArray, const unsigned int *rowKey, const int lengthOfColumnArray, const unsigned int *columnKey)
 A setter method for class MinorKey. More...
 
 MinorKey (const MinorKey &mk)
 A copy constructor. More...
 
 ~MinorKey ()
 A destructor for deleting an instance. More...
 
MinorKeyoperator= (const MinorKey &)
 just to make the compiler happy More...
 
bool operator== (const MinorKey &) const
 just to make the compiler happy More...
 
bool operator< (const MinorKey &) const
 just to make the compiler happy More...
 
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. More...
 
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. More...
 
int getRelativeRowIndex (const int i) const
 A method for retrieving the (0-based) relative index of the i-th row in this MinorKey. More...
 
int getRelativeColumnIndex (const int i) const
 A method for retrieving the (0-based) relative index of the i-th column in this MinorKey. More...
 
void getAbsoluteRowIndices (int *const target) const
 A method for retrieving the 0-based indices of all rows encoded in this MinorKey. More...
 
void getAbsoluteColumnIndices (int *const target) const
 A method for retrieving the 0-based indices of all columns encoded in this MinorKey. More...
 
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 MinorKey. More...
 
int compare (const MinorKey &mk) const
 A comparator for two instances of MinorKey. More...
 
void selectFirstRows (const int k, const MinorKey &mk)
 This method redefines the set of rows represented by this MinorKey. More...
 
bool selectNextRows (const int k, const MinorKey &mk)
 This method redefines the set of rows represented by this MinorKey. More...
 
void selectFirstColumns (const int k, const MinorKey &mk)
 This method redefines the set of columns represented by this MinorKey. More...
 
bool selectNextColumns (const int k, const MinorKey &mk)
 This method redefines the set of columns represented by this MinorKey. More...
 
std::string toString () const
 A method for providing a printable version of the represented MinorKey. More...
 

Private Member Functions

unsigned int getRowKey (const int blockIndex) const
 Inlined accessor of blockIndex-th element of _rowKey. More...
 
unsigned int getColumnKey (const int blockIndex) const
 Accessor of blockIndex-th element of _columnKey. More...
 
void setRowKey (const int blockIndex, const unsigned int rowKey)
 A method for setting the blockIndex-th element of _rowKey. More...
 
void setColumnKey (const int blockIndex, const unsigned int columnKey)
 A method for setting the blockIndex-th element of _columnKey. More...
 
int getNumberOfRowBlocks () const
 Accessor of _numberOfRowBlocks. More...
 
int getNumberOfColumnBlocks () const
 Accessor of _numberOfColumnBlocks. More...
 
void reset ()
 A method for deleting all entries of _rowKey and _columnKey. More...
 
int getSetBits (const int a) const
 A method for counting the number of set bits. More...
 

Private Attributes

unsigned int * _rowKey
 a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-defined matrix shall belong to the minor of interest; for i < j, _rowKey[i] holds lower bits than _rowKey[j] More...
 
unsigned int * _columnKey
 a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-defined matrix shall belong to the minor of interest; for i < j, _columnKey[i] holds lower bits than _columnKey[j] More...
 
int _numberOfRowBlocks
 the number of ints (i.e. More...
 
int _numberOfColumnBlocks
 the number of ints (i.e. More...
 

Friends

class MinorProcessor
 For letting MinorProcessor see the private methods of this class. More...
 

Detailed Description

Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache.

As such, it is a realization of the template class KeyClass which is used in the declaration of class Cache. Following the documentation of class Cache, we need to implement at least the methods:
bool MinorKey::operator< (const MinorKey& key),
bool MinorKey::operator== (const MinorKey& key),
MinorKey uses two private arrays of ints _rowKey and _columnKey to encode rows and columns of a pre-defined matrix. Semantically, the row indices and column indices form the key for caching the value of the corresponding minor.
More concretely, let us assume that the pre-defined matrix has 32*R+r, r<32, rows and 32*C+c, c<32, columns. All row indices can then be captured using R+1 ints, since an int is a 32-bit-number (regardless of the platform). The analog holds for the columns. Consequently, each instance of MinorKey encodes the sets of rows and columns which shall belong to the minor of interest (and which shall not).
Example: The _rowKey with _rowKey[1] = 0...011 and _rowKey[0] = 0...01101 encodes the rows with indices 33, 32, 3, 2, and 0.

Author
Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch

Definition at line 39 of file Minor.h.

Constructor & Destructor Documentation

MinorKey::MinorKey ( const int  lengthOfRowArray = 0,
const unsigned int *const  rowKey = 0,
const int  lengthOfColumnArray = 0,
const unsigned int *const  columnKey = 0 
)

A constructor for class MinorKey.

The ints given in the array rowKey encode all rows which shall belong to the minor. Each array entry encodes 32 rows, e.g. the i-th array entry 0...01101 encodes the rows with absolute matrix row indices 3+i*32, 2+i*32, and 0+i*32. Analog for columns.

Parameters
lengthOfRowArraythe length of the array rowKey
rowKeya pointer to an array of ints encoding the set of rows of the minor
lengthOfColumnArraythe length of the array columnKey
columnKeya pointer to an array of ints encoding the set of
  • columns of the minor

Definition at line 86 of file Minor.cc.

90 {
91  _numberOfRowBlocks = lengthOfRowArray;
92  _numberOfColumnBlocks = lengthOfColumnArray;
93 
94  /* allocate memory for new entries in _rowKey and _columnKey */
95  _rowKey = new unsigned int[_numberOfRowBlocks];
96  _columnKey = new unsigned int[_numberOfColumnBlocks];
97 
98  /* copying values from parameter arrays to private arrays */
99  for (int r = 0; r < _numberOfRowBlocks; r++)
100  _rowKey[r] = rowKey[r];
101 
102  for (int c = 0; c < _numberOfColumnBlocks; c++)
103  _columnKey[c] = columnKey[c];
104 }
const ring r
Definition: syzextra.cc:208
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
MinorKey::MinorKey ( const MinorKey mk)

A copy constructor.

This method overrides the shallow copy constructor by a self-written deep copy version.

Parameters
mkthe MinorKey to be deep copied

Definition at line 23 of file Minor.cc.

24 {
27 
28  /* allocate memory for new entries in _rowKey and _columnKey */
29  _rowKey = new unsigned int[_numberOfRowBlocks];
30  _columnKey = new unsigned int[_numberOfColumnBlocks];
31 
32  /* copying values from parameter arrays to private arrays */
33  for (int r = 0; r < _numberOfRowBlocks; r++)
34  _rowKey[r] = mk.getRowKey(r);
35  for (int c = 0; c < _numberOfColumnBlocks; c++)
36  _columnKey[c] = mk.getColumnKey(c);
37 }
const ring r
Definition: syzextra.cc:208
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
MinorKey::~MinorKey ( )

A destructor for deleting an instance.

Definition at line 106 of file Minor.cc.

107 {
108  _numberOfRowBlocks = 0;
110  delete [] _rowKey;
111  delete [] _columnKey;
112  _rowKey = 0;
113  _columnKey = 0;
114 }
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48

Member Function Documentation

int MinorKey::compare ( const MinorKey mk) const

A comparator for two instances of MinorKey.

The ordering induced by this implementation determines the ordering of all (key –> value) pairs in a cache that uses MinorKey as KeyClass.

Parameters
mka second MinorKey to be compared with this instance
Returns
-1 iff this instance is smaller than mk; 0 for equality; +1 otherwise
See also
MinorKey::operator== (const MinorKey&) const

Definition at line 414 of file Minor.cc.

415 {
416  /* compare by rowKeys first; in case of equality, use columnKeys */
417  if (this->getNumberOfRowBlocks() < that.getNumberOfRowBlocks())
418  return -1;
419  if (this->getNumberOfRowBlocks() > that.getNumberOfRowBlocks())
420  return 1;
421  /* Here, numbers of rows are equal. */
422  for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--)
423  {
424  if (this->getRowKey(r) < that.getRowKey(r)) return -1;
425  if (this->getRowKey(r) > that.getRowKey(r)) return 1;
426  }
427  /* Here, this and that encode ecaxtly the same sets of rows.
428  Now, we take a look at the columns. */
429  if (this->getNumberOfColumnBlocks() < that.getNumberOfColumnBlocks())
430  return -1;
431  if (this->getNumberOfColumnBlocks() > that.getNumberOfColumnBlocks())
432  return 1;
433  /* Here, numbers of columns are equal. */
434  for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
435  {
436  if (this->getColumnKey(c) < that.getColumnKey(c)) return -1;
437  if (this->getColumnKey(c) > that.getColumnKey(c)) return 1;
438  }
439  /* Here, this and that encode exactly the same sets of rows and columns. */
440  return 0;
441 }
const ring r
Definition: syzextra.cc:208
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
int MinorKey::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.

Lower values for i result in lower absolute column indices.

Example:
Applied to the column pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted from the right, i.e. 7.
Assertion
The method assumes that there are at least i columns encoded in the given MinorKey.
Parameters
ithe relative index of the column, as encoded in this
Returns
(0-based) absolute column index of the i-th row in this

Definition at line 153 of file Minor.cc.

154 {
155  /* This method is to return the absolute (0-based) index of the i-th
156  column encoded in \a this.
157  Example: bit-pattern of columns: "10010001101", i = 3:
158  This should yield the 0-based absolute index of the 3-rd bit
159  (counted from the right), i.e. 7. */
160 
161  int matchedBits = -1; /* counter for matched bits; this needs to reach i,
162  then we're done */
163  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
164  {
165  /* start with lowest bits, i.e. in block No. 0 */
166  /* the bits in this block of 32 bits: */
167  unsigned int blockBits = getColumnKey(block);
168  unsigned int shiftedBit = 1;
169  int exponent = 0;
170  /* The invariant "shiftedBit = 2^exponent" will hold throughout the
171  entire while loop. */
172  while (exponent < 32)
173  {
174  if (shiftedBit & blockBits) matchedBits++;
175  if (matchedBits == i) return exponent + (32 * block);
176  shiftedBit = shiftedBit << 1;
177  exponent++;
178  }
179  }
180  /* We should never reach this line of code. */
181  assume(false);
182  return -1;
183 }
#define block
Definition: scanner.cc:662
#define assume(x)
Definition: mod2.h:405
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int i
Definition: cfEzgcd.cc:123
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
void MinorKey::getAbsoluteColumnIndices ( int *const  target) const

A method for retrieving the 0-based indices of all columns encoded in this MinorKey.

The user of this method needs to know the number of columns in this, in order to know which indices in target[k] will be valid.

Example:
The bit pattern 0...01101 will give rise to the settings target[0] = 0, target[1] = 2, target[2] = 3, and the user needs to know in advance that there are three columns in this MinorKey.
Assertion
The method assumes that target has enough positions for all columns encoded in this MinorKey.
Parameters
targeta pointer to some array of ints that is to be filled with the requested indices

Definition at line 206 of file Minor.cc.

207 {
208  int i = 0; /* index for filling the target array */
209  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
210  {
211  /* start with lowest bits, i.e. in block No. 0 */
212  /* the bits in this block of 32 bits: */
213  unsigned int blockBits = getColumnKey(block);
214  unsigned int shiftedBit = 1;
215  int exponent = 0;
216  /* The invariant "shiftedBit = 2^exponent" will hold throughout the
217  entire while loop. */
218  while (exponent < 32)
219  {
220  if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
221  shiftedBit = shiftedBit << 1;
222  exponent++;
223  }
224  }
225 }
#define block
Definition: scanner.cc:662
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int i
Definition: cfEzgcd.cc:123
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
int MinorKey::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.

Lower values for i result in lower absolute row indices.

Example:
Applied to the row pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted from the right, i.e. 7.
Assertion
The method assumes that there are at least i rows encoded in the given MinorKey.
Parameters
ithe relative index of the row, as encoded in this
Returns
(0-based) absolute row index of the i-th row in this

Definition at line 121 of file Minor.cc.

122 {
123  /* This method is to return the absolute (0-based) index of the i-th
124  row encoded in \a this.
125  Example: bit-pattern of rows: "10010001101", i = 3:
126  This should yield the 0-based absolute index of the 3-rd bit
127  (counted from the right), i.e. 7. */
128 
129  int matchedBits = -1; /* counter for matched bits;
130  this needs to reach i, then we're done */
131  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
132  {
133  /* start with lowest bits, i.e. in block No. 0 */
134  /* the bits in this block of 32 bits: */
135  unsigned int blockBits = getRowKey(block);
136  unsigned int shiftedBit = 1;
137  int exponent = 0;
138  /* The invariant "shiftedBit = 2^exponent" will hold throughout the
139  entire while loop. */
140  while (exponent < 32)
141  {
142  if (shiftedBit & blockBits) matchedBits++;
143  if (matchedBits == i) return exponent + (32 * block);
144  shiftedBit = shiftedBit << 1;
145  exponent++;
146  }
147  }
148  /* We should never reach this line of code. */
149  assume(false);
150  return -1;
151 }
#define block
Definition: scanner.cc:662
#define assume(x)
Definition: mod2.h:405
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
int i
Definition: cfEzgcd.cc:123
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
void MinorKey::getAbsoluteRowIndices ( int *const  target) const

A method for retrieving the 0-based indices of all rows encoded in this MinorKey.

The user of this method needs to know the number of rows in this, in order to know which indices in target[k] will be valid.

Example:
The bit pattern 0...01101 will give rise to the settings target[0] = 0, target[1] = 2, target[2] = 3, and the user needs to know in advance that there are three rows in this MinorKey.
Assertion
The method assumes that target has enough positions for all rows encoded in this MinorKey.
Parameters
targeta pointer to some array of ints that is to be filled with the requested indices

Definition at line 185 of file Minor.cc.

186 {
187  int i = 0; /* index for filling the target array */
188  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
189  {
190  /* start with lowest bits, i.e. in block No. 0 */
191  /* the bits in this block of 32 bits: */
192  unsigned int blockBits = getRowKey(block);
193  unsigned int shiftedBit = 1;
194  int exponent = 0;
195  /* The invariant "shiftedBit = 2^exponent" will hold throughout the
196  entire while loop. */
197  while (exponent < 32)
198  {
199  if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
200  shiftedBit = shiftedBit << 1;
201  exponent++;
202  }
203  }
204 }
#define block
Definition: scanner.cc:662
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
int i
Definition: cfEzgcd.cc:123
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int MinorKey::getColumnKey ( const int  blockIndex) const
private

Accessor of blockIndex-th element of _columnKey.

Parameters
blockIndexthe index of the int to be retrieved
Returns
an entry of _columnKey

Definition at line 296 of file Minor.cc.

297 {
298  return _columnKey[blockIndex];
299 }
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int MinorKey::getNumberOfColumnBlocks ( ) const
private

Accessor of _numberOfColumnBlocks.

Returns
the number of 32-bit-blocks needed to encode all columns of the minor as a sequence of bits

Definition at line 306 of file Minor.cc.

307 {
308  return _numberOfColumnBlocks;
309 }
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int MinorKey::getNumberOfRowBlocks ( ) const
private

Accessor of _numberOfRowBlocks.

Returns
the number of 32-bit-blocks needed to encode all rows of the minor as a sequence of bits

Definition at line 301 of file Minor.cc.

302 {
303  return _numberOfRowBlocks;
304 }
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
int MinorKey::getRelativeColumnIndex ( const int  i) const

A method for retrieving the (0-based) relative index of the i-th column in this MinorKey.

Lower values for i result in lower relative column indices. Note that the absolute index i is 0-based, too.

Example:
Applied to the column pattern 10010001101 and i = 7, we get the relative 0-based position of the bit representing the absolute index 7, i.e. 3.
Assertion
The method assumes that the bit which corresponds to the absolute index i is actually set.
Parameters
ithe absolute 0-based index of a column encoded in this
Returns
(0-based) relative column index corresponding to i

Definition at line 259 of file Minor.cc.

260 {
261  /* This method is to return the relative (0-based) index
262  of the column with absolute index \c i.
263  Example: bit-pattern of columns: "10010001101", i = 7:
264  This should yield the 0-based relative index of the bit
265  corresponding to column no. 7, i.e. 3. */
266 
267  int matchedBits = -1; /* counter for matched bits; this is going
268  to contain our return value */
269  for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
270  {
271  /* start with lowest bits, i.e. in block No. 0 */
272  /* the bits in this block of 32 bits: */
273  unsigned int blockBits = getColumnKey(block);
274  unsigned int shiftedBit = 1;
275  int exponent = 0;
276  /* The invariant "shiftedBit = 2^exponent" will hold
277  throughout the entire while loop. */
278  while (exponent < 32)
279  {
280  if (shiftedBit & blockBits) matchedBits++;
281  if (exponent + (32 * block) == i) return matchedBits;
282  shiftedBit = shiftedBit << 1;
283  exponent++;
284  }
285  }
286  /* We should never reach this line of code. */
287  assume(false);
288  return -1;
289 }
#define block
Definition: scanner.cc:662
#define assume(x)
Definition: mod2.h:405
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int i
Definition: cfEzgcd.cc:123
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
int MinorKey::getRelativeRowIndex ( const int  i) const

A method for retrieving the (0-based) relative index of the i-th row in this MinorKey.

Lower values for i result in lower relative row indices. Note that the absolute index i is 0-based, too.

Example:
Applied to the row pattern 10010001101 and i = 7, we get the relative 0-based position of the bit representing the absolute index 7, i.e. 3.
Assertion
The method assumes that the bit which corresponds to the absolute index i is actually set.
Parameters
ithe absolute 0-based index of a row encoded in this
Returns
(0-based) relative row index corresponding to i

Definition at line 227 of file Minor.cc.

228 {
229  /* This method is to return the relative (0-based) index of the row
230  with absolute index \c i.
231  Example: bit-pattern of rows: "10010001101", i = 7:
232  This should yield the 0-based relative index of the bit
233  corresponding to row no. 7, i.e. 3. */
234 
235  int matchedBits = -1; /* counter for matched bits; this is going to
236  contain our return value */
237  for (int block = 0; block < getNumberOfRowBlocks(); block ++)
238  {
239  /* start with lowest bits, i.e. in block No. 0 */
240  /* the bits in this block of 32 bits: */
241  unsigned int blockBits = getRowKey(block);
242  unsigned int shiftedBit = 1;
243  int exponent = 0;
244  /* The invariant "shiftedBit = 2^exponent" will hold throughout the
245  entire while loop. */
246  while (exponent < 32)
247  {
248  if (shiftedBit & blockBits) matchedBits++;
249  if (exponent + (32 * block) == i) return matchedBits;
250  shiftedBit = shiftedBit << 1;
251  exponent++;
252  }
253  }
254  /* We should never reach this line of code. */
255  assume(false);
256  return -1;
257 }
#define block
Definition: scanner.cc:662
#define assume(x)
Definition: mod2.h:405
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
int i
Definition: cfEzgcd.cc:123
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int MinorKey::getRowKey ( const int  blockIndex) const
private

Inlined accessor of blockIndex-th element of _rowKey.

Parameters
blockIndexthe index of the int to be retrieved
Returns
an entry of _rowKey

Definition at line 291 of file Minor.cc.

292 {
293  return _rowKey[blockIndex];
294 }
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
int MinorKey::getSetBits ( const int  a) const
private

A method for counting the number of set bits.

For a == 1, the number of set bits in _rowKey will be counted; for a == 2 in _columnKey. This method will only be called in the debug version.

Parameters
afor controlling whether to count in _rowKey or _columnKey
Returns
the number of set bits either in _rowKey or _columnKey

Definition at line 312 of file Minor.cc.

313 {
314  int b = 0;
315  if (a == 1)
316  { /* rows */
317  for (int i = 0; i < _numberOfRowBlocks; i++)
318  {
319  unsigned int m = _rowKey[i];
320  unsigned int k = 1;
321  for (int j = 0; j < 32; j++)
322  {
323  /* k = 2^j */
324  if (m & k) b++;
325  k = k << 1;
326  }
327  }
328  }
329  else
330  { /* columns */
331  for (int i = 0; i < _numberOfColumnBlocks; i++)
332  {
333  unsigned int m = _columnKey[i];
334  unsigned int k = 1;
335  for (int j = 0; j < 32; j++)
336  {
337  /* k = 2^j */
338  if (m & k) b++;
339  k = k << 1;
340  }
341  }
342  }
343  return b;
344 }
const poly a
Definition: syzextra.cc:212
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
const poly b
Definition: syzextra.cc:213
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
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 MinorKey.

Assertion
The method assumes that the row with absolute index absoluteEraseRowIndex (counted from lower bits to higher bits) and the column with absolute index absoluteEraseColumnIndex are actually set in mk.
Parameters
absoluteEraseRowIndexthe 0-based absolute index of a row in mk
absoluteEraseColumnIndexthe 0-based absolute index of a column in mk
Returns
the MinorKey when omitting the specified row and column

Definition at line 347 of file Minor.cc.

349 {
350  int rowBlock = absoluteEraseRowIndex / 32;
351  int exponent = absoluteEraseRowIndex % 32;
352  unsigned int newRowBits = getRowKey(rowBlock) - (1 << exponent);
353  int highestRowBlock = getNumberOfRowBlocks() - 1;
354  /* highestRowBlock will finally contain the highest block index with
355  non-zero bit pattern */
356  if ((newRowBits == 0) && (rowBlock == highestRowBlock))
357  {
358  /* we have thus nullified the highest block;
359  we can now forget about the highest block... */
360  highestRowBlock -= 1;
361  while (getRowKey(highestRowBlock) == 0) /* ...and maybe even some more
362  zero-blocks */
363  highestRowBlock -= 1;
364  }
365  /* highestRowBlock now contains the highest row block index with non-zero
366  bit pattern */
367 
368  int columnBlock = absoluteEraseColumnIndex / 32;
369  exponent = absoluteEraseColumnIndex % 32;
370  unsigned int newColumnBits = getColumnKey(columnBlock) - (1 << exponent);
371  int highestColumnBlock = getNumberOfColumnBlocks() - 1;
372  /* highestColumnBlock will finally contain the highest block index with
373  non-zero bit pattern */
374  if ((newColumnBits == 0) && (columnBlock == highestColumnBlock))
375  {
376  /* we have thus nullified the highest block;
377  we can now forget about the highest block... */
378  highestColumnBlock -= 1;
379  while (getColumnKey(highestColumnBlock) == 0) /* ...and maybe even some
380  more zero-blocks */
381  highestColumnBlock -= 1;
382  }
383  /* highestColumnBlock now contains the highest column block index with
384  non-zero bit pattern */
385 
386  MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1,
387  _columnKey);
388  /* This is just a copy with maybe some leading bit blocks omitted. We still
389  need to re-define the row block at index 'rowBlock' and the column block
390  at index 'columnBlock': */
391  if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1))
392  result.setRowKey(rowBlock, newRowBits);
393  if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
394  result.setColumnKey(columnBlock, newColumnBits);
395 
396  /* let's check that the number of selected rows and columns are equal;
397  (this check is only performed in the debug version) */
398  assume(result.getSetBits(1) == result.getSetBits(2));
399 
400  return result;
401 }
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
#define assume(x)
Definition: mod2.h:405
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
Class MinorKey can be used for representing keys in a cache for sub-determinantes; see class Cache...
Definition: Minor.h:39
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
return result
Definition: facAbsBiFact.cc:76
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
bool MinorKey::operator< ( const MinorKey mk) const

just to make the compiler happy

Definition at line 453 of file Minor.cc.

454 {
455  assume(false);
456  return this->compare(mk) == -1;
457 }
#define assume(x)
Definition: mod2.h:405
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:414
MinorKey & MinorKey::operator= ( const MinorKey mk)

just to make the compiler happy

Definition at line 39 of file Minor.cc.

40 {
41  if (_numberOfRowBlocks != 0) delete [] _rowKey;
42  if (_numberOfColumnBlocks != 0) delete [] _columnKey;
45  _rowKey = 0;
46  _columnKey = 0;
47 
50 
51  /* allocate memory for new entries in _rowKey and _columnKey */
52  _rowKey = new unsigned int[_numberOfRowBlocks];
53  _columnKey = new unsigned int[_numberOfColumnBlocks];
54 
55  /* copying values from parameter arrays to private arrays */
56  for (int r = 0; r < _numberOfRowBlocks; r++)
57  _rowKey[r] = mk.getRowKey(r);
58  for (int c = 0; c < _numberOfColumnBlocks; c++)
59  _columnKey[c] = mk.getColumnKey(c);
60 
61  return *this;
62 }
const ring r
Definition: syzextra.cc:208
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
bool MinorKey::operator== ( const MinorKey mk) const

just to make the compiler happy

Definition at line 445 of file Minor.cc.

446 {
447  assume(false);
448  return this->compare(mk) == 0;
449 }
#define assume(x)
Definition: mod2.h:405
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:414
void MinorKey::reset ( )
private

A method for deleting all entries of _rowKey and _columnKey.

Definition at line 13 of file Minor.cc.

14 {
17  delete [] _rowKey;
18  delete [] _columnKey;
19  _rowKey = 0;
20  _columnKey = 0;
21 }
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
void MinorKey::selectFirstColumns ( const int  k,
const MinorKey mk 
)

This method redefines the set of columns represented by this MinorKey.

After the method, the defined set of columns coincides with the lowest k columns of mk. (Here, lowest means w.r.t. indices.)
Note that the method modifies the given instance of MinorKey.

Assertion
It is assumed that mk represents at least k columns.
Parameters
kthe number of columns
mkthe MinorKey from which to choose the lowest k columns
See also
MinorKey::selectNextColumns (const int k, const MinorKey& mk)

Definition at line 499 of file Minor.cc.

500 {
501  int hitBits = 0; /* the number of bits we have hit; in the end, this
502  has to be equal to k, the dimension of the minor */
503  int blockIndex = -1; /* the index of the current int in mk */
504  unsigned int highestInt = 0; /* the new highest block of this MinorKey */
505  /* We determine which ints of mk we can copy. Their indices will be
506  0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
507  int (which may be only a portion of the corresponding int in mk.
508  We loop until hitBits = k: */
509  while (hitBits < k)
510  {
511  blockIndex++;
512  highestInt = 0;
513  unsigned int currentInt = mk.getColumnKey(blockIndex);
514  unsigned int shiftedBit = 1;
515  int exponent = 0;
516  /* invariant in the loop: shiftedBit = 2^exponent */
517  while (exponent < 32 && hitBits < k)
518  {
519  if (shiftedBit & currentInt)
520  {
521  highestInt += shiftedBit;
522  hitBits++;
523  }
524  shiftedBit = shiftedBit << 1;
525  exponent++;
526  }
527  }
528  /* free old memory */
529  delete [] _columnKey; _columnKey = 0;
530  _numberOfColumnBlocks = blockIndex + 1;
531  /* allocate memory for new entries in _columnKey; */
532  _columnKey = new unsigned int[_numberOfColumnBlocks];
533  /* copying values from mk to this MinorKey */
534  for (int c = 0; c < blockIndex; c++)
535  _columnKey[c] = mk.getColumnKey(c);
536  _columnKey[blockIndex] = highestInt;
537 }
int k
Definition: cfEzgcd.cc:93
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
void MinorKey::selectFirstRows ( const int  k,
const MinorKey mk 
)

This method redefines the set of rows represented by this MinorKey.

After the method, the defined set of rows coincides with the lowest k rows of mk. (Here, lowest means w.r.t. indices.)
Note that the method modifies the given instance of MinorKey.

Assertion
It is assumed that mk represents at least k rows.
Parameters
kthe number of rows
mkthe MinorKey from which to choose the lowest k rows
See also
MinorKey::selectNextRows (const int k, const MinorKey& mk)

Definition at line 459 of file Minor.cc.

460 {
461  int hitBits = 0; /* the number of bits we have hit; in the end, this
462  has to be equal to k, the dimension of the minor */
463  int blockIndex = -1; /* the index of the current int in mk */
464  unsigned int highestInt = 0; /* the new highest block of this MinorKey */
465  /* We determine which ints of mk we can copy. Their indices will be
466  0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
467  int (which may be only a portion of the corresponding int in mk.
468  We loop until hitBits = k: */
469  while (hitBits < k)
470  {
471  blockIndex++;
472  highestInt = 0;
473  unsigned int currentInt = mk.getRowKey(blockIndex);
474  unsigned int shiftedBit = 1;
475  int exponent = 0;
476  /* invariant in the loop: shiftedBit = 2^exponent */
477  while (exponent < 32 && hitBits < k)
478  {
479  if (shiftedBit & currentInt)
480  {
481  highestInt += shiftedBit;
482  hitBits++;
483  }
484  shiftedBit = shiftedBit << 1;
485  exponent++;
486  }
487  }
488  /* free old memory */
489  delete [] _rowKey; _rowKey = 0;
490  _numberOfRowBlocks = blockIndex + 1;
491  /* allocate memory for new entries in _rowKey; */
492  _rowKey = new unsigned int[_numberOfRowBlocks];
493  /* copying values from mk to this MinorKey */
494  for (int r = 0; r < blockIndex; r++)
495  _rowKey[r] = mk.getRowKey(r);
496  _rowKey[blockIndex] = highestInt;
497 }
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
bool MinorKey::selectNextColumns ( const int  k,
const MinorKey mk 
)

This method redefines the set of columns represented by this MinorKey.

Both the old and the new set of k columns are subsets of the columns represented by mk. After the method, the defined set of columns is the next sensible choice of k columns of mk. (Here, next means the next w.r.t. the increasing index ordering on multi-indices of natural numbers.)
Note that the method modifies the given instance of MinorKey.

Assertion
It is assumed that mk represents at least k columns. Furthermore, the method assumes that the old set of columns represented by this is also a subset of the columns given by mk.
Parameters
kthe number of columns
mkthe MinorKey from which to choose the lowest k columns
Returns
true iff there is a next choice of k columns
See also
MinorKey::selectFirstColumns (const int k, const MinorKey& mk)

Definition at line 670 of file Minor.cc.

671 {
672  /* We need to compute the set of k columns which must all be contained in mk.
673  AND: This set must be the least possible of this kind which is larger
674  than the currently encoded set of columns. (Here, '<' is w.r.t. to
675  the natural ordering on multi-indices.
676  Example: mk encodes the columns according to the bit pattern 11010111,
677  k = 3, this MinorKey encodes 10010100. Then, the method must
678  shift the set of columns in this MinorKey to 11000001 (, and
679  return true). */
680 
681  /* The next two variables will finally name a column which is
682  (1) currently not yet among the columns in this MinorKey, but
683  (2) among the columns in mk, and
684  (3) which is "higher" than the lowest column in this MinorKey, and
685  (4) which is the lowest possible choice such that (1) - (3) hold.
686  If we should not be able to find such a column, then there is no next
687  subset of columns. In this case, the method will return false; otherwise
688  always true. */
689  int newBitBlockIndex = 0; /* the block index of the bit */
690  unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */
691 
692  /* number of ints (representing columns) in this MinorKey: */
693  int blockCount = this->getNumberOfColumnBlocks();
694  /* for iterating along the blocks of mk: */
695  int mkBlockIndex = mk.getNumberOfColumnBlocks();
696 
697  int hitBits = 0; /* the number of bits we have hit */
698  int bitCounter = 0; /* for storing the number of bits hit before a specific
699  moment; see below */
700  while (hitBits < k)
701  {
702  mkBlockIndex--;
703  unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
704  unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
705  the highest bit */
706  while (hitBits < k && shiftedBit > 0)
707  {
708  if ((blockCount - 1 >= mkBlockIndex) &&
709  (shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
710  else if (shiftedBit & currentInt)
711  {
712  newBitToBeSet = shiftedBit;
713  newBitBlockIndex = mkBlockIndex;
714  bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want to
715  remember the momentary number of hit bits.
716  This will later be needed; see below. */
717  }
718  shiftedBit = shiftedBit >> 1;
719  }
720  }
721  if (newBitToBeSet == 0)
722  {
723  return false;
724  }
725  else
726  {
727  /* Note that the following must hold when reaching this line of code:
728  (1) The column with bit newBitToBeSet in
729  this->getColumnKey(newBitBlockIndex) is currently not among the
730  columns in this MinorKey, but
731  (2) it is among the columns in mk, and
732  (3) it is higher than the lowest columns in this MinorKey, and
733  (4) it is the lowest possible choice such that (1) - (3) hold.
734  In the above example, we would reach this line with
735  newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
736  */
737 
738  if (blockCount - 1 < newBitBlockIndex)
739  { /* In this case, _columnKey is too small. */
740  /* free old memory */
741  delete [] _columnKey; _columnKey = 0;
742  _numberOfColumnBlocks = newBitBlockIndex + 1;
743  /* allocate memory for new entries in _columnKey; */
744  _columnKey = new unsigned int[_numberOfColumnBlocks];
745  /* initializing entries to zero */
746  for (int c = 0; c < _numberOfColumnBlocks; c++) _columnKey[c] = 0;
747  }
748  else
749  {
750  /* We need to delete all bits in _columnKey[newBitBlockIndex] that are
751  below newBitToBeSet: */
752  unsigned int anInt = this->getColumnKey(newBitBlockIndex);
753  unsigned int deleteBit = newBitToBeSet >> 1; /* in example: = 2^5 */
754  while (deleteBit > 0)
755  {
756  if (anInt & deleteBit) anInt -= deleteBit;
757  deleteBit = deleteBit >> 1;
758  };
759  _columnKey[newBitBlockIndex] = anInt;
760  /* ...and we delete all entries in _columnKey[i] fo
761  0 <= i < newBitBlockIndex */
762  for (int i = 0; i < newBitBlockIndex; i++)
763  _columnKey[i] = 0;
764  }
765  /* We have now deleted all bits from _columnKey[...] below the bit
766  2^newBitToBeSet. In the example we shall have at this point:
767  _columnKey[...] = 10000000. Now let's set the new bit: */
768  _columnKey[newBitBlockIndex] += newBitToBeSet;
769  /* in the example: _columnKey[newBitBlockIndex] = 11000000 */
770  bitCounter++; /* This is now the number of correct bits in
771  _columnKey[...]; i.e. in the example this will be equal
772  to 2. */
773 
774  /* Now we only need to fill _columnKey[...] with the lowest possible bits
775  until it consists of exactly k bits. (We know that we need to set
776  exactly (k - bitCounter) additional bits.) */
777  mkBlockIndex = -1;
778  while (bitCounter < k)
779  {
780  mkBlockIndex++;
781  unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
782  unsigned int shiftedBit = 1;
783  int exponent = 0;
784  /* invariant: shiftedBit = 2^exponent */
785  while (bitCounter < k && exponent < 32)
786  {
787  if (shiftedBit & currentInt)
788  {
789  _columnKey[mkBlockIndex] += shiftedBit;
790  bitCounter++;
791  };
792  shiftedBit = shiftedBit << 1;
793  exponent++;
794  }
795  };
796  /* in the example, we shall obtain _columnKey[...] = 11000001 */
797  return true;
798  }
799 }
int k
Definition: cfEzgcd.cc:93
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition: Minor.cc:306
int i
Definition: cfEzgcd.cc:123
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:296
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
bool MinorKey::selectNextRows ( const int  k,
const MinorKey mk 
)

This method redefines the set of rows represented by this MinorKey.

Both the old and the new set of k rows are subsets of the rows represented by mk. After the method, the defined set of rows is the next sensible choice of k rows of mk. (Here, next means the next w.r.t. the increasing index ordering on multi-indices of natural numbers.)
Note that the method modifies the given instance of MinorKey.

Assertion
It is assumed that mk represents at least k rows. Furthermore, the method assumes that the old set of rows represented by this is also a subset of the rows given by mk.
Parameters
kthe number of rows
mkthe MinorKey from which to choose the lowest k rows
Returns
true iff there is a next choice of k rows
See also
MinorKey::selectFirstRows (const int k, const MinorKey& mk)

Definition at line 539 of file Minor.cc.

540 {
541  /* We need to compute the set of k rows which must all be contained in mk.
542  AND: This set must be the least possible of this kind which is larger
543  than the currently encoded set of rows. (Here, '<' is w.r.t. to the
544  natural ordering on multi-indices.
545  Example: mk encodes the rows according to the bit pattern 11010111,
546  k = 3, this MinorKey encodes 10010100. Then, the method must
547  shift the set of rows in this MinorKey to 11000001 (, and
548  return true). */
549 
550  /* The next two variables will finally name a row which is
551  (1) currently not yet among the rows in this MinorKey, but
552  (2) among the rows in mk, and
553  (3) which is "higher" than the lowest row in this MinorKey, and
554  (4) which is the lowest possible choice such that (1) - (3) hold.
555  If we should not be able to find such a row, then there is no next
556  subset of rows. In this case, the method will return false; otherwise
557  always true. */
558  int newBitBlockIndex = 0; /* the block index of the bit */
559  unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */
560 
561  /* number of ints (representing rows) in this MinorKey: */
562  int blockCount = this->getNumberOfRowBlocks();
563  /* for iterating along the blocks of mk: */
564  int mkBlockIndex = mk.getNumberOfRowBlocks();
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
568  specific moment; see below */
569  while (hitBits < k)
570  {
571  mkBlockIndex--;
572  unsigned int currentInt = mk.getRowKey(mkBlockIndex);
573  unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
574  the highest bit */
575  while (hitBits < k && shiftedBit > 0)
576  {
577  if ((blockCount - 1 >= mkBlockIndex) &&
578  (shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
579  else if (shiftedBit & currentInt)
580  {
581  newBitToBeSet = shiftedBit;
582  newBitBlockIndex = mkBlockIndex;
583  bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want
584  to remember the momentary number of hit
585  bits. This will later be needed; see below. */
586  }
587  shiftedBit = shiftedBit >> 1;
588  }
589  }
590  if (newBitToBeSet == 0)
591  {
592  return false;
593  }
594  else
595  {
596  /* Note that the following must hold when reaching this line of code:
597  (1) The row with bit newBitToBeSet in this->getRowKey(newBitBlockIndex)
598  is currently not among the rows in this MinorKey, but
599  (2) it is among the rows in mk, and
600  (3) it is higher than the lowest row in this MinorKey, and
601  (4) it is the lowest possible choice such that (1) - (3) hold.
602  In the above example, we would reach this line with
603  newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
604  */
605 
606  if (blockCount - 1 < newBitBlockIndex)
607  { /* In this case, _rowKey is too small. */
608  /* free old memory */
609  delete [] _rowKey; _rowKey = 0;
610  _numberOfRowBlocks = newBitBlockIndex + 1;
611  /* allocate memory for new entries in _rowKey; */
612  _rowKey = new unsigned int[_numberOfRowBlocks];
613  /* initializing entries to zero */
614  for (int r = 0; r < _numberOfRowBlocks; r++) _rowKey[r] = 0;
615  }
616  else
617  {
618  /* We need to delete all bits in _rowKey[newBitBlockIndex] that are
619  below newBitToBeSet: */
620  unsigned int anInt = this->getRowKey(newBitBlockIndex);
621  unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5
622  while (deleteBit > 0)
623  {
624  if (anInt & deleteBit) anInt -= deleteBit;
625  deleteBit = deleteBit >> 1;
626  };
627  _rowKey[newBitBlockIndex] = anInt;
628  /* ...and we delete all entries in _rowKey[i] for
629  0 <= i < newBitBlockIndex */
630  for (int i = 0; i < newBitBlockIndex; i++)
631  _rowKey[i] = 0;
632  }
633 
634  /* We have now deleted all bits from _rowKey[...] below the bit
635  2^newBitToBeSet.
636  In the example we shall have at this point: _rowKey[...] = 10000000.
637  Now let's set the new bit: */
638  _rowKey[newBitBlockIndex] += newBitToBeSet;
639  /* in the example: _rowKey[newBitBlockIndex] = 11000000 */
640  bitCounter++; /* This is now the number of correct bits in _rowKey[...];
641  i.e. in the example this will be equal to 2. */
642 
643  /* Now we only need to fill _rowKey[...] with the lowest possible bits
644  until it consists of exactly k bits. (We know that we need to set
645  exactly (k - bitCounter) additional bits.) */
646  mkBlockIndex = -1;
647  while (bitCounter < k)
648  {
649  mkBlockIndex++;
650  unsigned int currentInt = mk.getRowKey(mkBlockIndex);
651  unsigned int shiftedBit = 1;
652  int exponent = 0;
653  /* invariant: shiftedBit = 2^exponent */
654  while (bitCounter < k && exponent < 32)
655  {
656  if (shiftedBit & currentInt)
657  {
658  _rowKey[mkBlockIndex] += shiftedBit;
659  bitCounter++;
660  };
661  shiftedBit = shiftedBit << 1;
662  exponent++;
663  }
664  };
665  /* in the example, we shall obtain _rowKey[...] = 11000001 */
666  return true;
667  }
668 }
int k
Definition: cfEzgcd.cc:93
const ring r
Definition: syzextra.cc:208
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:301
int i
Definition: cfEzgcd.cc:123
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:291
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
void MinorKey::set ( const int  lengthOfRowArray,
const unsigned int *  rowKey,
const int  lengthOfColumnArray,
const unsigned int *  columnKey 
)

A setter method for class MinorKey.

Just like the constructor of this class, this method will set all private fields according to the given parameters. Note that this method will change the given instance of MinorKey.

Parameters
lengthOfRowArraythe length of the array rowKey
rowKeya pointer to an array of ints encoding the set of rows of the minor
lengthOfColumnArraythe length of the array columnKey
columnKeya pointer to an array of ints encoding the set of columns of the minor
See also
MinorKey::MinorKey (const int lengthOfRowArray, const int* rowKey, const int lengthOfColumnArray, const int* columnKey)

Definition at line 64 of file Minor.cc.

67 {
68  /* free memory of _rowKey and _columnKey */
69  if (_numberOfRowBlocks > 0) { delete [] _rowKey; }
70  if (_numberOfColumnBlocks > 0) { delete [] _columnKey; }
71 
72  _numberOfRowBlocks = lengthOfRowArray;
73  _numberOfColumnBlocks = lengthOfColumnArray;
74 
75  /* allocate memory for new entries in _rowKey and _columnKey; */
76  _rowKey = new unsigned int[_numberOfRowBlocks];
77  _columnKey = new unsigned int[_numberOfColumnBlocks];
78 
79  /* copying values from parameter arrays to private arrays */
80  for (int r = 0; r < _numberOfRowBlocks; r++)
81  _rowKey[r] = rowKey[r];
82  for (int c = 0; c < _numberOfColumnBlocks; c++)
83  _columnKey[c] = columnKey[c];
84 }
const ring r
Definition: syzextra.cc:208
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
void MinorKey::setColumnKey ( const int  blockIndex,
const unsigned int  columnKey 
)
private

A method for setting the blockIndex-th element of _columnKey.

Parameters
blockIndexthe index of the int to be retrieved
columnKeythe column key to be set

Definition at line 408 of file Minor.cc.

410 {
411  _columnKey[blockIndex] = columnKey;
412 }
unsigned int * _columnKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-def...
Definition: Minor.h:56
void MinorKey::setRowKey ( const int  blockIndex,
const unsigned int  rowKey 
)
private

A method for setting the blockIndex-th element of _rowKey.

Parameters
blockIndexthe index of the int to be retrieved
rowKeythe row key to be set

Definition at line 403 of file Minor.cc.

404 {
405  _rowKey[blockIndex] = rowKey;
406 }
unsigned int * _rowKey
a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-define...
Definition: Minor.h:48
string MinorKey::toString ( ) const

A method for providing a printable version of the represented MinorKey.

Returns
a printable version of the given instance as instance of class string

Definition at line 801 of file Minor.cc.

802 { return ""; }

Friends And Related Function Documentation

friend class MinorProcessor
friend

For letting MinorProcessor see the private methods of this class.

Definition at line 136 of file Minor.h.

Field Documentation

unsigned int* MinorKey::_columnKey
private

a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which columns of a pre-defined matrix shall belong to the minor of interest; for i < j, _columnKey[i] holds lower bits than _columnKey[j]

Definition at line 56 of file Minor.h.

int MinorKey::_numberOfColumnBlocks
private

the number of ints (i.e.

32-bit-numbers) we need to encode the set of columns; If the higest column index is 70, we need 3 blocks of 32 bits to also encode the 70th bit.

Definition at line 72 of file Minor.h.

int MinorKey::_numberOfRowBlocks
private

the number of ints (i.e.

32-bit-numbers) we need to encode the set of rows; If the higest row index is 70, we need 3 blocks of 32 bits to also encode the 70th bit.

Definition at line 64 of file Minor.h.

unsigned int* MinorKey::_rowKey
private

a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which rows of a pre-defined matrix shall belong to the minor of interest; for i < j, _rowKey[i] holds lower bits than _rowKey[j]

Definition at line 48 of file Minor.h.


The documentation for this class was generated from the following files: