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=NULL, const int lengthOfColumnArray=0, const unsigned int *const columnKey=NULL)
 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() [1/2]

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

A constructor for class MinorKey.

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 84 of file Minor.cc.

88 {
89  _numberOfRowBlocks = lengthOfRowArray;
90  _numberOfColumnBlocks = lengthOfColumnArray;
91 
92  /* allocate memory for new entries in _rowKey and _columnKey */
93  _rowKey = (unsigned*)omalloc(_numberOfRowBlocks*sizeof(unsigned));
94  _columnKey = (unsigned*)omalloc(_numberOfColumnBlocks*sizeof(unsigned));
95 
96  /* copying values from parameter arrays to private arrays */
97  for (int r = 0; r < _numberOfRowBlocks; r++)
98  _rowKey[r] = rowKey[r];
99 
100  for (int c = 0; c < _numberOfColumnBlocks; c++)
101  _columnKey[c] = columnKey[c];
102 }
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
#define omalloc(size)
Definition: omAllocDecl.h:228
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() [2/2]

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 = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
30  _columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
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 }
#define omAlloc(size)
Definition: omAllocDecl.h:210
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:297
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:302
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:287
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:292
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::~MinorKey ( )

A destructor for deleting an instance.

Definition at line 104 of file Minor.cc.

105 {
106  _numberOfRowBlocks = 0;
110 }
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 omfree(addr)
Definition: omAllocDecl.h:237
#define NULL
Definition: omList.c:10
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

◆ compare()

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 410 of file Minor.cc.

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

◆ getAbsoluteColumnIndex()

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 149 of file Minor.cc.

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

◆ getAbsoluteColumnIndices()

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 202 of file Minor.cc.

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

◆ getAbsoluteRowIndex()

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 117 of file Minor.cc.

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

◆ getAbsoluteRowIndices()

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 181 of file Minor.cc.

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

◆ getColumnKey()

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 292 of file Minor.cc.

293 {
294  return _columnKey[blockIndex];
295 }
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

◆ getNumberOfColumnBlocks()

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 302 of file Minor.cc.

303 {
304  return _numberOfColumnBlocks;
305 }
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72

◆ getNumberOfRowBlocks()

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 297 of file Minor.cc.

298 {
299  return _numberOfRowBlocks;
300 }
int _numberOfRowBlocks
the number of ints (i.e.
Definition: Minor.h:64

◆ getRelativeColumnIndex()

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 255 of file Minor.cc.

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

◆ getRelativeRowIndex()

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 223 of file Minor.cc.

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

◆ getRowKey()

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 287 of file Minor.cc.

288 {
289  return _rowKey[blockIndex];
290 }
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

◆ getSetBits()

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

◆ getSubMinorKey()

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 343 of file Minor.cc.

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

◆ operator<()

bool MinorKey::operator< ( const MinorKey mk) const

just to make the compiler happy

Definition at line 449 of file Minor.cc.

450 {
451  assume(false);
452  return this->compare(mk) == -1;
453 }
#define assume(x)
Definition: mod2.h:394
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:410

◆ operator=()

MinorKey & MinorKey::operator= ( const MinorKey mk)

just to make the compiler happy

Definition at line 39 of file Minor.cc.

40 {
45 
48 
49  /* allocate memory for new entries in _rowKey and _columnKey */
50  _rowKey = (unsigned*)omalloc(_numberOfRowBlocks*sizeof(unsigned));
51  _columnKey = (unsigned*)omalloc(_numberOfColumnBlocks*sizeof(unsigned));
52 
53  /* copying values from parameter arrays to private arrays */
54  for (int r = 0; r < _numberOfRowBlocks; r++)
55  _rowKey[r] = mk.getRowKey(r);
56  for (int c = 0; c < _numberOfColumnBlocks; c++)
57  _columnKey[c] = mk.getColumnKey(c);
58 
59  return *this;
60 }
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition: Minor.cc:297
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:302
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omalloc(size)
Definition: omAllocDecl.h:228
#define NULL
Definition: omList.c:10
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:287
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:292
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

◆ operator==()

bool MinorKey::operator== ( const MinorKey mk) const

just to make the compiler happy

Definition at line 441 of file Minor.cc.

442 {
443  assume(false);
444  return this->compare(mk) == 0;
445 }
#define assume(x)
Definition: mod2.h:394
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition: Minor.cc:410

◆ reset()

void MinorKey::reset ( )
private

A method for deleting all entries of _rowKey and _columnKey.

Definition at line 13 of file Minor.cc.

14 {
17  omFree(_rowKey);
18  _rowKey = NULL;
20  _columnKey = NULL;
21 }
#define omFree(addr)
Definition: omAllocDecl.h:261
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 NULL
Definition: omList.c:10
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

◆ selectFirstColumns()

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 496 of file Minor.cc.

497 {
498  int hitBits = 0; /* the number of bits we have hit; in the end, this
499  has to be equal to k, the dimension of the minor */
500  int blockIndex = -1; /* the index of the current int in mk */
501  unsigned int highestInt = 0; /* the new highest block of this MinorKey */
502  /* We determine which ints of mk we can copy. Their indices will be
503  0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
504  int (which may be only a portion of the corresponding int in mk.
505  We loop until hitBits = k: */
506  while (hitBits < k)
507  {
508  blockIndex++;
509  highestInt = 0;
510  unsigned int currentInt = mk.getColumnKey(blockIndex);
511  unsigned int shiftedBit = 1;
512  int exponent = 0;
513  /* invariant in the loop: shiftedBit = 2^exponent */
514  while (exponent < 32 && hitBits < k)
515  {
516  if (shiftedBit & currentInt)
517  {
518  highestInt += shiftedBit;
519  hitBits++;
520  }
521  shiftedBit = shiftedBit << 1;
522  exponent++;
523  }
524  }
525  /* free old memory */
527  _numberOfColumnBlocks = blockIndex + 1;
528  /* allocate memory for new entries in _columnKey; */
529  _columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
530  /* copying values from mk to this MinorKey */
531  for (int c = 0; c < blockIndex; c++)
532  _columnKey[c] = mk.getColumnKey(c);
533  _columnKey[blockIndex] = highestInt;
534 }
int k
Definition: cfEzgcd.cc:93
#define omAlloc(size)
Definition: omAllocDecl.h:210
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 omfree(addr)
Definition: omAllocDecl.h:237
#define NULL
Definition: omList.c:10
int _numberOfColumnBlocks
the number of ints (i.e.
Definition: Minor.h:72
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition: Minor.cc:292
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )

◆ selectFirstRows()

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 455 of file Minor.cc.

456 {
457  int hitBits = 0; /* the number of bits we have hit; in the end, this
458  has to be equal to k, the dimension of the minor */
459  int blockIndex = -1; /* the index of the current int in mk */
460  unsigned int highestInt = 0; /* the new highest block of this MinorKey */
461  /* We determine which ints of mk we can copy. Their indices will be
462  0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
463  int (which may be only a portion of the corresponding int in mk.
464  We loop until hitBits = k: */
465  while (hitBits < k)
466  {
467  blockIndex++;
468  highestInt = 0;
469  unsigned int currentInt = mk.getRowKey(blockIndex);
470  unsigned int shiftedBit = 1;
471  int exponent = 0;
472  /* invariant in the loop: shiftedBit = 2^exponent */
473  while (exponent < 32 && hitBits < k)
474  {
475  if (shiftedBit & currentInt)
476  {
477  highestInt += shiftedBit;
478  hitBits++;
479  }
480  shiftedBit = shiftedBit << 1;
481  exponent++;
482  }
483  }
484  /* free old memory */
485  omfree(_rowKey);
486  _rowKey = NULL;
487  _numberOfRowBlocks = blockIndex + 1;
488  /* allocate memory for new entries in _rowKey; */
489  _rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
490  /* copying values from mk to this MinorKey */
491  for (int r = 0; r < blockIndex; r++)
492  _rowKey[r] = mk.getRowKey(r);
493  _rowKey[blockIndex] = highestInt;
494 }
int k
Definition: cfEzgcd.cc:93
#define omAlloc(size)
Definition: omAllocDecl.h:210
const ring r
Definition: syzextra.cc:208
#define omfree(addr)
Definition: omAllocDecl.h:237
#define NULL
Definition: omList.c:10
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition: Minor.cc:287
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 * _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

◆ selectNextColumns()

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 667 of file Minor.cc.

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

◆ selectNextRows()

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 536 of file Minor.cc.

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

◆ set()

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 62 of file Minor.cc.

65 {
66  /* free memory of _rowKey and _columnKey */
67  if (_numberOfRowBlocks > 0) { omFree(_rowKey); }
69 
70  _numberOfRowBlocks = lengthOfRowArray;
71  _numberOfColumnBlocks = lengthOfColumnArray;
72 
73  /* allocate memory for new entries in _rowKey and _columnKey; */
74  _rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
75  _columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
76 
77  /* copying values from parameter arrays to private arrays */
78  for (int r = 0; r < _numberOfRowBlocks; r++)
79  _rowKey[r] = rowKey[r];
80  for (int c = 0; c < _numberOfColumnBlocks; c++)
81  _columnKey[c] = columnKey[c];
82 }
#define omAlloc(size)
Definition: omAllocDecl.h:210
const ring r
Definition: syzextra.cc:208
#define omFree(addr)
Definition: omAllocDecl.h:261
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

◆ setColumnKey()

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 404 of file Minor.cc.

406 {
407  _columnKey[blockIndex] = columnKey;
408 }
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

◆ setRowKey()

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 399 of file Minor.cc.

400 {
401  _rowKey[blockIndex] = rowKey;
402 }
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

◆ toString()

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 798 of file Minor.cc.

799 { return ""; }

Friends And Related Function Documentation

◆ MinorProcessor

friend class MinorProcessor
friend

For letting MinorProcessor see the private methods of this class.

Definition at line 136 of file Minor.h.

Field Documentation

◆ _columnKey

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.

◆ _numberOfColumnBlocks

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.

◆ _numberOfRowBlocks

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.

◆ _rowKey

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: