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

## Private Member Functions

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

## 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]
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]
int | _numberOfRowBlocks
| the number of ints (i.e.
int | _numberOfColumnBlocks
| the number of ints (i.e.

## Friends

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

## 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

  lengthOfRowArray | the length of the array rowKey
  rowKey | a pointer to an array of ints encoding the set of rows of the minor
  lengthOfColumnArray | the length of the array columnKey

  columnKey

  a pointer to an array of ints encoding the set of
  - columns of the minor

Definition at line 84 of file Minor.cc.

{
_numberOfRowBlocks = lengthOfRowArray;
_numberOfColumnBlocks = lengthOfColumnArray;
/* allocate memory for new entries in _rowKey and _columnKey */
_rowKey = (unsigned*)omalloc(_numberOfRowBlocks*sizeof(unsigned));
_columnKey = (unsigned*)omalloc(_numberOfColumnBlocks*sizeof(unsigned));
/* copying values from parameter arrays to private arrays */
for (int r = 0; r < _numberOfRowBlocks; r++)
_rowKey[r] = rowKey[r];
for (int c = 0; c < _numberOfColumnBlocks; c++)
_columnKey[c] = columnKey[c];
}
MinorKey::_numberOfColumnBlocks
int _numberOfColumnBlocks
the number of ints (i.e.
Definition Minor.h:72
MinorKey::_columnKey
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
MinorKey::_rowKey
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::_numberOfRowBlocks
int _numberOfRowBlocks
the number of ints (i.e.
Definition Minor.h:64
omalloc
#define omalloc(size)
Definition omAllocDecl.h:228

## 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

  mk | the MinorKey to be deep copied

Definition at line 23 of file Minor.cc.

{
_numberOfRowBlocks = mk.getNumberOfRowBlocks();
_numberOfColumnBlocks = mk.getNumberOfColumnBlocks();;
/* allocate memory for new entries in _rowKey and _columnKey */
_rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
_columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
/* copying values from parameter arrays to private arrays */
for (int r = 0; r < _numberOfRowBlocks; r++)
_rowKey[r] = mk.getRowKey(r);
for (int c = 0; c < _numberOfColumnBlocks; c++)
_columnKey[c] = mk.getColumnKey(c);
}
MinorKey::getNumberOfColumnBlocks
int getNumberOfColumnBlocks() const
Accessor of _numberOfColumnBlocks.
Definition Minor.cc:302
MinorKey::getRowKey
unsigned int getRowKey(const int blockIndex) const
Inlined accessor of blockIndex-th element of _rowKey.
Definition Minor.cc:287
MinorKey::getNumberOfRowBlocks
int getNumberOfRowBlocks() const
Accessor of _numberOfRowBlocks.
Definition Minor.cc:297
MinorKey::getColumnKey
unsigned int getColumnKey(const int blockIndex) const
Accessor of blockIndex-th element of _columnKey.
Definition Minor.cc:292
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210

## ~MinorKey()

MinorKey::~MinorKey | ( |  | ) |

A destructor for deleting an instance.

Definition at line 104 of file Minor.cc.

{
_numberOfRowBlocks = 0;
_numberOfColumnBlocks = 0;
omfree(_rowKey); _rowKey = NULL;
omfree(_columnKey); _columnKey = NULL;
}
omfree
#define omfree(addr)
Definition omAllocDecl.h:237
NULL
#define NULL
Definition omList.c:12

## 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

  mk | a 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 412 of file Minor.cc.

{
/* compare by rowKeys first; in case of equality, use columnKeys */
if (this->getNumberOfRowBlocks() < that.getNumberOfRowBlocks())
return -1;
if (this->getNumberOfRowBlocks() > that.getNumberOfRowBlocks())
return 1;
/* Here, numbers of rows are equal. */
for (int r = this->getNumberOfRowBlocks() - 1; r >= 0; r--)
{
if (this->getRowKey(r) < that.getRowKey(r)) return -1;
if (this->getRowKey(r) > that.getRowKey(r)) return 1;
}
/* Here, this and that encode ecaxtly the same sets of rows.
Now, we take a look at the columns. */
if (this->getNumberOfColumnBlocks() < that.getNumberOfColumnBlocks())
return -1;
if (this->getNumberOfColumnBlocks() > that.getNumberOfColumnBlocks())
return 1;
/* Here, numbers of columns are equal. */
for (int c = this->getNumberOfColumnBlocks() - 1; c >= 0; c--)
{
if (this->getColumnKey(c) < that.getColumnKey(c)) return -1;
if (this->getColumnKey(c) > that.getColumnKey(c)) return 1;
}
/* Here, this and that encode exactly the same sets of rows and columns. */
return 0;
}

## 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

  i | the 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.

{
/* This method is to return the absolute (0-based) index of the i-th
column encoded in \a this.
Example: bit-pattern of columns: "10010001101", i = 3:
This should yield the 0-based absolute index of the 3-rd bit
(counted from the right), i.e. 7. */
int matchedBits = -1; /* counter for matched bits; this needs to reach i,
then we're done */
for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getColumnKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold throughout the
entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) matchedBits++;
if (matchedBits == i) return exponent + (32 * block);
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* We should never reach this line of code. */
assume(false);
return -1;
}
i
int i
Definition cfEzgcd.cc:132
exponent
#define exponent
Definition interpolation.cc:31
assume
#define assume(x)
Definition mod2.h:389
block
#define block
Definition scanner.cc:646

## 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

  target | a pointer to some array of ints that is to be filled with the requested indices

Definition at line 202 of file Minor.cc.

{
int i = 0; /* index for filling the target array */
for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getColumnKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold throughout the
entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
shiftedBit = shiftedBit << 1;
exponent++;
}
}
}

## 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

  i | the 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.

{
/* This method is to return the absolute (0-based) index of the i-th
row encoded in \a this.
Example: bit-pattern of rows: "10010001101", i = 3:
This should yield the 0-based absolute index of the 3-rd bit
(counted from the right), i.e. 7. */
int matchedBits = -1; /* counter for matched bits;
this needs to reach i, then we're done */
for (int block = 0; block < getNumberOfRowBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getRowKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold throughout the
entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) matchedBits++;
if (matchedBits == i) return exponent + (32 * block);
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* We should never reach this line of code. */
assume(false);
return -1;
}

## 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

  target | a pointer to some array of ints that is to be filled with the requested indices

Definition at line 181 of file Minor.cc.

{
int i = 0; /* index for filling the target array */
for (int block = 0; block < getNumberOfRowBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getRowKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold throughout the
entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) target[i++] = exponent + (32 * block);
shiftedBit = shiftedBit << 1;
exponent++;
}
}
}

## getColumnKey()

unsigned int MinorKey::getColumnKey | ( | const int | blockIndex | ) | const

private

Accessor of blockIndex-th element of _columnKey.

Parameters

  blockIndex | the index of the int to be retrieved

Returns
  an entry of _columnKey

Definition at line 292 of file Minor.cc.

{
return _columnKey[blockIndex];
}

## 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.

{
return _numberOfColumnBlocks;
}

## 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.

{
return _numberOfRowBlocks;
}

## 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

  i | the 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.

{
/* This method is to return the relative (0-based) index
of the column with absolute index \c i.
Example: bit-pattern of columns: "10010001101", i = 7:
This should yield the 0-based relative index of the bit
corresponding to column no. 7, i.e. 3. */
int matchedBits = -1; /* counter for matched bits; this is going
to contain our return value */
for (int block = 0; block < getNumberOfColumnBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getColumnKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold
throughout the entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) matchedBits++;
if (exponent + (32 * block) == i) return matchedBits;
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* We should never reach this line of code. */
assume(false);
return -1;
}

## 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

  i | the 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.

{
/* This method is to return the relative (0-based) index of the row
with absolute index \c i.
Example: bit-pattern of rows: "10010001101", i = 7:
This should yield the 0-based relative index of the bit
corresponding to row no. 7, i.e. 3. */
int matchedBits = -1; /* counter for matched bits; this is going to
contain our return value */
for (int block = 0; block < getNumberOfRowBlocks(); block ++)
{
/* start with lowest bits, i.e. in block No. 0 */
/* the bits in this block of 32 bits: */
unsigned int blockBits = getRowKey(block);
unsigned int shiftedBit = 1;
int exponent = 0;
/* The invariant "shiftedBit = 2^exponent" will hold throughout the
entire while loop. */
while (exponent < 32)
{
if (shiftedBit & blockBits) matchedBits++;
if (exponent + (32 * block) == i) return matchedBits;
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* We should never reach this line of code. */
assume(false);
return -1;
}

## getRowKey()

unsigned int MinorKey::getRowKey | ( | const int | blockIndex | ) | const

private

Inlined accessor of blockIndex-th element of _rowKey.

Parameters

  blockIndex | the index of the int to be retrieved

Returns
  an entry of _rowKey

Definition at line 287 of file Minor.cc.

{
return _rowKey[blockIndex];
}

## 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

  absoluteEraseRowIndex | the 0-based absolute index of a row in mk
  absoluteEraseColumnIndex | the 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.

{
int rowBlock = absoluteEraseRowIndex / 32;
int exponent = absoluteEraseRowIndex % 32;
unsigned int newRowBits = getRowKey(rowBlock) - (1 << exponent);
int highestRowBlock = getNumberOfRowBlocks() - 1;
/* highestRowBlock will finally contain the highest block index with
non-zero bit pattern */
if ((newRowBits == 0) && (rowBlock == highestRowBlock))
{
/* we have thus nullified the highest block;
we can now forget about the highest block... */
highestRowBlock -= 1;
while (getRowKey(highestRowBlock) == 0) /* ...and maybe even some more
zero-blocks */
highestRowBlock -= 1;
}
/* highestRowBlock now contains the highest row block index with non-zero
bit pattern */
int columnBlock = absoluteEraseColumnIndex / 32;
exponent = absoluteEraseColumnIndex % 32;
unsigned int newColumnBits = getColumnKey(columnBlock) - (1 << exponent);
int highestColumnBlock = getNumberOfColumnBlocks() - 1;
/* highestColumnBlock will finally contain the highest block index with
non-zero bit pattern */
if ((newColumnBits == 0) && (columnBlock == highestColumnBlock))
{
/* we have thus nullified the highest block;
we can now forget about the highest block... */
highestColumnBlock -= 1;
while (getColumnKey(highestColumnBlock) == 0) /* ...and maybe even some
more zero-blocks */
highestColumnBlock -= 1;
}
/* highestColumnBlock now contains the highest column block index with
non-zero bit pattern */
MinorKey result(highestRowBlock + 1, _rowKey, highestColumnBlock + 1,
_columnKey);
/* This is just a copy with maybe some leading bit blocks omitted. We still
need to re-define the row block at index 'rowBlock' and the column block
at index 'columnBlock': */
if ((newRowBits != 0) || (rowBlock < getNumberOfRowBlocks() - 1))
result.setRowKey(rowBlock, newRowBits);
if ((newColumnBits != 0) || (columnBlock < getNumberOfColumnBlocks() - 1))
result.setColumnKey(columnBlock, newColumnBits);
#ifndef SING_NDEBUG
/* let's check that the number of selected rows and columns are equal;
(this check is only performed in the debug version) */
assume(result.getSetBits(1) == result.getSetBits(2));
#endif
return result;
}
MinorKey::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.
Definition Minor.cc:84
result
return result
Definition facAbsBiFact.cc:76

## operator<()

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

just to make the compiler happy

Definition at line 451 of file Minor.cc.

{
assume(false);
return this->compare(mk) == -1;
}
MinorKey::compare
int compare(const MinorKey &mk) const
A comparator for two instances of MinorKey.
Definition Minor.cc:412

## operator=()

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

just to make the compiler happy

Definition at line 39 of file Minor.cc.

{
omfree(_rowKey); _rowKey = NULL;
omfree(_columnKey); _columnKey = NULL;
_numberOfRowBlocks = 0;
_numberOfColumnBlocks = 0;
_numberOfRowBlocks = mk.getNumberOfRowBlocks();
_numberOfColumnBlocks = mk.getNumberOfColumnBlocks();;
/* allocate memory for new entries in _rowKey and _columnKey */
_rowKey = (unsigned*)omalloc(_numberOfRowBlocks*sizeof(unsigned));
_columnKey = (unsigned*)omalloc(_numberOfColumnBlocks*sizeof(unsigned));
/* copying values from parameter arrays to private arrays */
for (int r = 0; r < _numberOfRowBlocks; r++)
_rowKey[r] = mk.getRowKey(r);
for (int c = 0; c < _numberOfColumnBlocks; c++)
_columnKey[c] = mk.getColumnKey(c);
return *this;
}

## operator==()

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

just to make the compiler happy

Definition at line 443 of file Minor.cc.

{
assume(false);
return this->compare(mk) == 0;
}

## reset()

void MinorKey::reset | ( |  | ) |

private

A method for deleting all entries of _rowKey and _columnKey.

Definition at line 13 of file Minor.cc.

{
_numberOfRowBlocks = 0;
_numberOfColumnBlocks = 0;
omfree(_rowKey);
_rowKey = NULL;
omfree(_columnKey);
_columnKey = NULL;
}

## 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

  k | the number of columns
  mk | the MinorKey from which to choose the lowest `k` columns

See also
  MinorKey::selectNextColumns (const int k, const MinorKey& mk)

Definition at line 498 of file Minor.cc.

{
int hitBits = 0; /* the number of bits we have hit; in the end, this
has to be equal to k, the dimension of the minor */
int blockIndex = -1; /* the index of the current int in mk */
unsigned int highestInt = 0; /* the new highest block of this MinorKey */
/* We determine which ints of mk we can copy. Their indices will be
0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
int (which may be only a portion of the corresponding int in mk.
We loop until hitBits = k: */
while (hitBits < k)
{
blockIndex++;
highestInt = 0;
unsigned int currentInt = mk.getColumnKey(blockIndex);
unsigned int shiftedBit = 1;
int exponent = 0;
/* invariant in the loop: shiftedBit = 2^exponent */
while (exponent < 32 && hitBits < k)
{
if (shiftedBit & currentInt)
{
highestInt += shiftedBit;
hitBits++;
}
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* free old memory */
omfree(_columnKey); _columnKey = NULL;
_numberOfColumnBlocks = blockIndex + 1;
/* allocate memory for new entries in _columnKey; */
_columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
/* copying values from mk to this MinorKey */
for (int c = 0; c < blockIndex; c++)
_columnKey[c] = mk.getColumnKey(c);
_columnKey[blockIndex] = highestInt;
}
k
int k
Definition cfEzgcd.cc:99

## 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

  k | the number of rows
  mk | the MinorKey from which to choose the lowest `k` rows

See also
  MinorKey::selectNextRows (const int k, const MinorKey& mk)

Definition at line 457 of file Minor.cc.

{
int hitBits = 0; /* the number of bits we have hit; in the end, this
has to be equal to k, the dimension of the minor */
int blockIndex = -1; /* the index of the current int in mk */
unsigned int highestInt = 0; /* the new highest block of this MinorKey */
/* We determine which ints of mk we can copy. Their indices will be
0, 1, ..., blockIndex - 1. And highestInt is going to capture the highest
int (which may be only a portion of the corresponding int in mk.
We loop until hitBits = k: */
while (hitBits < k)
{
blockIndex++;
highestInt = 0;
unsigned int currentInt = mk.getRowKey(blockIndex);
unsigned int shiftedBit = 1;
int exponent = 0;
/* invariant in the loop: shiftedBit = 2^exponent */
while (exponent < 32 && hitBits < k)
{
if (shiftedBit & currentInt)
{
highestInt += shiftedBit;
hitBits++;
}
shiftedBit = shiftedBit << 1;
exponent++;
}
}
/* free old memory */
omfree(_rowKey);
_rowKey = NULL;
_numberOfRowBlocks = blockIndex + 1;
/* allocate memory for new entries in _rowKey; */
_rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
/* copying values from mk to this MinorKey */
for (int r = 0; r < blockIndex; r++)
_rowKey[r] = mk.getRowKey(r);
_rowKey[blockIndex] = highestInt;
}

## 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

  k | the number of columns
  mk | the 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 669 of file Minor.cc.

{
/* We need to compute the set of k columns which must all be contained in mk.
AND: This set must be the least possible of this kind which is larger
than the currently encoded set of columns. (Here, '<' is w.r.t. to
the natural ordering on multi-indices.
Example: mk encodes the columns according to the bit pattern 11010111,
k = 3, this MinorKey encodes 10010100. Then, the method must
shift the set of columns in this MinorKey to 11000001 (, and
return true). */
/* The next two variables will finally name a column which is
(1) currently not yet among the columns in this MinorKey, but
(2) among the columns in mk, and
(3) which is "higher" than the lowest column in this MinorKey, and
(4) which is the lowest possible choice such that (1) - (3) hold.
If we should not be able to find such a column, then there is no next
subset of columns. In this case, the method will return false; otherwise
always true. */
int newBitBlockIndex = 0; /* the block index of the bit */
unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */
/* number of ints (representing columns) in this MinorKey: */
int blockCount = this->getNumberOfColumnBlocks();
/* for iterating along the blocks of mk: */
int mkBlockIndex = mk.getNumberOfColumnBlocks();
int hitBits = 0; /* the number of bits we have hit */
int bitCounter = 0; /* for storing the number of bits hit before a specific
moment; see below */
while (hitBits < k)
{
mkBlockIndex--;
unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
the highest bit */
while (hitBits < k && shiftedBit > 0)
{
if ((blockCount - 1 >= mkBlockIndex) &&
(shiftedBit & this->getColumnKey(mkBlockIndex))) hitBits++;
else if (shiftedBit & currentInt)
{
newBitToBeSet = shiftedBit;
newBitBlockIndex = mkBlockIndex;
bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want to
remember the momentary number of hit bits.
This will later be needed; see below. */
}
shiftedBit = shiftedBit >> 1;
}
}
if (newBitToBeSet == 0)
{
return false;
}
else
{
/* Note that the following must hold when reaching this line of code:
(1) The column with bit newBitToBeSet in
this->getColumnKey(newBitBlockIndex) is currently not among the
columns in this MinorKey, but
(2) it is among the columns in mk, and
(3) it is higher than the lowest columns in this MinorKey, and
(4) it is the lowest possible choice such that (1) - (3) hold.
In the above example, we would reach this line with
newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
*/
if (blockCount - 1 < newBitBlockIndex)
{ /* In this case, _columnKey is too small. */
/* free old memory */
omFree( _columnKey); _columnKey = NULL;
_numberOfColumnBlocks = newBitBlockIndex + 1;
/* allocate memory for new entries in _columnKey; */
_columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
/* initializing entries to zero */
for (int c = 0; c < _numberOfColumnBlocks; c++) _columnKey[c] = 0;
}
else
{
/* We need to delete all bits in _columnKey[newBitBlockIndex] that are
below newBitToBeSet: */
unsigned int anInt = this->getColumnKey(newBitBlockIndex);
unsigned int deleteBit = newBitToBeSet >> 1; /* in example: = 2^5 */
while (deleteBit > 0)
{
if (anInt & deleteBit) anInt -= deleteBit;
deleteBit = deleteBit >> 1;
};
_columnKey[newBitBlockIndex] = anInt;
/* ...and we delete all entries in _columnKey[i] for
0 <= i < newBitBlockIndex */
for (int i = 0; i < newBitBlockIndex; i++)
_columnKey[i] = 0;
}
/* We have now deleted all bits from _columnKey[...] below the bit
2^newBitToBeSet. In the example we shall have at this point:
_columnKey[...] = 10000000. Now let's set the new bit: */
_columnKey[newBitBlockIndex] += newBitToBeSet;
/* in the example: _columnKey[newBitBlockIndex] = 11000000 */
bitCounter++; /* This is now the number of correct bits in
_columnKey[...]; i.e. in the example this will be equal
to 2. */
/* Now we only need to fill _columnKey[...] with the lowest possible bits
until it consists of exactly k bits. (We know that we need to set
exactly (k - bitCounter) additional bits.) */
mkBlockIndex = -1;
while (bitCounter < k)
{
mkBlockIndex++;
unsigned int currentInt = mk.getColumnKey(mkBlockIndex);
unsigned int shiftedBit = 1;
int exponent = 0;
/* invariant: shiftedBit = 2^exponent */
while (bitCounter < k && exponent < 32)
{
if (shiftedBit & currentInt)
{
_columnKey[mkBlockIndex] += shiftedBit;
bitCounter++;
};
shiftedBit = shiftedBit << 1;
exponent++;
}
};
/* in the example, we shall obtain _columnKey[...] = 11000001 */
return true;
}
}
omFree
#define omFree(addr)
Definition omAllocDecl.h:261

## 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

  k | the number of rows
  mk | the 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 538 of file Minor.cc.

{
/* We need to compute the set of k rows which must all be contained in mk.
AND: This set must be the least possible of this kind which is larger
than the currently encoded set of rows. (Here, '<' is w.r.t. to the
natural ordering on multi-indices.
Example: mk encodes the rows according to the bit pattern 11010111,
k = 3, this MinorKey encodes 10010100. Then, the method must
shift the set of rows in this MinorKey to 11000001 (, and
return true). */
/* The next two variables will finally name a row which is
(1) currently not yet among the rows in this MinorKey, but
(2) among the rows in mk, and
(3) which is "higher" than the lowest row in this MinorKey, and
(4) which is the lowest possible choice such that (1) - (3) hold.
If we should not be able to find such a row, then there is no next
subset of rows. In this case, the method will return false; otherwise
always true. */
int newBitBlockIndex = 0; /* the block index of the bit */
unsigned int newBitToBeSet = 0; /* the bit as 2^e, where 0 <= e <= 31 */
/* number of ints (representing rows) in this MinorKey: */
int blockCount = this->getNumberOfRowBlocks();
/* for iterating along the blocks of mk: */
int mkBlockIndex = mk.getNumberOfRowBlocks();
int hitBits = 0; /* the number of bits we have hit */
int bitCounter = 0; /* for storing the number of bits hit before a
specific moment; see below */
while (hitBits < k)
{
mkBlockIndex--;
unsigned int currentInt = mk.getRowKey(mkBlockIndex);
unsigned int shiftedBit = 1 << 31; /* initially, this equals 2^31, i.e.
the highest bit */
while (hitBits < k && shiftedBit > 0)
{
if ((blockCount - 1 >= mkBlockIndex) &&
(shiftedBit & this->getRowKey(mkBlockIndex))) hitBits++;
else if (shiftedBit & currentInt)
{
newBitToBeSet = shiftedBit;
newBitBlockIndex = mkBlockIndex;
bitCounter = hitBits; /* So, whenever we set newBitToBeSet, we want
to remember the momentary number of hit
bits. This will later be needed; see below. */
}
shiftedBit = shiftedBit >> 1;
}
}
if (newBitToBeSet == 0)
{
return false;
}
else
{
/* Note that the following must hold when reaching this line of code:
(1) The row with bit newBitToBeSet in this->getRowKey(newBitBlockIndex)
is currently not among the rows in this MinorKey, but
(2) it is among the rows in mk, and
(3) it is higher than the lowest row in this MinorKey, and
(4) it is the lowest possible choice such that (1) - (3) hold.
In the above example, we would reach this line with
newBitToBeSet == 2^6 and bitCounter == 1 (resulting from the bit 2^7).
*/
if (blockCount - 1 < newBitBlockIndex)
{ /* In this case, _rowKey is too small. */
/* free old memory */
omFree(_rowKey); _rowKey = NULL;
_numberOfRowBlocks = newBitBlockIndex + 1;
/* allocate memory for new entries in _rowKey; */
_rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
/* initializing entries to zero */
for (int r = 0; r < _numberOfRowBlocks; r++) _rowKey[r] = 0;
}
else
{
/* We need to delete all bits in _rowKey[newBitBlockIndex] that are
below newBitToBeSet: */
unsigned int anInt = this->getRowKey(newBitBlockIndex);
unsigned int deleteBit = newBitToBeSet >> 1; // in example: = 2^5
while (deleteBit > 0)
{
if (anInt & deleteBit) anInt -= deleteBit;
deleteBit = deleteBit >> 1;
};
_rowKey[newBitBlockIndex] = anInt;
/* ...and we delete all entries in _rowKey[i] for
0 <= i < newBitBlockIndex */
for (int i = 0; i < newBitBlockIndex; i++)
_rowKey[i] = 0;
}
/* We have now deleted all bits from _rowKey[...] below the bit
2^newBitToBeSet.
In the example we shall have at this point: _rowKey[...] = 10000000.
Now let's set the new bit: */
_rowKey[newBitBlockIndex] += newBitToBeSet;
/* in the example: _rowKey[newBitBlockIndex] = 11000000 */
bitCounter++; /* This is now the number of correct bits in _rowKey[...];
i.e. in the example this will be equal to 2. */
/* Now we only need to fill _rowKey[...] with the lowest possible bits
until it consists of exactly k bits. (We know that we need to set
exactly (k - bitCounter) additional bits.) */
mkBlockIndex = -1;
while (bitCounter < k)
{
mkBlockIndex++;
unsigned int currentInt = mk.getRowKey(mkBlockIndex);
unsigned int shiftedBit = 1;
int exponent = 0;
/* invariant: shiftedBit = 2^exponent */
while (bitCounter < k && exponent < 32)
{
if (shiftedBit & currentInt)
{
_rowKey[mkBlockIndex] += shiftedBit;
bitCounter++;
};
shiftedBit = shiftedBit << 1;
exponent++;
}
};
/* in the example, we shall obtain _rowKey[...] = 11000001 */
return true;
}
}

## 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

  lengthOfRowArray | the length of the array rowKey
  rowKey | a pointer to an array of ints encoding the set of rows of the minor
  lengthOfColumnArray | the length of the array columnKey
  columnKey | a 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.

{
/* free memory of _rowKey and _columnKey */
if (_numberOfRowBlocks > 0) { omFree(_rowKey); }
if (_numberOfColumnBlocks > 0) { omFree(_columnKey); }
_numberOfRowBlocks = lengthOfRowArray;
_numberOfColumnBlocks = lengthOfColumnArray;
/* allocate memory for new entries in _rowKey and _columnKey; */
_rowKey = (unsigned*)omAlloc(_numberOfRowBlocks*sizeof(unsigned));
_columnKey = (unsigned*)omAlloc(_numberOfColumnBlocks*sizeof(unsigned));
/* copying values from parameter arrays to private arrays */
for (int r = 0; r < _numberOfRowBlocks; r++)
_rowKey[r] = rowKey[r];
for (int c = 0; c < _numberOfColumnBlocks; c++)
_columnKey[c] = columnKey[c];
}

## setColumnKey()

void MinorKey::setColumnKey | ( | const int | blockIndex,
|  | const unsigned int | columnKey )

private

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

Parameters

  blockIndex | the index of the int to be retrieved
  columnKey | the column key to be set

Definition at line 406 of file Minor.cc.

{
_columnKey[blockIndex] = columnKey;
}

## setRowKey()

void MinorKey::setRowKey | ( | const int | blockIndex,
|  | const unsigned int | rowKey )

private

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

Parameters

  blockIndex | the index of the int to be retrieved
  rowKey | the row key to be set

Definition at line 401 of file Minor.cc.

{
_rowKey[blockIndex] = rowKey;
}

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

{ return ""; }

## Friends And Related Symbol 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 highest 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 highest 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:

- kernel/linear_algebra/Minor.h
- kernel/linear_algebra/Minor.cc