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

MinorKey &	operator= (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...

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

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() [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()

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;
}

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;
}

◆ 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;
}

◆ 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;
}

◆ 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;
}

◆ 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;
  }
}

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

801{ 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 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

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ MinorKey() [1/2]

◆ MinorKey() [2/2]

◆ ~MinorKey()

Member Function Documentation

◆ compare()

◆ getAbsoluteColumnIndex()

◆ getAbsoluteColumnIndices()

◆ getAbsoluteRowIndex()

◆ getAbsoluteRowIndices()

◆ getColumnKey()

◆ getNumberOfColumnBlocks()

◆ getNumberOfRowBlocks()

◆ getRelativeColumnIndex()

◆ getRelativeRowIndex()

◆ getRowKey()

◆ getSubMinorKey()

◆ operator<()

◆ operator=()

◆ operator==()

◆ reset()

◆ selectFirstColumns()

◆ selectFirstRows()

◆ selectNextColumns()

◆ selectNextRows()

◆ set()

◆ setColumnKey()

◆ setRowKey()

◆ toString()

Friends And Related Function Documentation

◆ MinorProcessor

Field Documentation

◆ _columnKey

◆ _numberOfColumnBlocks

◆ _numberOfRowBlocks

◆ _rowKey