Changeset 68ec38 in git for Singular/Minor.h


Ignore:
Timestamp:
Feb 2, 2010, 2:22:24 PM (14 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')
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.h

    r13d171b r68ec38  
    1212    sub-determinantes; see class Cache.
    1313
    14     As such, it is a realization of the template class KeyClass which is used in
    15     the declaration of class Cache. Following the documentation of class Cache, we
    16     need to implement at least the methods:<br>
     14    As such, it is a realization of the template class KeyClass which is used
     15    in the declaration of class Cache. Following the documentation of class
     16    Cache, we need to implement at least the methods:<br>
    1717    <c>bool MinorKey::operator< (const MinorKey& key),</c><br>
    1818    <c>bool MinorKey::operator== (const MinorKey& key),</c><br>
    19     MinorKey uses two private arrays of ints \c _rowKey and \c _columnKey to encode rows and
    20     columns of a pre-defined matrix. Semantically, the row indices and column indices form the key
    21     for caching the value of the corresponding minor.<br>
    22     More concretely, let us assume that the pre-defined matrix has <em>32*R+r, r<32,</em> rows and
    23     <em>32*C+c, c<32,</em> columns. All row indices can then be captured using R+1 ints, since
    24     an int is a 32-bit-number (regardless of the platform). The analog holds for the columns. Consequently, each instance of MinorKey
    25     encodes the sets of rows and columns which shall belong to the minor of interest (and which shall not).<br>
    26     Example: The \c _rowKey with \c _rowKey[1] = 0...011 and \c _rowKey[0] = 0...01101 encodes the rows with
    27     indices 33, 32, 3, 2, and 0.
     19    MinorKey uses two private arrays of ints \c _rowKey and \c _columnKey to
     20    encode rows and columns of a pre-defined matrix. Semantically, the row
     21    indices and column indices form the key for caching the value of the
     22    corresponding minor.<br>
     23    More concretely, let us assume that the pre-defined matrix has
     24    <em>32*R+r, r<32,</em> rows and <em>32*C+c, c<32,</em> columns. All row
     25    indices can then be captured using R+1 ints, since an int is a
     26    32-bit-number (regardless of the platform). The analog holds for the
     27    columns. Consequently, each instance of MinorKey encodes the sets of rows
     28    and columns which shall belong to the minor of interest (and which shall
     29    not).<br>
     30    Example: The \c _rowKey with \c _rowKey[1] = 0...011 and
     31    \c _rowKey[0] = 0...01101 encodes the rows with indices 33, 32, 3, 2,
     32    and 0.
    2833    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
    2934*/
    30 class MinorKey {
    31       private:
    32              /**
    33              * a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which
    34              * rows of a pre-defined matrix shall belong to the minor of interest;
    35              * for i < j, _rowKey[i] holds lower bits than _rowKey[j]
    36              */
    37              unsigned int* _rowKey;
    38 
    39              /**
    40              * a pointer to an array[0..k-1] of ints, capturing k*32 bits for determining which
    41              * columns of a pre-defined matrix shall belong to the minor of interest;
    42              * for i < j, _columnKey[i] holds lower bits than _columnKey[j]
    43              */
    44              unsigned int* _columnKey;
    45 
    46              /**
    47              * the number of ints (i.e. 32-bit-numbers) we need to encode the set of rows;
    48              * If the higest row index is 70, we need 3 blocks of 32 bits to also encode the 70th bit.
    49              */
    50              int _numberOfRowBlocks;
    51 
    52              /**
    53              * the number of ints (i.e. 32-bit-numbers) we need to encode the set of columns;
    54              * If the higest column index is 70, we need 3 blocks of 32 bits to also encode the 70th bit.
    55              */
    56              int _numberOfColumnBlocks;
    57 
    58              /**
    59              * Inlined accessor of blockIndex-th element of _rowKey.
    60              * @param blockIndex the index of the int to be retrieved
    61              * @return an entry of _rowKey
    62              */
    63              unsigned int getRowKey (const int blockIndex) const;
    64 
    65              /**
    66              * Inlined accessor of blockIndex-th element of _columnKey.
    67              * @param blockIndex the index of the int to be retrieved
    68              * @return an entry of _columnKey
    69              */
    70              unsigned int getColumnKey (const int blockIndex) const;
    71 
    72              void setRowKey (const int blockIndex, const unsigned int rowKey);
    73 
    74              void setColumnKey (const int blockIndex, const unsigned int columnKey);
    75 
    76              /**
    77              * Inlined accessor of _numberOfRowBlocks.
    78              * @return the number of 32-bit-blocks needed to encode all rows of the minor as a sequence of bits
    79              */
    80              int getNumberOfRowBlocks () const;
    81 
    82              /**
    83              * Inlined accessor of _numberOfColumnBlocks.
    84              * @return the number of 32-bit-blocks needed to encode all columns of the minor as a sequence of bits
    85              */
    86              int getNumberOfColumnBlocks () const;
    87 
    88              void reset();
    89 
    90              // just for debugging
    91              int getSetBits(const int a) const;
    92 
    93              friend class MinorProcessor;
    94       public:
    95              /**
    96              * A constructor for class MinorKey.
    97              * The ints given in the array rowKey encode all rows which shall belong to the minor.
    98              * Each array entry encodes 32 rows, e.g. the i-th array entry 0...01101 encodes the rows with
    99              * absolute matrix row indices 3+i*32, 2+i*32, and 0+i*32. Analog for columns.
    100              * @param lengthOfRowArray the length of the array rowKey
    101              * @param rowKey a pointer to an array of ints encoding the set of rows of the minor
    102              * @param lengthOfColumnArray the length of the array columnKey
    103              * @param columnKey a pointer to an array of ints encoding the set of columns of the minor
    104              */
    105              MinorKey (const int lengthOfRowArray = 0, const unsigned int* const rowKey = 0,
    106                        const int lengthOfColumnArray = 0, const unsigned int* const columnKey = 0);
    107 
    108              /**
    109              * A setter method for class MinorKey.
    110              * Just like the constructor of this class, this method will set all private
    111              * fields according to the given parameters. Note that this method will change the given
    112              * instance of MinorKey.
    113              * @param lengthOfRowArray the length of the array rowKey
    114              * @param rowKey a pointer to an array of ints encoding the set of rows of the minor
    115              * @param lengthOfColumnArray the length of the array columnKey
    116              * @param columnKey a pointer to an array of ints encoding the set of columns of the minor
    117              * @see MinorKey::MinorKey (const int lengthOfRowArray, const int* rowKey, const int lengthOfColumnArray, const int* columnKey)
    118              */
    119              void set(const int lengthOfRowArray, const unsigned int* rowKey,
    120                       const int lengthOfColumnArray, const unsigned int* columnKey);
    121 
    122              /**
    123              * A copy constructor.
    124              * This method overrides the shallow copy constructor by a self-written deep copy version.
    125              * @param mk the MinorKey to be deep copied
    126              */
    127              MinorKey (const MinorKey& mk);
    128 
    129              /**
    130              * A destructor for deleting an instance.
    131              */
    132              ~MinorKey ();
    133 
    134              // just to make the compiler happy
    135              MinorKey& operator=(const MinorKey&);
    136              
    137              // just to make the compiler happy
    138              bool operator==(const MinorKey&) const;
    139 
    140              // just to make the compiler happy
    141              bool operator<(const MinorKey&) const;
    142 
    143              /**
    144              * A method for retrieving the (0-based) index of the i-th row in the set of rows encoded in \a this.
    145              * Lower values for \c i result in lower absolute row indices.
    146              * \par Example:
    147              * Applied to the row pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted
    148              * from the right, i.e. 7.
    149              * \par Assertion
    150              * The method assumes that there are at least \c i rows encoded in the given MinorKey.
    151              * @param i the relative index of the row, as encoded in \a this
    152              * @return (0-based) absolute row index of the i-th row in \a this
    153              */
    154              int getAbsoluteRowIndex (const int i) const;
    155 
    156              /**
    157              * A method for retrieving the (0-based) index of the i-th column in the set of columns encoded in \a this.
    158              * Lower values for \c i result in lower absolute column indices.
    159              * \par Example:
    160              * Applied to the column pattern 10010001101 and i = 3, we get the 0-based index of the 3-rd set bit counted
    161              * from the right, i.e. 7.
    162              * \par Assertion
    163              * The method assumes that there are at least \c i columns encoded in the given MinorKey.
    164              * @param i the relative index of the column, as encoded in \a this
    165              * @return (0-based) absolute column index of the i-th row in \a this
    166              */
    167              int getAbsoluteColumnIndex (const int i) const;
    168 
    169              /**
    170              * A method for retrieving the (0-based) relative index of the i-th row in \a this MinorKey.
    171              * Lower values for \c i result in lower relative row indices. Note that the absolute index
    172              * \c i is 0-based, too.
    173              * \par Example:
    174              * Applied to the row pattern 10010001101 and i = 7, we get the relative 0-based position of the
    175              * bit representing the absolute index 7, i.e. 3.
    176              * \par Assertion
    177              * The method assumes that the bit which corresponds to the absolute index i is actually set.
    178              * @param i the absolute 0-based index of a row encoded in \a this
    179              * @return (0-based) relative row index corresponding to \c i
    180              */
    181              int getRelativeRowIndex (const int i) const;
    182 
    183              /**
    184              * A method for retrieving the (0-based) relative index of the i-th column in \a this MinorKey.
    185              * Lower values for \c i result in lower relative column indices. Note that the absolute index
    186              * \c i is 0-based, too.
    187              * \par Example:
    188              * Applied to the column pattern 10010001101 and i = 7, we get the relative 0-based position of the
    189              * bit representing the absolute index 7, i.e. 3.
    190              * \par Assertion
    191              * The method assumes that the bit which corresponds to the absolute index i is actually set.
    192              * @param i the absolute 0-based index of a column encoded in \a this
    193              * @return (0-based) relative column index corresponding to \c i
    194              */
    195              int getRelativeColumnIndex (const int i) const;
    196 
    197              /**
    198              * A method for retrieving the 0-based indices of all rows encoded in \a this MinorKey.
    199              * The user of this method needs to know the number of rows in \a this, in order to know which
    200              * indices in \c target[k] will be valid.
    201              * \par Example:
    202              * The bit pattern <c>0...01101</c> will give rise to the settings
    203              * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs to know in advance that
    204              * there are three rows in \a this MinorKey.
    205              * \par Assertion
    206              * The method assumes that target has enough positions for all rows encoded in \a this MinorKey.
    207              * @param target a pointer to some array of ints that is to be filled with the requested indices
    208              */
    209              void getAbsoluteRowIndices(int* const target) const;
    210 
    211              /**
    212              * A method for retrieving the 0-based indices of all columns encoded in \a this MinorKey.
    213              * The user of this method needs to know the number of columns in \a this, in order to know which
    214              * indices in \c target[k] will be valid.
    215              * \par Example:
    216              * The bit pattern <c>0...01101</c> will give rise to the settings
    217              * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs to know in advance that
    218              * there are three columns in \a this MinorKey.
    219              * \par Assertion
    220              * The method assumes that target has enough positions for all columns encoded in \a this MinorKey.
    221              * @param target a pointer to some array of ints that is to be filled with the requested indices
    222              */
    223              void getAbsoluteColumnIndices(int* const target) const;
    224 
    225              /**
    226              * A method for retrieving a sub-MinorKey resulting from omitting one row and one column
    227              * of \a this MinorKey.
    228              * \par Assertion
    229              * The method assumes that the row with absolute index \c absoluteEraseRowIndex (counted from lower bits
    230              * to higher bits) and the column with absolute index \c absoluteEraseColumnIndex are actually set in
    231              * \c mk.
    232              * @param absoluteEraseRowIndex the 0-based absolute index of a row in \a mk
    233              * @param absoluteEraseColumnIndex the 0-based absolute index of a column in \a mk
    234              * @return the MinorKey when omitting the specified row and column
    235              */
    236              MinorKey getSubMinorKey (const int absoluteEraseRowIndex,
    237                                       const int absoluteEraseColumnIndex) const;
    238 
    239              /**
    240              * A comparator for two instances of MinorKey.
    241              * The ordering induced by this implementation determines the ordering of all
    242              * (key --> value) pairs in a cache that uses MinorKey as KeyClass.
    243              * @param mk a second MinorKey to be compared with \a this instance
    244              * @return -1 iff \a this instance is smaller than \a mk; 0 for equality; +1 otherwise
    245              * @see MinorKey::operator== (const MinorKey&) const
    246              */
    247              int compare (const MinorKey& mk) const;
    248 
    249              /**
    250              * This method redefines the set of rows represented by \a this MinorKey.
    251              * After the method, the defined set of rows coincides with the lowest
    252              * \c k rows of \c mk. (Here, lowest means w.r.t. indices.)<br>
    253              * Note that the method modifies the given instance of MinorKey.
    254              * \par Assertion
    255              * It is assumed that \c mk represents at least \c k rows.
    256              * @param k the number of rows
    257              * @param mk the MinorKey from which to choose the lowest \c k rows
    258              * @see MinorKey::selectNextRows (const int k, const MinorKey& mk)
    259              */
    260              void selectFirstRows (const int k, const MinorKey& mk);
    261 
    262              /**
    263              * This method redefines the set of rows represented by \a this MinorKey.
    264              * Both the old and the new set of \c k rows are subsets of the rows
    265              * represented by \c mk. After the method, the defined set of rows is
    266              * the next sensible choice of \c k rows of \c mk. (Here, next means
    267              * the next w.r.t. the increasing index ordering on multi-indices of
    268              * natural numbers.)<br>
    269              * Note that the method modifies the given instance of MinorKey.
    270              * \par Assertion
    271              * It is assumed that \c mk represents at least \c k rows. Furthermore,
    272              * the method assumes that the old set of rows represented by \a this
    273              * is also a subset of the rows given by \c mk.
    274              * @param k the number of rows
    275              * @param mk the MinorKey from which to choose the lowest \c k rows
    276              * @return true iff there is a next choice of \c k rows
    277              * @see MinorKey::selectFirstRows (const int k, const MinorKey& mk)
    278              */
    279              bool selectNextRows (const int k, const MinorKey& mk);
    280 
    281              /**
    282              * This method redefines the set of columns represented by \a this MinorKey.
    283              * After the method, the defined set of columns coincides with the lowest
    284              * \c k columns of \c mk. (Here, lowest means w.r.t. indices.)<br>
    285              * Note that the method modifies the given instance of MinorKey.
    286              * \par Assertion
    287              * It is assumed that \c mk represents at least \c k columns.
    288              * @param k the number of columns
    289              * @param mk the MinorKey from which to choose the lowest \c k columns
    290              * @see MinorKey::selectNextColumns (const int k, const MinorKey& mk)
    291              */
    292              void selectFirstColumns (const int k, const MinorKey& mk);
    293 
    294              /**
    295              * This method redefines the set of columns represented by \a this MinorKey.
    296              * Both the old and the new set of \c k columns are subsets of the columns
    297              * represented by \c mk. After the method, the defined set of columns is
    298              * the next sensible choice of \c k columns of \c mk. (Here, next means
    299              * the next w.r.t. the increasing index ordering on multi-indices of
    300              * natural numbers.)<br>
    301              * Note that the method modifies the given instance of MinorKey.
    302              * \par Assertion
    303              * It is assumed that \c mk represents at least \c k columns. Furthermore,
    304              * the method assumes that the old set of columns represented by \a this
    305              * is also a subset of the columns given by \c mk.
    306              * @param k the number of columns
    307              * @param mk the MinorKey from which to choose the lowest \c k columns
    308              * @return true iff there is a next choice of \c k columns
    309              * @see MinorKey::selectFirstColumns (const int k, const MinorKey& mk)
    310              */
    311              bool selectNextColumns (const int k, const MinorKey& mk);
    312 
    313              /**
    314              * A method for providing a printable version of the represented MinorKey.
    315              * @return a printable version of the given instance as instance of class string
    316              */
    317              string toString () const;
    318 
    319              /**
    320              * A method for printing a string representation of the given MinorKey to std::cout.
    321              */
    322              void print () const;
     35class MinorKey
     36{
     37  private:
     38     /**
     39     * a pointer to an array[0..k-1] of ints, capturing k*32 bits for
     40     * determining which rows of a pre-defined matrix shall belong to the
     41     * minor of interest;
     42     * for i < j, _rowKey[i] holds lower bits than _rowKey[j]
     43     */
     44     unsigned int* _rowKey;
     45
     46     /**
     47     * a pointer to an array[0..k-1] of ints, capturing k*32 bits for
     48     * determining which columns of a pre-defined matrix shall belong to the
     49     * minor of interest;
     50     * for i < j, _columnKey[i] holds lower bits than _columnKey[j]
     51     */
     52     unsigned int* _columnKey;
     53
     54     /**
     55     * the number of ints (i.e. 32-bit-numbers) we need to encode the set of
     56     * rows;
     57     * If the higest row index is 70, we need 3 blocks of 32 bits to also
     58     * encode the 70th bit.
     59     */
     60     int _numberOfRowBlocks;
     61
     62     /**
     63     * the number of ints (i.e. 32-bit-numbers) we need to encode the set of
     64     * columns;
     65     * If the higest column index is 70, we need 3 blocks of 32 bits to also
     66     * encode the 70th bit.
     67     */
     68     int _numberOfColumnBlocks;
     69
     70     /**
     71     * Inlined accessor of blockIndex-th element of _rowKey.
     72     * @param blockIndex the index of the int to be retrieved
     73     * @return an entry of _rowKey
     74     */
     75     unsigned int getRowKey (const int blockIndex) const;
     76
     77     /**
     78     * Accessor of blockIndex-th element of _columnKey.
     79     * @param blockIndex the index of the int to be retrieved
     80     * @return an entry of _columnKey
     81     */
     82     unsigned int getColumnKey (const int blockIndex) const;
     83
     84     /**
     85     * A method for setting the blockIndex-th element of _rowKey.
     86     * @param blockIndex the index of the int to be retrieved
     87     * @param rowKey the row key to be set
     88     */
     89     void setRowKey (const int blockIndex, const unsigned int rowKey);
     90
     91     /**
     92     * A method for setting the blockIndex-th element of _columnKey.
     93     * @param blockIndex the index of the int to be retrieved
     94     * @param columnKey the column key to be set
     95     */
     96     void setColumnKey (const int blockIndex, const unsigned int columnKey);
     97
     98     /**
     99     * Accessor of _numberOfRowBlocks.
     100     * @return the number of 32-bit-blocks needed to encode all rows of the
     101     *         minor as a sequence of bits
     102     */
     103     int getNumberOfRowBlocks () const;
     104
     105     /**
     106     * Accessor of _numberOfColumnBlocks.
     107     * @return the number of 32-bit-blocks needed to encode all columns of
     108     *         the minor as a sequence of bits
     109     */
     110     int getNumberOfColumnBlocks () const;
     111
     112     /**
     113     * A method for deleting all entries of _rowKey and _columnKey.
     114     */
     115     void reset();
     116
     117     /**
     118     * A method for counting the number of set bits.
     119     * For a == 1, the number of set bits in _rowKey will be counted;
     120     * for a == 2 in _columnKey.
     121     * This method will only be called in the debug version.
     122     * @param a for controlling whether to count in _rowKey or _columnKey
     123     * @return the number of set bits either in _rowKey or _columnKey
     124     */
     125     int getSetBits (const int a) const;
     126
     127     /**
     128     * For letting MinorProcessor see the private methods of this class.
     129     */
     130     friend class MinorProcessor;
     131  public:
     132     /**
     133     * A constructor for class MinorKey.
     134     * The ints given in the array rowKey encode all rows which shall belong
     135     * to the minor. Each array entry encodes 32 rows, e.g. the i-th array
     136     * entry 0...01101 encodes the rows with absolute matrix row indices
     137     * 3+i*32, 2+i*32, and 0+i*32. Analog for columns.
     138     * @param lengthOfRowArray the length of the array rowKey
     139     * @param rowKey a pointer to an array of ints encoding the set of rows of
     140     *        the minor
     141     * @param lengthOfColumnArray the length of the array columnKey
     142     * @param columnKey a pointer to an array of ints encoding the set of
     143     +        columns of the minor
     144     */
     145     MinorKey (const int lengthOfRowArray = 0,
     146               const unsigned int* const rowKey = 0,
     147               const int lengthOfColumnArray = 0,
     148               const unsigned int* const columnKey = 0);
     149
     150     /**
     151     * A setter method for class MinorKey.
     152     * Just like the constructor of this class, this method will set all
     153     * private fields according to the given parameters. Note that this method
     154     * will change the given instance of MinorKey.
     155     * @param lengthOfRowArray the length of the array rowKey
     156     * @param rowKey a pointer to an array of ints encoding the set of rows of
     157     * the minor
     158     * @param lengthOfColumnArray the length of the array columnKey
     159     * @param columnKey a pointer to an array of ints encoding the set of
     160     *        columns of the minor
     161     * @see MinorKey::MinorKey (const int lengthOfRowArray, const int* rowKey,
     162                                const int lengthOfColumnArray,
     163                                const int* columnKey)
     164     */
     165     void set(const int lengthOfRowArray, const unsigned int* rowKey,
     166              const int lengthOfColumnArray, const unsigned int* columnKey);
     167
     168     /**
     169     * A copy constructor.
     170     * This method overrides the shallow copy constructor by a self-written
     171     * deep copy version.
     172     * @param mk the MinorKey to be deep copied
     173     */
     174     MinorKey (const MinorKey& mk);
     175
     176     /**
     177     * A destructor for deleting an instance.
     178     */
     179     ~MinorKey ();
     180
     181     /**
     182     * just to make the compiler happy
     183     */
     184     MinorKey& operator=(const MinorKey&);
     185     
     186     /**
     187     * just to make the compiler happy
     188     */
     189     bool operator==(const MinorKey&) const;
     190
     191     /**
     192     * just to make the compiler happy
     193     */
     194     bool operator<(const MinorKey&) const;
     195
     196     /**
     197     * A method for retrieving the (0-based) index of the i-th row in the set
     198     * of rows encoded in \a this.
     199     * Lower values for \c i result in lower absolute row indices.
     200     * \par Example:
     201     * Applied to the row pattern 10010001101 and i = 3, we get the 0-based
     202     * index of the 3-rd set bit counted from the right, i.e. 7.
     203     * \par Assertion
     204     * The method assumes that there are at least \c i rows encoded in the
     205     * given MinorKey.
     206     * @param i the relative index of the row, as encoded in \a this
     207     * @return (0-based) absolute row index of the i-th row in \a this
     208     */
     209     int getAbsoluteRowIndex (const int i) const;
     210
     211     /**
     212     * A method for retrieving the (0-based) index of the i-th column in the
     213     * set of columns encoded in \a this.
     214     * Lower values for \c i result in lower absolute column indices.
     215     * \par Example:
     216     * Applied to the column pattern 10010001101 and i = 3, we get the 0-based
     217     * index of the 3-rd set bit counted from the right, i.e. 7.
     218     * \par Assertion
     219     * The method assumes that there are at least \c i columns encoded in the
     220     * given MinorKey.
     221     * @param i the relative index of the column, as encoded in \a this
     222     * @return (0-based) absolute column index of the i-th row in \a this
     223     */
     224     int getAbsoluteColumnIndex (const int i) const;
     225
     226     /**
     227     * A method for retrieving the (0-based) relative index of the i-th row
     228     * in \a this MinorKey.
     229     * Lower values for \c i result in lower relative row indices. Note that
     230     * the absolute index \c i is 0-based, too.
     231     * \par Example:
     232     * Applied to the row pattern 10010001101 and i = 7, we get the relative
     233     * 0-based position of the bit representing the absolute index 7, i.e. 3.
     234     * \par Assertion
     235     * The method assumes that the bit which corresponds to the absolute index
     236     * i is actually set.
     237     * @param i the absolute 0-based index of a row encoded in \a this
     238     * @return (0-based) relative row index corresponding to \c i
     239     */
     240     int getRelativeRowIndex (const int i) const;
     241
     242     /**
     243     * A method for retrieving the (0-based) relative index of the i-th column
     244     * in \a this MinorKey.
     245     * Lower values for \c i result in lower relative column indices. Note that
     246     * the absolute index \c i is 0-based, too.
     247     * \par Example:
     248     * Applied to the column pattern 10010001101 and i = 7, we get the
     249     * relative 0-based position of the bit representing the absolute index 7,
     250     * i.e. 3.
     251     * \par Assertion
     252     * The method assumes that the bit which corresponds to the absolute index
     253     * i is actually set.
     254     * @param i the absolute 0-based index of a column encoded in \a this
     255     * @return (0-based) relative column index corresponding to \c i
     256     */
     257     int getRelativeColumnIndex (const int i) const;
     258
     259     /**
     260     * A method for retrieving the 0-based indices of all rows encoded in \a
     261     * this MinorKey.
     262     * The user of this method needs to know the number of rows in \a this,
     263     * in order to know which indices in \c target[k] will be valid.
     264     * \par Example:
     265     * The bit pattern <c>0...01101</c> will give rise to the settings
     266     * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs
     267     * to know in advance that there are three rows in \a this MinorKey.
     268     * \par Assertion
     269     * The method assumes that target has enough positions for all rows
     270     * encoded in \a this MinorKey.
     271     * @param target a pointer to some array of ints that is to be filled with
     272     *        the requested indices
     273     */
     274     void getAbsoluteRowIndices(int* const target) const;
     275
     276     /**
     277     * A method for retrieving the 0-based indices of all columns encoded in
     278     * \a this MinorKey.
     279     * The user of this method needs to know the number of columns in \a this,
     280     * in order to know which indices in \c target[k] will be valid.
     281     * \par Example:
     282     * The bit pattern <c>0...01101</c> will give rise to the settings
     283     * <c>target[0] = 0, target[1] = 2, target[2] = 3</c>, and the user needs
     284     * to know in advance that there are three columns in \a this MinorKey.
     285     * \par Assertion
     286     * The method assumes that target has enough positions for all columns
     287     * encoded in \a this MinorKey.
     288     * @param target a pointer to some array of ints that is to be filled
     289     *        with the requested indices
     290     */
     291     void getAbsoluteColumnIndices(int* const target) const;
     292
     293     /**
     294     * A method for retrieving a sub-MinorKey resulting from omitting one row
     295     * and one column of \a this MinorKey.
     296     * \par Assertion
     297     * The method assumes that the row with absolute index
     298     * \c absoluteEraseRowIndex (counted from lower bits to higher bits) and
     299     * the column with absolute index \c absoluteEraseColumnIndex are actually
     300     * set in \c mk.
     301     * @param absoluteEraseRowIndex the 0-based absolute index of a row in
     302     *        \a mk
     303     * @param absoluteEraseColumnIndex the 0-based absolute index of a column
     304     *        in \a mk
     305     * @return the MinorKey when omitting the specified row and column
     306     */
     307     MinorKey getSubMinorKey (const int absoluteEraseRowIndex,
     308                              const int absoluteEraseColumnIndex) const;
     309
     310     /**
     311     * A comparator for two instances of MinorKey.
     312     * The ordering induced by this implementation determines the ordering of
     313     * all (key --> value) pairs in a cache that uses MinorKey as KeyClass.
     314     * @param mk a second MinorKey to be compared with \a this instance
     315     * @return -1 iff \a this instance is smaller than \a mk; 0 for equality;
     316     *         +1 otherwise
     317     * @see MinorKey::operator== (const MinorKey&) const
     318     */
     319     int compare (const MinorKey& mk) const;
     320
     321     /**
     322     * This method redefines the set of rows represented by \a this MinorKey.
     323     * After the method, the defined set of rows coincides with the lowest
     324     * \c k rows of \c mk. (Here, lowest means w.r.t. indices.)<br>
     325     * Note that the method modifies the given instance of MinorKey.
     326     * \par Assertion
     327     * It is assumed that \c mk represents at least \c k rows.
     328     * @param k the number of rows
     329     * @param mk the MinorKey from which to choose the lowest \c k rows
     330     * @see MinorKey::selectNextRows (const int k, const MinorKey& mk)
     331     */
     332     void selectFirstRows (const int k, const MinorKey& mk);
     333
     334     /**
     335     * This method redefines the set of rows represented by \a this MinorKey.
     336     * Both the old and the new set of \c k rows are subsets of the rows
     337     * represented by \c mk. After the method, the defined set of rows is
     338     * the next sensible choice of \c k rows of \c mk. (Here, next means
     339     * the next w.r.t. the increasing index ordering on multi-indices of
     340     * natural numbers.)<br>
     341     * Note that the method modifies the given instance of MinorKey.
     342     * \par Assertion
     343     * It is assumed that \c mk represents at least \c k rows. Furthermore,
     344     * the method assumes that the old set of rows represented by \a this
     345     * is also a subset of the rows given by \c mk.
     346     * @param k the number of rows
     347     * @param mk the MinorKey from which to choose the lowest \c k rows
     348     * @return true iff there is a next choice of \c k rows
     349     * @see MinorKey::selectFirstRows (const int k, const MinorKey& mk)
     350     */
     351     bool selectNextRows (const int k, const MinorKey& mk);
     352
     353     /**
     354     * This method redefines the set of columns represented by \a this
     355     * MinorKey.
     356     * After the method, the defined set of columns coincides with the lowest
     357     * \c k columns of \c mk. (Here, lowest means w.r.t. indices.)<br>
     358     * Note that the method modifies the given instance of MinorKey.
     359     * \par Assertion
     360     * It is assumed that \c mk represents at least \c k columns.
     361     * @param k the number of columns
     362     * @param mk the MinorKey from which to choose the lowest \c k columns
     363     * @see MinorKey::selectNextColumns (const int k, const MinorKey& mk)
     364     */
     365     void selectFirstColumns (const int k, const MinorKey& mk);
     366
     367     /**
     368     * This method redefines the set of columns represented by \a this
     369     * MinorKey.
     370     * Both the old and the new set of \c k columns are subsets of the columns
     371     * represented by \c mk. After the method, the defined set of columns is
     372     * the next sensible choice of \c k columns of \c mk. (Here, next means
     373     * the next w.r.t. the increasing index ordering on multi-indices of
     374     * natural numbers.)<br>
     375     * Note that the method modifies the given instance of MinorKey.
     376     * \par Assertion
     377     * It is assumed that \c mk represents at least \c k columns. Furthermore,
     378     * the method assumes that the old set of columns represented by \a this
     379     * is also a subset of the columns given by \c mk.
     380     * @param k the number of columns
     381     * @param mk the MinorKey from which to choose the lowest \c k columns
     382     * @return true iff there is a next choice of \c k columns
     383     * @see MinorKey::selectFirstColumns (const int k, const MinorKey& mk)
     384     */
     385     bool selectNextColumns (const int k, const MinorKey& mk);
     386
     387     /**
     388     * A method for providing a printable version of the represented MinorKey.
     389     * @return a printable version of the given instance as instance of class
     390     * string
     391     */
     392     string toString () const;
     393
     394     /**
     395     * A method for printing a string representation of the given MinorKey to
     396     * std::cout.
     397     */
     398     void print () const;
    323399};
    324400
    325 class MinorValue {
    326       protected:
    327              /**
    328              * -1 iff cache is not used, otherwise the number of retrievals so far of the current minor
    329              */
    330              int _retrievals;
    331 
    332              /**
    333              * // -1 iff cache is not used, otherwise the maximum number of potential retrievals of
    334              * this minor (e.g. when the minor would be kept in cache forever)
    335              */
    336              int _potentialRetrievals;
    337 
    338              /**
    339              * a store for the actual number of multiplications to compute the current minor
    340              */
    341              int _multiplications;
    342 
    343              /**
    344              * a store for the actual number of additions to compute the current minor
    345              */
    346              int _additions;
    347 
    348              /**
    349              * a store for the accumulated number of multiplications to compute the current minor;
    350              * This also includes all multiplications nested in sub-minors which may be retrieved
    351              * from a cache. (Thus, these nested operations do not need to be performed again.)
    352              */
    353              int _accumulatedMult;
    354 
    355              /**
    356              * a store for the accumulated number of additions to compute the current minor;
    357              * This also includes all additions nested in sub-minors which may be retrieved
    358              * from a cache. (Thus, these nested operations do not need to be performed again.)
    359              */
    360              int _accumulatedSum;
    361 
    362              /**
    363              * A method for obtaining a rank measure for the given MinorValue.<br>
    364              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    365              * on MinorValues has an impact on the caching behaviour in a given cache: Greater
    366              * MinorValues will be cached longer than lower ones.<br>
    367              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    368              * will be cached longer when caching strategy 1 is deployed.<br>
    369              * Rank measure 1 is equal to the number of actually performed multiplications to compute \a mv.
    370              * @return an integer rank measure of \c this
    371              * @see MinorValue::operator< (const MinorValue& mv)
    372              */
    373              int rankMeasure1 () const;
    374 
    375              /**
    376              * A method for obtaining a rank measure for the given MinorValue.<br>
    377              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    378              * on MinorValues has an impact on the caching behaviour in a given cache: Greater
    379              * MinorValues will be cached longer than lower ones.<br>
    380              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    381              * will be cached longer when caching strategy 1 is deployed.<br>
    382              * Rank measure 2 is equal to the number of accumulated multiplications to compute the given MinorValue.
    383              * This also includes all nested multiplications which were performed to compute all
    384              * sub-minors which could be reused from cache.
    385              * @return an integer rank measure of \c this
    386              * @see MinorValue::operator< (const MinorValue& mv)
    387              */
    388              int rankMeasure2 () const;
    389 
    390              /**
    391              * A method for obtaining a rank measure for the given MinorValue.<br>
    392              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    393              * on MinorValues has an impact on the caching behaviour in a given cache: Greater
    394              * MinorValues will be cached longer than lower ones.<br>
    395              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    396              * will be cached longer when caching strategy 1 is deployed.<br>
    397              * Rank measure 3 is equal to the number of actually performed multiplications, weighted
    398              * with the ratio of not yet performed retrievals over the maximum number of retrievals.
    399              * @return an integer rank measure of \c this
    400              * @see MinorValue::operator< (const MinorValue& mv)
    401              */
    402              int rankMeasure3 () const;
    403 
    404              /**
    405              * A method for obtaining a rank measure for the given MinorValue.<br>
    406              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    407              * on MinorValues has an impact on the caching behaviour in a given cache: Greater
    408              * MinorValues will be cached longer than lower ones.<br>
    409              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    410              * will be cached longer when caching strategy 1 is deployed.<br>
    411              * Rank measure 4 is equal to the number of actually performed multiplications, multiplied
    412              * with the number of not yet performed retrievals.
    413              * @return an integer rank measure of \c this
    414              * @see MinorValue::operator< (const MinorValue& mv)
    415              */
    416              int rankMeasure4 () const;
    417 
    418              /**
    419              * A method for obtaining a rank measure for the given MinorValue.<br>
    420              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    421              * on MinorValues has an impact on the caching behaviour in a given cache: Greater
    422              * MinorValues will be cached longer than lower ones.<br>
    423              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    424              * will be cached longer when caching strategy 1 is deployed.<br>
    425              * Rank measure 5 is equal to the number of not yet performed retrievals. This strategy tends
    426              * to cache MinorValues longer which have a high maximum number of potential retrievals.
    427              * @return an integer rank measure of \c this
    428              * @see MinorValue::operator< (const MinorValue& mv)
    429              */
    430              int rankMeasure5 () const;
    431 
    432              /**
    433              * private store for the current value ranking strategy;
    434              * This member can be set using MinorValue::SetRankingStrategy (const int).
    435              */
    436              static int _RankingStrategy;
    437 
    438              /**
    439              * Inlined accessor for the static private field _RankingStrategy.
    440              */
    441              static int GetRankingStrategy();
    442       public:
    443              // just to make the compiler happy
    444              bool operator== (const MinorValue& mv) const;
    445 
    446              // just to make the compiler happy
    447              bool operator< (const MinorValue& mv) const;
    448 
    449              /**
    450              * A method for retrieving the weight of a given MinorValue.
    451              * The implementation of Cache uses this function to determine the total
    452              * weight of an entire cache. As the user can instantiate Cache by
    453              * determining its maximum total weight (see Cache::Cache(const int, const int)),
    454              * the definition of weight of a MinorValue
    455              * may have an impact on the behaviour of the cache.
    456              * @return the weight of a given instance of MinorValue
    457              * @see Cache::getWeight () const
    458              */
    459              virtual int getWeight () const;
    460 
    461              /**
    462              * A method for accessing the number of retrievals of this minor. Multiple retrievals will
    463              * occur when computing large minors by means of cached sub-minors. (Then, the latter ones
    464              * may be retrieved multiple times.)
    465              * @return the number of retrievals of this minor
    466              * @see MinorValue::getPotentialRetrievals () const
    467              */
    468              int getRetrievals () const;
    469 
    470              /**
    471              * A method for accessing the maximum number of potential retrievals of this minor.
    472              * Multiple retrievals will
    473              * occur when computing large minors by means of cached sub-minors. (Then, the latter ones
    474              * may be retrieved multiple times.)
    475              * @return the maximum number of potential retrievals of this minor
    476              * @see MinorValue::getRetrievals () const
    477              */
    478              int getPotentialRetrievals () const;
    479 
    480              /**
    481              * A method for accessing the multiplications performed while computing this minor.
    482              * Due to multiplication with zero entries of the underlying matrix, some sub-minors
    483              * may be irrelevant. In this case, the multiplications needed to compute these sub-minors
    484              * will not be counted (, as they need not be performed).
    485              * Moreover, multiplications that were needed to compute cached sub-minors will not be counted
    486              * either, as the value of those sub-minors can be directly retrieved from the cache.
    487              * @return the number of multiplications performed
    488              * @see MinorValue::getAccumulatedMultiplications () const
    489              */
    490              int getMultiplications () const;
    491 
    492              /**
    493              * A method for accessing the multiplications performed while computing this minor, including
    494              * all nested multiplications.
    495              * Contrary to MinorValue::getMultiplications () const, this method will also count multiplications
    496              * needed to compute all cached sub-minors (, although they need not be performed again in order to
    497              * compute the given instance of MinorValue).
    498              * @return the number of multiplications performed, including nested multiplications
    499              * @see MinorValue::getMultiplications () const
    500              */
    501              int getAccumulatedMultiplications () const;
    502 
    503              /**
    504              * A method for accessing the additions performed while computing this minor.
    505              * Additions that were needed to compute cached sub-minors will not be counted,
    506              * as the value of those sub-minors can be directly retrieved from the cache.
    507              * @return the number of additions performed
    508              * @see MinorValue::getAccumulatedAdditions () const
    509              */
    510              int getAdditions () const;
    511 
    512              /**
    513              * A method for accessing the additions performed while computing this minor, including
    514              * all nested additions.
    515              * Contrary to MinorValue::getAdditions () const, this method will also count additions
    516              * needed to compute all cached sub-minors (, although they need not be performed again in order to
    517              * compute the given instance of MinorValue).
    518              * @return the number of additions performed, including nested additions
    519              * @see MinorValue::getAdditions () const
    520              */
    521              int getAccumulatedAdditions () const;
    522 
    523              /**
    524              * A method for incrementing the number of performed retrievals of \a this instance of MinorValue.<br>
    525              * Note that, when calling MinorValue::incrementRetrievals () for some instance \a mv of MinorValue
    526              * which has been cached in a Cache under MinorKey \a mk, the user should be careful:
    527              * After incrementing the number of retrievals for \a mv, the user should always
    528              * put the value again into cache, i.e. should perform Cache::put (const KeyClass&, const ValueClass&)
    529              * with \a mk and the modified \a mv as arguments. This is due to the fact that changing the number of
    530              * performed retrievals of a MinorValue may have an impact on its ranking in Cache. Only by calling
    531              * Cache::put (const KeyClass&, const ValueClass&) can the user ensure that the pair (\a mk --> \a mv)
    532              * will be correctly re-positioned within the Cache.
    533              */
    534              void incrementRetrievals ();
    535 
    536              /**
    537              * A method for obtaining a rank measure for theiven MinorValue.<br>
    538              * Rank measures are used to compare any two instances of MinorValue. The induced ordering
    539              * on MinorValues has an impact on the caching behaviour of the underlying cache: Greater
    540              * MinorValues will be cached longer than lower ones.<br>
    541              * More explicitely, this means: Make the return value of this method greater, and the given MinorValue
    542              * will be cached longer.<br>
    543              * Internally, this method will call one of several implementations, depending on the pre-defined
    544              * caching strategy; see MinorProcessor::SetCacheStrategy (const int).
    545              * @return an integer rank measure of \c this
    546              * @see MinorValue::operator< (const MinorValue& mv)
    547              * @see MinorProcessor::SetCacheStrategy (const int)
    548              */
    549              int getUtility () const;
    550 
    551              /**
    552              * A method for determining the value ranking strategy.<br>
    553              * This setting has a direct effect on how long the given MinorValue
    554              * will be cached in any cache that uses MinorValue to represent its
    555              * cached values.
    556              * @param rankingStrategy an int, so far one of 1, 2, ..., 5
    557              */
    558              static void SetRankingStrategy (const int rankingStrategy);
    559 
    560              /**
    561              * A method for providing a printable version of the represented MinorValue.
    562              * @return a printable version of the given instance as instance of class string
    563              */
    564              virtual string toString () const;
    565 
    566              /**
    567              * A method for printing a string representation of the given MinorValue to std::cout.
    568              */
    569              void print () const;
     401class MinorValue
     402{
     403  protected:
     404    /**
     405    * -1 iff cache is not used, otherwise the number of retrievals so far of
     406    * the current minor
     407    */
     408    int _retrievals;
     409   
     410    /**
     411    * -1 iff cache is not used, otherwise the maximum number of potential
     412    * retrievals of this minor (e.g. when the minor would be kept in cache
     413    * forever)
     414    */
     415    int _potentialRetrievals;
     416   
     417    /**
     418    * a store for the actual number of multiplications to compute the current
     419    * minor
     420    */
     421    int _multiplications;
     422   
     423    /**
     424    * a store for the actual number of additions to compute the current minor
     425    */
     426    int _additions;
     427   
     428    /**
     429    * a store for the accumulated number of multiplications to compute the
     430    * current minor;
     431    * This also includes all multiplications nested in sub-minors which may be
     432    * retrieved from a cache. (Thus, these nested operations do not need to be
     433    * performed again.)
     434    */
     435    int _accumulatedMult;
     436   
     437    /**
     438    * a store for the accumulated number of additions to compute the current
     439    * minor;
     440    * This also includes all additions nested in sub-minors which may be
     441    * retrieved from a cache. (Thus, these nested operations do not need to be
     442    * performed again.)
     443    */
     444    int _accumulatedSum;
     445   
     446    /**
     447    * A method for obtaining a rank measure for the given MinorValue.<br>
     448    * Rank measures are used to compare any two instances of MinorValue. The
     449    * induced ordering
     450    * on MinorValues has an impact on the caching behaviour in a given cache:
     451    * Greater MinorValues will be cached longer than lower ones.<br>
     452    * More explicitely, this means: Make the return value of this method
     453    * greater, and the given MinorValue will be cached longer when caching
     454    * strategy 1 is deployed.<br>
     455    * Rank measure 1 is equal to the number of actually performed
     456    * multiplications to compute \a mv.
     457    * @return an integer rank measure of \c this
     458    * @see MinorValue::operator< (const MinorValue& mv)
     459    */
     460    int rankMeasure1 () const;
     461   
     462    /**
     463    * A method for obtaining a rank measure for the given MinorValue.<br>
     464    * Rank measures are used to compare any two instances of MinorValue. The
     465    * induced ordering on MinorValues has an impact on the caching behaviour
     466    * in a given cache: Greater MinorValues will be cached longer than lower
     467    * ones.<br>
     468    * More explicitely, this means: Make the return value of this method
     469    * greater, and the given MinorValue will be cached longer when caching
     470    * strategy 1 is deployed.<br>
     471    * Rank measure 2 is equal to the number of accumulated multiplications to
     472    * compute the given MinorValue. This also includes all nested
     473    * multiplications which were performed to compute all sub-minors which
     474    * could be reused from cache.
     475    * @return an integer rank measure of \c this
     476    * @see MinorValue::operator< (const MinorValue& mv)
     477    */
     478    int rankMeasure2 () const;
     479   
     480    /**
     481    * A method for obtaining a rank measure for the given MinorValue.<br>
     482    * Rank measures are used to compare any two instances of MinorValue. The
     483    * induced ordering on MinorValues has an impact on the caching behaviour
     484    * in a given cache: Greater MinorValues will be cached longer than lower
     485    * ones.<br>
     486    * More explicitely, this means: Make the return value of this method
     487    * greater, and the given MinorValue will be cached longer when caching
     488    * strategy 1 is deployed.<br>
     489    * Rank measure 3 is equal to the number of actually performed
     490    * multiplications, weighted with the ratio of not yet performed retrievals
     491    * over the maximum number of retrievals.
     492    * @return an integer rank measure of \c this
     493    * @see MinorValue::operator< (const MinorValue& mv)
     494    */
     495    int rankMeasure3 () const;
     496   
     497    /**
     498    * A method for obtaining a rank measure for the given MinorValue.<br>
     499    * Rank measures are used to compare any two instances of MinorValue. The
     500    * induced ordering on MinorValues has an impact on the caching behaviour
     501    * in a given cache: Greater MinorValues will be cached longer than lower
     502    * ones.<br>
     503    * More explicitely, this means: Make the return value of this method
     504    * greater, and the given MinorValue will be cached longer when caching
     505    * strategy 1 is deployed.<br>
     506    * Rank measure 4 is equal to the number of actually performed
     507    * multiplications, multiplied with the number of not yet performed
     508    * retrievals.
     509    * @return an integer rank measure of \c this
     510    * @see MinorValue::operator< (const MinorValue& mv)
     511    */
     512    int rankMeasure4 () const;
     513   
     514    /**
     515    * A method for obtaining a rank measure for the given MinorValue.<br>
     516    * Rank measures are used to compare any two instances of MinorValue. The
     517    * induced ordering on MinorValues has an impact on the caching behaviour
     518    * in a given cache: Greater MinorValues will be cached longer than lower
     519    * ones.<br>
     520    * More explicitely, this means: Make the return value of this method
     521    * greater, and the given MinorValue will be cached longer when caching
     522    * strategy 1 is deployed.<br>
     523    * Rank measure 5 is equal to the number of not yet performed retrievals.
     524    * This strategy tends to cache MinorValues longer which have a high
     525    * maximum number of potential retrievals.
     526    * @return an integer rank measure of \c this
     527    * @see MinorValue::operator< (const MinorValue& mv)
     528    */
     529    int rankMeasure5 () const;
     530   
     531    /**
     532    * private store for the current value ranking strategy;
     533    * This member can be set using MinorValue::SetRankingStrategy (const int).
     534    */
     535    static int _RankingStrategy;
     536   
     537    /**
     538    * Accessor for the static private field _RankingStrategy.
     539    */
     540    static int GetRankingStrategy();
     541  public:
     542    /**
     543    * just to make the compiler happy
     544    */
     545    bool operator== (const MinorValue& mv) const;
     546   
     547    /**
     548    * just to make the compiler happy
     549    */
     550    bool operator< (const MinorValue& mv) const;
     551   
     552    /**
     553    * A method for retrieving the weight of a given MinorValue.
     554    * The implementation of Cache uses this function to determine the total
     555    * weight of an entire cache. As the user can instantiate Cache by
     556    * determining its maximum total weight
     557    * (see Cache::Cache(const int, const int)),
     558    * the definition of weight of a MinorValue
     559    * may have an impact on the behaviour of the cache.
     560    * @return the weight of a given instance of MinorValue
     561    * @see Cache::getWeight () const
     562    */
     563    virtual int getWeight () const;
     564   
     565    /**
     566    * A method for accessing the number of retrievals of this minor. Multiple
     567    * retrievals will occur when computing large minors by means of cached
     568    * sub-minors. (Then, the latter ones may be retrieved multiple times.)
     569    * @return the number of retrievals of this minor
     570    * @see MinorValue::getPotentialRetrievals () const
     571    */
     572    int getRetrievals () const;
     573   
     574    /**
     575    * A method for accessing the maximum number of potential retrievals of
     576    * this minor. Multiple retrievals will occur when computing large minors
     577    * by means of cached sub-minors. (Then, the latter ones may be retrieved
     578    * multiple times.)
     579    * @return the maximum number of potential retrievals of this minor
     580    * @see MinorValue::getRetrievals () const
     581    */
     582    int getPotentialRetrievals () const;
     583   
     584    /**
     585    * A method for accessing the multiplications performed while computing
     586    * this minor.
     587    * Due to multiplication with zero entries of the underlying matrix, some
     588    * sub-minors may be irrelevant. In this case, the multiplications needed
     589    * to compute these sub-minors will not be counted (, as they need not be
     590    * performed).
     591    * Moreover, multiplications that were needed to compute cached sub-minors
     592    * will not be counted either, as the value of those sub-minors can be
     593    * directly retrieved from the cache.
     594    * @return the number of multiplications performed
     595    * @see MinorValue::getAccumulatedMultiplications () const
     596    */
     597    int getMultiplications () const;
     598   
     599    /**
     600    * A method for accessing the multiplications performed while computing
     601    * this minor, including all nested multiplications.
     602    * Contrary to MinorValue::getMultiplications () const, this method will
     603    * also count multiplications needed to compute all cached sub-minors
     604    * (, although they need not be performed again in order to compute the
     605    * given instance of MinorValue).
     606    * @return the number of multiplications performed, including nested
     607    *         multiplications
     608    * @see MinorValue::getMultiplications () const
     609    */
     610    int getAccumulatedMultiplications () const;
     611   
     612    /**
     613    * A method for accessing the additions performed while computing this
     614    * minor.
     615    * Additions that were needed to compute cached sub-minors will not be
     616    * counted, as the value of those sub-minors can be directly retrieved
     617    * from the cache.
     618    * @return the number of additions performed
     619    * @see MinorValue::getAccumulatedAdditions () const
     620    */
     621    int getAdditions () const;
     622
     623    /**
     624    * A method for accessing the additions performed while computing this
     625    * minor, including all nested additions.
     626    * Contrary to MinorValue::getAdditions () const, this method will also
     627    * count additions needed to compute all cached sub-minors (, although
     628    * they need not be performed again in order to compute the given instance
     629    * of MinorValue).
     630    * @return the number of additions performed, including nested additions
     631    * @see MinorValue::getAdditions () const
     632    */
     633    int getAccumulatedAdditions () const;
     634   
     635    /**
     636    * A method for incrementing the number of performed retrievals of \a this
     637    * instance of MinorValue.<br>
     638    * Note that, when calling MinorValue::incrementRetrievals () for some
     639    * instance \a mv of MinorValue which has been cached in a Cache under
     640    * MinorKey \a mk, the user should be careful: After incrementing the
     641    * number of retrievals for \a mv, the user should always put the value
     642    * again into cache, i.e. should perform
     643    * Cache::put (const KeyClass&, const ValueClass&)
     644    * with \a mk and the modified \a mv as arguments. This is due to the fact
     645    * that changing the number of performed retrievals of a MinorValue may
     646    * have an impact on its ranking in Cache. Only by calling
     647    * Cache::put (const KeyClass&, const ValueClass&) can the user ensure
     648    * that the pair (\a mk --> \a mv) will be correctly re-positioned within
     649    * the Cache.
     650    */
     651    void incrementRetrievals ();
     652   
     653    /**
     654    * A method for obtaining a rank measure for theiven MinorValue.<br>
     655    * Rank measures are used to compare any two instances of MinorValue. The
     656    * induced ordering on MinorValues has an impact on the caching behaviour
     657    * of the underlying cache: Greater MinorValues will be cached longer than
     658    * lower ones.<br>
     659    * More explicitely, this means: Make the return value of this method
     660    * greater, and the given MinorValue will be cached longer.<br>
     661    * Internally, this method will call one of several implementations,
     662    * depending on the pre-defined caching strategy; see
     663    * MinorProcessor::SetCacheStrategy (const int).
     664    * @return an integer rank measure of \c this
     665    * @see MinorValue::operator< (const MinorValue& mv)
     666    * @see MinorProcessor::SetCacheStrategy (const int)
     667    */
     668    int getUtility () const;
     669   
     670    /**
     671    * A method for determining the value ranking strategy.<br>
     672    * This setting has a direct effect on how long the given MinorValue
     673    * will be cached in any cache that uses MinorValue to represent its
     674    * cached values.
     675    * @param rankingStrategy an int, so far one of 1, 2, ..., 5
     676    */
     677    static void SetRankingStrategy (const int rankingStrategy);
     678   
     679    /**
     680    * A method for providing a printable version of the represented MinorValue.
     681    * @return a printable version of the given instance as instance of class
     682    *         string
     683    */
     684    virtual string toString () const;
     685   
     686    /**
     687    * A method for printing a string representation of the given MinorValue
     688    * to std::cout.
     689    */
     690    void print () const;
    570691};
    571692
    572693/*! \class IntMinorValue
    573     \brief Class IntMinorValue can be used for representing values in a cache for
    574     sub-determinantes; see class Cache.
    575 
    576     As such, it is a realization of the template class ValueClass which is used in
    577     the declaration of class Cache. Following the documentation of class Cache, we
    578     need to implement at least the methods:<br>
     694    \brief Class IntMinorValue is derived from MinorValue and can be used for
     695    representing values in a cache for sub-determinantes; see class Cache.
     696
     697    As such, it is a realization of the template class ValueClass which is
     698    used in the declaration of class Cache. Following the documentation of
     699    class Cache, we need to implement at least the methods:<br>
    579700    <c>bool IntMinorValue::operator< (const IntMinorValue& key),</c><br>
    580701    <c>bool IntMinorValue::operator== (const IntMinorValue& key),</c><br>
    581702    <c>int IntMinorValue::getWeight ().</c><br><br>
    582     The main purpose of IntMinorValue is to represent values of sub-determinantes of a pre-defined
    583     matrix. Class MinorKey is used to determine which rows and columns of this pre-defined matrix
    584     ought to belong to the respective sub-determinante of interest. So far, IntMinorValue is just
    585     an example implementation which assumes matrices with int entries, such that the result
    586     of any minor is again an int.<br>
    587     Besides capturing the actual value of a minor, IntMinorValue also has built-in facilities to
    588     count the number of additions and multiplications performed when computing a minor. These two
    589     counters, especially the latter, are important measures when we want to investigate the complexity
    590     of computing minors.<br>
    591     When used in a cache, each minor \e M (e.g. of size 3 x 3) may be used several times, e.g. when
    592     computing a larger minor (e.g. of size 6 x 6) which contains \e M. MinorValue offers functionality
    593     to also count the number of retrievals of \e M in such a computational context.
     703    The main purpose of IntMinorValue is to represent values of
     704    sub-determinantes of a pre-defined matrix. Class MinorKey is used to
     705    determine which rows and columns of this pre-defined matrix ought to
     706    belong to the respective sub-determinante of interest. So far,
     707    IntMinorValue is just an example implementation which assumes matrices
     708    with int entries, such that the result of any minor is again an int.
    594709    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
    595710*/
    596 class IntMinorValue : public MinorValue {
    597       private:
    598              /**
    599              * a store for the actual value of the minor
    600              */
    601              int _result;
    602       public:
    603              /**
    604              * A constructor for class MinorValue.
    605              * @param result the actual value of the represented minor
    606              * @param multiplications number of multiplications to compute \a this minor
    607              * @param additions number of additions to compute \a this minor
    608              * @param accumulatedMultiplications number of multiplications to compute \a this minor, including nested operations
    609              * @param accumulatedAdditions number of additions to compute \a this minor, including nested operations
    610              * @param retrievals number of times this minor has been retrieved from cache
    611              * @param potentialRetrievals maximum number of times this minor may be retrieved from cache
    612              */
    613              IntMinorValue (const int result, const int multiplications, const int additions,
    614                              const int accumulatedMultiplications, const int accumulatedAdditions,
    615                              const int retrievals, const int potentialRetrievals);
    616 
    617              IntMinorValue (const IntMinorValue& mv);
    618              
    619              // just to make the compiler happy
    620              IntMinorValue ();
    621              
    622              virtual ~IntMinorValue ();
    623              
    624              int getResult() const;
    625 
    626              int getWeight () const;
    627 
    628              /**
    629              * A method for providing a printable version of the represented MinorValue.
    630              * @return a printable version of the given instance as instance of class string
    631              */
    632              string toString () const;
     711class IntMinorValue : public MinorValue
     712{
     713  private:
     714    /**
     715    * a store for the actual value of the minor
     716    */
     717    int _result;
     718  public:
     719    /**
     720    * A constructor for class MinorValue.
     721    * @param result the actual value of the represented minor
     722    * @param multiplications number of multiplications to compute \a this
     723             minor
     724    * @param additions number of additions to compute \a this minor
     725    * @param accumulatedMultiplications number of multiplications to compute
     726             \a this minor, including nested operations
     727    * @param accumulatedAdditions number of additions to compute \a this minor,
     728             including nested operations
     729    * @param retrievals number of times this minor has been retrieved from
     730             cache
     731    * @param potentialRetrievals maximum number of times this minor may be
     732             retrieved from cache
     733    */
     734    IntMinorValue (const int result, const int multiplications,
     735                   const int additions,
     736                   const int accumulatedMultiplications,
     737                   const int accumulatedAdditions, const int retrievals,
     738                   const int potentialRetrievals);
     739
     740    /**
     741    * Copy constructor
     742    */
     743    IntMinorValue (const IntMinorValue& mv);
     744
     745    /**
     746    * just to make the compiler happy
     747    */
     748    IntMinorValue ();
     749
     750    /**
     751    * Destructor
     752    */
     753    virtual ~IntMinorValue ();
     754   
     755    /**
     756    * Accessor for the private field _result.
     757    * @result the result encoded in this class instance
     758    */
     759    int getResult() const;
     760   
     761    /**
     762    * Accessor for the current weight of this class instance.
     763    * @result the current weight of this class instance
     764    */
     765    int getWeight () const;
     766
     767    /**
     768    * A method for providing a printable version of the represented MinorValue.
     769    * @return a printable version of the given instance as instance of class
     770    * string
     771    */
     772    string toString () const;
    633773};
    634774
    635 class PolyMinorValue : public MinorValue {
    636       private:
    637              /**
    638              * a store for the actual value of the minor
    639              */
    640              poly _result;
    641       public:
    642              /**
    643              * A constructor for class MinorValue.
    644              * @param result the actual value of the represented minor
    645              * @param multiplications number of multiplications to compute \a this minor
    646              * @param additions number of additions to compute \a this minor
    647              * @param accumulatedMultiplications number of multiplications to compute \a this minor, including nested operations
    648              * @param accumulatedAdditions number of additions to compute \a this minor, including nested operations
    649              * @param retrievals number of times this minor has been retrieved from cache
    650              * @param potentialRetrievals maximum number of times this minor may be retrieved from cache
    651              */
    652              PolyMinorValue (const poly result, const int multiplications, const int additions,
    653                              const int accumulatedMultiplications, const int accumulatedAdditions,
    654                              const int retrievals, const int potentialRetrievals);
    655 
    656              PolyMinorValue (const PolyMinorValue& mv);
    657              
    658              /* deep copy */
    659              void operator= (const PolyMinorValue& mv);
    660 
    661              // just to make the compiler happy
    662              PolyMinorValue ();
    663              
    664              virtual ~PolyMinorValue ();
    665 
    666              poly getResult() const;
    667 
    668              int getWeight () const;
    669 
    670              /**
    671              * A method for providing a printable version of the represented MinorValue.
    672              * @return a printable version of the given instance as instance of class string
    673              */
    674              string toString () const;
     775/*! \class PolyMinorValue
     776    \brief Class PolyMinorValue is derived from MinorValue and can be used for
     777    representing values in a cache for sub-determinantes; see class Cache.
     778
     779    As such, it is a realization of the template class ValueClass which is
     780    used in the declaration of class Cache. Following the documentation of
     781    class Cache, we need to implement at least the methods:<br>
     782    <c>bool IntMinorValue::operator< (const IntMinorValue& key),</c><br>
     783    <c>bool IntMinorValue::operator== (const IntMinorValue& key),</c><br>
     784    <c>int IntMinorValue::getWeight ().</c><br><br>
     785    The main purpose of PolyMinorValue is to represent values of
     786    sub-determinantes of a pre-defined matrix. Class MinorKey is used to
     787    determine which rows and columns of this pre-defined matrix ought to
     788    belong to the respective sub-determinante of interest. PolyMinorValue is
     789    a special implementation which assumes matrices with polynomial entries,
     790    such that the result of any minor is again a polynomial.
     791    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
     792*/
     793class PolyMinorValue : public MinorValue
     794{
     795  private:
     796    /**
     797    * a store for the actual value of the minor
     798    */
     799    poly _result;
     800  public:
     801    /**
     802    * A constructor for class MinorValue.
     803    * @param result the actual value of the represented minor
     804    * @param multiplications number of multiplications to compute \a this
     805             minor
     806    * @param additions number of additions to compute \a this minor
     807    * @param accumulatedMultiplications number of multiplications to compute
     808             \a this minor, including nested operations
     809    * @param accumulatedAdditions number of additions to compute \a this
     810             minor, including nested operations
     811    * @param retrievals number of times this minor has been retrieved from
     812             cache
     813    * @param potentialRetrievals maximum number of times this minor may be
     814             retrieved from cache
     815    */
     816    PolyMinorValue (const poly result, const int multiplications,
     817                    const int additions,
     818                    const int accumulatedMultiplications,
     819                    const int accumulatedAdditions, const int retrievals,
     820                    const int potentialRetrievals);
     821
     822    /**
     823    * Copy constructor for creating a deep copy.
     824    */
     825    PolyMinorValue (const PolyMinorValue& mv);
     826
     827    /**
     828    * Assignment operator which creates a deep copy.
     829    */
     830    void operator= (const PolyMinorValue& mv);
     831   
     832    /**
     833    * just to make the compiler happy
     834    */
     835    PolyMinorValue ();
     836
     837    /**
     838    * Destructor
     839    */
     840    virtual ~PolyMinorValue ();
     841   
     842    /**
     843    * Accessor for the private field _result.
     844    * @result the result encoded in this class instance
     845    */
     846    poly getResult() const;
     847   
     848    /**
     849    * Accessor for the current weight of this class instance.
     850    * @result the current weight of this class instance
     851    */
     852    int getWeight () const;
     853   
     854    /**
     855    * A method for providing a printable version of the represented MinorValue.
     856    * @return a printable version of the given instance as instance of class
     857    * string
     858    */
     859    string toString () const;
    675860};
    676861
Note: See TracChangeset for help on using the changeset viewer.