Changeset 68ec38 in git for Singular/Minor.cc


Ignore:
Timestamp:
Feb 2, 2010, 2:22:24 PM (14 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
Children:
13e38971987d79bd6f926205a82e193ea34b07bd
Parents:
13d171b75aff221780f5e6852dfb845024c5771b
Message:
documentation and style guide conformance

git-svn-id: file:///usr/local/Singular/svn/trunk@12501 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/Minor.cc

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