Changeset 68ec38 in git


Ignore:
Timestamp:
Feb 2, 2010, 2:22:24 PM (13 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a657104b677b4c461d018cbf3204d72d34ad66a9')
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
Location:
Singular
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • Singular/Cache.h

    r13d171b r68ec38  
    2020    the total \e weight of the cache.<br>
    2121    Here, the \e weight of a cache is defined as the sum
    22     of \e weights of all cached values, where the \e weight of a single value
    23     needs to be implemented in the actual class replacing the placeholder class
    24     \c KeyClass. An example for the weight of a cached value
     22    of \e weights of all cached values, where the \e weight of each value
     23    needs to be implemented in the actual class \c ValueClass.
     24    An example for the weight of a cached value
    2525    may simply be its size in bytes, or may capture some other useful notion
    2626    of how \e heavy the value is. E.g., when caching polynomials, the \e weight
    27     may be defined to equal the number of its monomials.<br><br>
    28     The <em>key --> value</em> pairs of a cache are being stored in two standard lists
    29     \c _key and \c _value of equal length <em>L</em>.<br>
     27    may be defined to be equal to the number of its monomials.<br><br>
     28    The <em>key --> value</em> pairs of a cache are being stored in two
     29    standard lists \c _key and \c _value of equal length <em>L</em>.<br>
    3030    In order to enable a fast
    3131    value lookup, the vector \c _key maintains an ordering such that<br>
    3232    <em> i < j  ==>  _key[i] < _key[j],</em><br>
    3333    where the right-hand side comparator
    34     \e < needs to be implemented by class \c KeyClass. Note that this ordering allows
    35     for value lookup in time <em>O(log(L))</em>, when given a specific key.<br><br>
    36     In addition to \c _key and \c _value, there is a third book-keeping structure
    37     in Cache: The vector \c _rank of integers captures ranking information among
    38     all cached values. More concretely,<br>
     34    \e < needs to be implemented by class \c KeyClass. Note that this
     35    ordering allows for value lookup in time <em>O(log(L))</em>, when given
     36    a specific key.<br><br>
     37    In addition to \c _key and \c _value, there is a third book-keeping
     38    structure in Cache: The vector \c _rank of integers captures ranking
     39    information among all cached values. More concretely,<br>
    3940    <em>_rank : {0, 1, 2, ..., L - 1} --> {0, 1, 2, ..., L - 1}</em><br>
    4041    is a bijection with the semantic<br>
    4142    <em>_rank[s] < _rank[t] :<==> _value[_rank[s]] < _value[_rank[t]],</em><br>
    4243    where the right-hand side comparator \e < needs to be
    43     implemented by class \c ValueClass. Any relation
     44    implemented by class \c ValueClass. The intention here is that any relation
    4445    <em>_rank[s] < _rank[t]</em>
    45     implies that the key-value pair <em>_key[_rank[t]] --> _value[_rank[t]]</em> will
    46     be kept at least as long in cache as
    47     <em> _key[_rank[s]] --> _value[_rank[s]]</em>. (I.e., loosely speaking, the higher the
    48     rank, the longer will a pair be cached.)<br><br>
    49     Whenever the cache becomes either too large (in terms of number of entries), or too
    50     \e heavy (in terms of accumulated weight), it will automatically shrink until
    51     both bounds will have been re-established. To this end, the <em>key --> value</em>
    52     pair with least value rank will be erased from the cache. This process
    53     is repeated until the cache is small enough again, in terms of both the number of
    54     entries and the \e weight. (Note that it may be necessary to erase numerous pairs
    55     after inserting just one <em>key --> value</em> when this value's \e weight
    56     is unproportionally high.)<br><br>
    57     In order to make the above procedures work, the two template classes \c KeyClass
    58     and \c ValueClass need to implement the following methods:<br>
     46    is to imply that the key-value pair
     47    <em>_key[_rank[t]] --> _value[_rank[t]]</em> will be kept at least as
     48    long in cache as <em> _key[_rank[s]] --> _value[_rank[s]]</em>.
     49    (I.e., loosely speaking, the higher the rank, the longer a pair is going
     50    to be cached.)<br><br>
     51    Whenever the cache becomes either too large (in terms of number of
     52    entries), or too \e heavy (in terms of accumulated weight), it will
     53    automatically shrink until both bounds will have been re-established. To
     54    this end, the <em>key --> value</em> pair with least value rank will be
     55    erased from the cache. This process is repeated until the cache is small
     56    enough again, in terms of both the number of entries and the \e weight.
     57    (Note that it may be necessary to erase numerous pairs after inserting
     58    just one <em>key --> value</em> when this value's \e weight is
     59    unproportionally high.)<br><br>
     60    In order to make the above procedures work, the two template classes
     61    \c KeyClass and \c ValueClass need to implement the following methods:<br>
    5962    <c>bool KeyClass::operator< (const KeyClass& key),</c><br>
    6063    <c>bool KeyClass::operator== (const KeyClass& key),</c><br>
    … …  
    6467    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
    6568*/
    66 template<class KeyClass, class ValueClass> class Cache {
    67       private:
    68              /**
    69              * It is a bijection on the set {0, ..., _key.size() - 1}.<br>
    70              * Semantically, <c>_rank(j) > _rank(i)</c> means that the pair
    71              * <c>key(_rank(j)) --> value(_rank(j))</c> will be cached at least
    72              * as long as the pair <c>key(_rank(i)) -->  value(_rank(i))</c>.
    73              */
    74              list<int> _rank;
    75 
    76              /**
    77              * _key is sorted in ascending order, i.e.,
    78              * <em>j < i  ==>  _key(j) < _key(i),</em>
    79              * where the right-hand side comparator "<" needs to be implemented by KeyClass.
    80              */
    81              list<KeyClass> _key;
    82 
    83              /**
    84              *  _value captures the actual objects of interest;<br>
    85              * \c _value[i] corresponds to \c _key[i] and may be retrieved
    86              * by calling Cache::getValue (const KeyClass&) const with the argument \c _key[i]).
    87              */
    88              list<ValueClass> _value;
    89              
    90              list<int> _weights;
    91 
    92              mutable typename list<KeyClass>::const_iterator _itKey;
    93              mutable typename list<ValueClass>::const_iterator _itValue;
    94 
    95              /**
    96              * for storing the momentary weight of the given cache;<br>
    97              * This is the sum of \c _value[i].getWeight() over all \e i,
    98              * i.e., over all cached values.
    99              */
    100              int _weight;
    101 
    102              /**
    103              * the bound of cache entries;<br>
    104              * The cache will automatically ensure that this bound will never be exceeded;
    105              * see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
    106              */
    107              int _maxEntries;
    108 
    109              /**
    110              * the bound on total cache weight;<br>
    111              * The cache will automatically ensure that this bound will never be exceeded; see
    112              * see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
    113              */
    114              int _maxWeight;
    115 
    116              /**
    117              * A method for providing the index of a given key in the vector _key.
    118              * Either _key contains the given key, then its index will be returned.
    119              * Otherwise the position in _key, at which the given key should be placed
    120              * (with respect to the ordering in _key) is returned.
    121              * @param key an instance of KeyClass
    122              * @return the actual or would-be index of key in _key
    123              * @see Cache::hasKey (const KeyClass&) const
    124              */
    125              int getIndexInKey (const KeyClass& key) const;
    126 
    127              /**
    128              * A method for providing the index of a given value in the vector _rank.
    129              * Based on the rank of the given value, the position in _rank at which
    130              * the given value should be inserted, is returned.
    131              * (The method also works, when the given value is already contained in the
    132              * cache.)
    133              * @param value an instance of ValueClass
    134              * @return the index of value in _rank
    135              */
    136              int getIndexInRank (const ValueClass& value) const;
    137 
    138              /**
    139              * A method for shrinking the given cache so that it meet the bounds on
    140              * number of entries and total weight again.
    141              * The method returns true iff the process of shrinking deleted a pair
    142              * (k --> v) from the cache such that k equals the given key.
    143              * @param key an instance of KeyClass
    144              * @return true iff shrinking deleted a pair (key --> *)
    145              */
    146              bool shrink(const KeyClass& key);
    147 
    148              // @return true iff this deleted a pair (key --> *)
    149              bool deleteLast(const KeyClass& key);
    150       public:
    151              /**
    152              * A constructor for class Cache.
    153              * The method makes sure that all member vectors be empty.
    154              */
    155              Cache();
    156 
    157              /**
    158              * A destructor for class Cache.
    159              * The method makes that all member vectors are being cleared.
    160              * By calling "clear" on each vector instance, the destruction of all entries
    161              * of the cache is ensured.
    162              */
    163              ~Cache();
    164 
    165              /**
    166              * Copy implementation for class Cache.
    167              * Apart from copying all flat members, all vectors need to be deep-copied.
    168              */
    169              Cache (const Cache& c);
    170 
    171              /**
    172              * A user-suited constructor for class Cache.
    173              * The method makes sure that all member vectors be empty.
    174              * Moreover, the user can provide bounds for the number of entries
    175              * in the cache, and for the total weight of the cache.
    176              * @param maxEntries the (positive) maximal number of pairs (key --> value) in the cache
    177              * @param maxWeight the (positive) maximal weight of the cache
    178              */
    179              Cache (const int maxEntries, const int maxWeight);
    180 
    181              /**
    182              * A method for retrieving the momentary weight of the cache.
    183              * The return value will always be less than or equal to the result of
    184              * Cache::getMaxWeight () const.<br>
    185              * Semantically, the total weight of a cache is the sum of weights of all contained cache values.
    186              * @return the momentary weight of the cache
    187              * @see Cache::getMaxWeight () const
    188              * @see MinorValue::getWeight () const
    189              */
    190              int getWeight () const;
    191 
    192              /**
    193              * A method for retrieving the momentary number of (key --> value) pairs
    194              * in the cache.
    195              * The return value will always be less than or equal to the result of
    196              * Cache::getMaxNumberOfEntries () const.
    197              * @return the momentary number of cached values of the cache
    198              * @see Cache::getMaxNumberOfEntries () const
    199              */
    200              int getNumberOfEntries () const;
    201 
    202              /**
    203              * A method for retrieving the maximum number of (key --> value) pairs
    204              * in the cache.
    205              * The return value will always be greater than or equal to the result of
    206              * Cache::getNumberOfEntries () const.
    207              * @return the maximum number of cached values of the cache
    208              * @see Cache::getNumberOfEntries () const
    209              * @see Cache::Cache (const int, const int)
    210              */
    211              int getMaxNumberOfEntries () const;
    212 
    213              /**
    214              * A method for retrieving the maximum weight of the cache.
    215              * The return value will always be greater than or equal to the result of
    216              * Cache::getWeight () const.
    217              * @return the maximum weight of the cache
    218              * @see Cache::getWeight () const
    219              * @see Cache::Cache (const int, const int)
    220              */
    221              int getMaxWeight () const;
    222 
    223              /**
    224              * Checks whether the cache contains a pair (k --> v) such that
    225              * k equals the given key.
    226              * If so, the method returns true; false otherwise.
    227              * In order to make Cache::getValue (const KeyClass&) const
    228              * work properly, the user is strongly adviced to always check key
    229              * containment by means of Cache::hasKey (const KeyClass&) const.
    230              * (The implementation at hand ensures
    231              * that this does not result in extra computational efforts.)
    232              * @param key the key for which containment shall be checked
    233              * @return true iff the cache contains the given key
    234              * @see Cache::getValue (const KeyClass&) const
    235              */
    236              bool hasKey (const KeyClass& key) const;
    237 
    238              /**
    239              * Returns the value for a given key.
    240              * The method assumes that there is actually an entry of the form
    241              * (key --> *) in the cache. This can be checked using
    242              * Cache::hasKey (const KeyClass&) const. (Note that calling
    243              * both methods in direct succession does not result in extra computational
    244              * efforts.)
    245              * \par Assertions
    246              * If the given key is not contained in the cache, program execution will be stopped.
    247              * @param key the key, for which the corresponding value shall be returned
    248              * @return the value corresponding to the given key
    249              * @see Cache::hasKey (const KeyClass&) const
    250              */
    251              ValueClass getValue (const KeyClass& key) const;
    252 
    253              /**
    254              * Inserts the pair (key --> value) in the cache.
    255              * If there is already some entry (key --> value'), then the
    256              * value entry is being replaced.
    257              * As putting some new pair in the cache may result in a violation
    258              * of the maximal number of entries or the weight of the cache, or both,
    259              * Cache::put (const KeyClass&, const ValueClass&) will always finalize by
    260              * calling the private method Cache::shrink(const KeyClass&), in order to
    261              * re-establish both bounds. This may then result in deleting the newly
    262              * inserted pair (key --> value).<br>
    263              * Therefore, the method returns whether the pair is actually contained in
    264              * the cache after invokation of Cache::put (const KeyClass&, const ValueClass&).
    265              * @param key an instance of KeyClass
    266              * @param value an instance of ValueClass
    267              * @return whether the pair (key --> value) is contained in the modified cache
    268              * @see Cache::getValue (const KeyClass&) const
    269              */
    270              bool put (const KeyClass& key, const ValueClass& value);
    271 
    272              /**
    273              * Clears the cache so that it has no entry. This method will also enforce
    274              * destruction of all former entries of the cache.
    275              */
    276              void clear ();
    277 
    278              /**
    279              * A method for providing a printable version of the represented
    280              * cache, including all contained (key --> value) pairs.
    281              * @return a printable version of the given instance as instance of class string
    282              */
    283              string toString () const;
    284 
    285              /**
    286              * A method for printing a string representation of the given cache to std::cout.
    287              * This includes string representations of all contained (key --> value) pairs.
    288              */
    289              void print () const;
     69template<class KeyClass, class ValueClass> class Cache
     70{
     71  private:
     72     /**
     73     * A bijection on the set {0, ..., _key.size() - 1}.<br>
     74     * Semantically, <c>_rank(j) > _rank(i)</c> means that the pair
     75     * <c>key(_rank(j)) --> value(_rank(j))</c> will be cached at least
     76     * as long as the pair <c>key(_rank(i)) -->  value(_rank(i))</c>.
     77     */
     78     list<int> _rank;
     79 
     80     /**
     81     * _key is sorted in ascending order, i.e.,
     82     * <em>j < i  ==>  _key(j) < _key(i),</em>
     83     * where the right-hand side comparator "<" needs to be implemented
     84     * in KeyClass.
     85     */
     86     list<KeyClass> _key;
     87 
     88     /**
     89     *  _value captures the actual objects of interest;<br>
     90     * \c _value[i] corresponds to \c _key[i] and may be retrieved
     91     * by calling Cache::getValue (const KeyClass&) const with the
     92     * argument \c _key[i]).
     93     */
     94     list<ValueClass> _value;
     95     
     96     /**
     97     * container for the weights of all cached values
     98     */
     99     list<int> _weights;
     100 
     101     /**
     102     * a pointer to some element of _key;
     103     * We make this mutable so that methods which leave the cache
     104     * unmodified but which alter _itKey can still be declared as
     105     * const, as the user would expect for these methods.
     106     */
     107     mutable typename list<KeyClass>::const_iterator _itKey;
     108     
     109     /**
     110     * a pointer to some element of _value;
     111     * We make this mutable so that methods which leave the cache
     112     * unmodified but which alter _itValue can still be declared as
     113     * const, as the user would expect for these methods.
     114     */
     115     mutable typename list<ValueClass>::const_iterator _itValue;
     116 
     117     /**
     118     * for storing the momentary weight of the given cache;<br>
     119     * This is the sum of \c _value[i].getWeight() over all \e i,
     120     * i.e., over all cached values. Equivalently, this is equal
     121     * to all weights stored in _weights.
     122     */
     123     int _weight;
     124 
     125     /**
     126     * the bound for the number of cached <c>key --> value</c> pairs;<br>
     127     * The cache will automatically ensure that this bound will never be
     128     * exceeded;
     129     * see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
     130     */
     131     int _maxEntries;
     132 
     133     /**
     134     * the bound on total cache weight;<br>
     135     * The cache will automatically ensure that this bound will never be
     136     * exceeded; see
     137     * see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
     138     */
     139     int _maxWeight;
     140 
     141     /**
     142     * A method for providing the index of a given key in the vector _key.
     143     * Either _key contains the given key, then its index will be returned.
     144     * Otherwise the position in _key, at which the given key should be placed
     145     * (with respect to the ordering in _key) is returned.
     146     * @param key an instance of KeyClass
     147     * @return the actual or would-be index of key in _key
     148     * @see Cache::hasKey (const KeyClass&) const
     149     */
     150     int getIndexInKey (const KeyClass& key) const;
     151 
     152     /**
     153     * A method for providing the index of a given value in the vector _rank.
     154     * Based on the rank of the given value, the position in _rank at which
     155     * the given value should be inserted, is returned.
     156     * (The method also works, when the given value is already contained in
     157     * the cache.)
     158     * @param value an instance of ValueClass
     159     * @return the actual or would-be index of value in _rank
     160     */
     161     int getIndexInRank (const ValueClass& value) const;
     162 
     163     /**
     164     * A method for shrinking the given cache so that it meet the bounds on
     165     * the maximum number of entries and total weight again.
     166     * The method returns true iff the process of shrinking deleted a pair
     167     * (k --> v) from the cache such that k equals the given key.
     168     * @param key an instance of KeyClass
     169     * @return true iff shrinking deleted a pair (key --> *)
     170     */
     171     bool shrink (const KeyClass& key);
     172 
     173     /**
     174     * A method for deleting the least-ranked cache entry.
     175     * The method returns true iff the deleted pair (k --> v)
     176     * satisfies k == key.
     177     * @param key an instance of KeyClass
     178     * @return true iff a pair (key --> *) was deleted
     179     */
     180     bool deleteLast (const KeyClass& key);
     181  public:
     182     /**
     183     * A constructor for class Cache.
     184     * The method makes sure that all member vectors be empty.
     185     */
     186     Cache();
     187 
     188     /**
     189     * A destructor for class Cache.
     190     * The method clears all member vectors. (This includes that
     191     * destructors are invoked, accordingly.)
     192     */
     193     ~Cache();
     194 
     195     /**
     196     * Copy implementation for class Cache.
     197     * Apart from copying all flat members, all vectors are being
     198     * deep-copied.
     199     */
     200     Cache (const Cache& c);
     201 
     202     /**
     203     * A user-suited constructor for class Cache.
     204     * The method makes sure that all member vectors be empty.
     205     * Moreover, the user can provide bounds for the maximum
     206     * number of entries in the cache, and for the total weight
     207     * of the cache.
     208     * @param maxEntries the (positive) maximum number of pairs
     209              (key --> value) in the cache
     210     * @param maxWeight the (positive) maximum weight of the cache
     211     */
     212     Cache (const int maxEntries, const int maxWeight);
     213 
     214     /**
     215     * A method for retrieving the momentary weight of the cache.
     216     * The return value will always be less than or equal to the result
     217     * of Cache::getMaxWeight () const.<br>
     218     * Semantically, the total weight of a cache is the sum of weights
     219     * of all cached values.
     220     * @return the momentary weight of the cache
     221     * @see Cache::getMaxWeight () const
     222     * @see MinorValue::getWeight () const
     223     */
     224     int getWeight () const;
     225 
     226     /**
     227     * A method for retrieving the momentary number of (key --> value) pairs
     228     * in the cache.
     229     * The return value will always be less than or equal to the result of
     230     * Cache::getMaxNumberOfEntries () const.
     231     * @return the momentary number of cached values of the cache
     232     * @see Cache::getMaxNumberOfEntries () const
     233     */
     234     int getNumberOfEntries () const;
     235 
     236     /**
     237     * A method for retrieving the maximum number of (key --> value) pairs
     238     * in the cache.
     239     * @return the maximum number of cached values of the cache
     240     * @see Cache::getNumberOfEntries () const
     241     * @see Cache::Cache (const int, const int)
     242     */
     243     int getMaxNumberOfEntries () const;
     244 
     245     /**
     246     * A method for retrieving the maximum weight of the cache.
     247     * @return the maximum weight of the cache
     248     * @see Cache::getWeight () const
     249     * @see Cache::Cache (const int, const int)
     250     */
     251     int getMaxWeight () const;
     252 
     253     /**
     254     * Checks whether the cache contains a pair (k --> v) such that
     255     * k equals the given key.
     256     * If so, the method returns true; false otherwise.
     257     * In order to make Cache::getValue (const KeyClass&) const
     258     * work properly, the user is strongly adviced to always check key
     259     * containment by means of Cache::hasKey (const KeyClass&) const.
     260     * (The implementation at hand ensures that invoking hasKey and
     261     * getValue does not result in extra computational efforts.)
     262     * @param key the key for which containment is to be checked
     263     * @return true iff the cache contains the given key
     264     * @see Cache::getValue (const KeyClass&) const
     265     */
     266     bool hasKey (const KeyClass& key) const;
     267 
     268     /**
     269     * Returns the value for a given key.
     270     * The method assumes that there is actually an entry of the form
     271     * (key --> *) in the cache. This can be checked before using
     272     * Cache::hasKey (const KeyClass&) const. (Note that calling
     273     * both methods in direct succession does not result in extra
     274     * computational efforts.)
     275     * \par Assertions
     276     * If the given key is not contained in the cache, program execution
     277     * will be stopped.
     278     * @param key the key, for which the corresponding value is to be returned
     279     * @return the value corresponding to the given key
     280     * @see Cache::hasKey (const KeyClass&) const
     281     */
     282     ValueClass getValue (const KeyClass& key) const;
     283 
     284     /**
     285     * Inserts the pair (key --> value) in the cache.
     286     * If there is already some entry (key --> value'), then value will be
     287     * replaced by value'.
     288     * As putting some new pair in the cache may result in a violation
     289     * of the maximal number of entries or the weight of the cache, or both,
     290     * Cache::put (const KeyClass&, const ValueClass&) will always finalize by
     291     * calling the private method Cache::shrink(const KeyClass&), in order to
     292     * re-establish both bounds. Note that this may even result in deleting the
     293     * newly inserted pair (key --> value).<br>
     294     * Because of that undesirable but possible effect, the method returns
     295     * whether the pair is actually contained in the cache after invokation of
     296     * Cache::put (const KeyClass&, const ValueClass&).
     297     * @param key an instance of KeyClass
     298     * @param value an instance of ValueClass
     299     * @return whether the pair (key --> value) is contained in the modified
     300     *         cache
     301     * @see Cache::getValue (const KeyClass&) const
     302     */
     303     bool put (const KeyClass& key, const ValueClass& value);
     304 
     305     /**
     306     * Clears the cache so that it has no entry. This method will also
     307     * enforce destruction of all former entries of the cache.
     308     */
     309     void clear ();
     310 
     311     /**
     312     * A method for providing a printable version of the represented
     313     * cache, including all contained (key --> value) pairs.
     314     * @return a printable version of the given instance as instance of class
     315     *         string
     316     */
     317     string toString () const;
     318 
     319     /**
     320     * A method for printing a string representation of the given cache to
     321     * std::cout. This includes string representations of all contained
     322     * (key --> value) pairs.
     323     */
     324     void print () const;
    290325};
    291326

  • Singular/CacheImplementation.h

    r13d171b r68ec38  
    33
    44template<class KeyClass, class ValueClass>
    5 Cache<KeyClass, ValueClass>::Cache (const int maxEntries, const int maxWeight) {
    6     _maxEntries = maxEntries;
    7     _maxWeight = maxWeight;
    8     _rank.clear();
    9     _key.clear();
    10     _value.clear();
    11     _weights.clear();
    12     _itKey = _key.end(); // referring to past-the-end element in the list
    13     _itValue = _value.end(); // referring to past-the-end element in the list
    14     _weight = 0;
    15 }
    16 
    17 template<class KeyClass, class ValueClass>
    18 int Cache<KeyClass, ValueClass>::getWeight() const {
    19     return _weight;
    20 }
    21 
    22 template<class KeyClass, class ValueClass>
    23 int Cache<KeyClass, ValueClass>::getNumberOfEntries() const {
    24     return _rank.size();
    25 }
    26 
    27 template<class KeyClass, class ValueClass>
    28 void Cache<KeyClass, ValueClass>::clear() {
    29     _rank.clear();
    30     _key.clear();
    31     _value.clear();
    32     _weights.clear();
    33 }
    34 
    35 template<class KeyClass, class ValueClass>
    36 Cache<KeyClass, ValueClass>::~Cache() {
    37     _rank.clear();
    38     _key.clear();
    39     _value.clear();
    40     _weights.clear();
    41 }
    42 
    43 template<class KeyClass, class ValueClass>
    44 bool Cache<KeyClass, ValueClass>::hasKey (const KeyClass& key) const {
    45     _itKey = _key.end(); // referring to past-the-end element in the list
    46     typename list<KeyClass>::const_iterator itKey;
    47     _itValue = _value.begin();
    48     // As _key is a sorted list, the following could actually be implemented
    49     // in logarithmic time, by bisection. For lists this does not work.
    50     // But often, we can still terminate the linear loop.
    51     for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    52         int c = key.compare(*itKey);
    53         if (c == 0) {
    54             _itKey = itKey;
    55             return true;
     5Cache<KeyClass, ValueClass>::Cache (const int maxEntries, const int maxWeight)
     6{
     7  _maxEntries = maxEntries;
     8  _maxWeight = maxWeight;
     9  _rank.clear();
     10  _key.clear();
     11  _value.clear();
     12  _weights.clear();
     13  _itKey = _key.end(); /* referring to past-the-end element in the list */
     14  _itValue = _value.end(); /* referring to past-the-end element in the list */
     15  _weight = 0;
     16}
     17
     18template<class KeyClass, class ValueClass>
     19int Cache<KeyClass, ValueClass>::getWeight() const
     20{
     21  return _weight;
     22}
     23
     24template<class KeyClass, class ValueClass>
     25int Cache<KeyClass, ValueClass>::getNumberOfEntries() const
     26{
     27  return _rank.size();
     28}
     29
     30template<class KeyClass, class ValueClass>
     31void Cache<KeyClass, ValueClass>::clear()
     32{
     33  _rank.clear();
     34  _key.clear();
     35  _value.clear();
     36  _weights.clear();
     37}
     38
     39template<class KeyClass, class ValueClass>
     40Cache<KeyClass, ValueClass>::~Cache()
     41{
     42  _rank.clear();
     43  _key.clear();
     44  _value.clear();
     45  _weights.clear();
     46}
     47
     48template<class KeyClass, class ValueClass>
     49bool Cache<KeyClass, ValueClass>::hasKey (const KeyClass& key) const
     50{
     51  _itKey = _key.end(); // referring to past-the-end element in the list
     52  typename list<KeyClass>::const_iterator itKey;
     53  _itValue = _value.begin();
     54  /* As _key is a sorted list, the following could actually be implemented
     55     in logarithmic time, by bisection. However, for lists this does not work.
     56     But often, we can still terminate the linear loop before having visited
     57     all elements. */
     58  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     59  {
     60    int c = key.compare(*itKey);
     61    if (c == 0)
     62    {
     63      _itKey = itKey;
     64      return true;
     65    }
     66    if (c == -1) return false;
     67    _itValue++;
     68  }
     69  return false;
     70}
     71
     72template<class KeyClass, class ValueClass>
     73ValueClass Cache<KeyClass, ValueClass>::getValue (const KeyClass& key) const
     74{
     75  if (_itKey == _key.end())
     76    /* _itKey refers to past-the-end element in the list;
     77       thus, getValue has been called although hasKey
     78       produced no match */
     79    assert(false);
     80
     81  return *_itValue;
     82}
     83
     84template<class KeyClass, class ValueClass>
     85bool Cache<KeyClass, ValueClass>::shrink(const KeyClass& key)
     86{
     87  /* We need to return true iff the pair with given key needed to
     88     be erased during the shrinking procedure. So far, we assume no: */
     89  bool result = false;
     90  /* Shrink until both bounds will be met again: */
     91  while (int(_key.size()) > _maxEntries || _weight > _maxWeight)
     92  {
     93    if (deleteLast(key)) result = true;
     94  }
     95  return result;
     96}
     97
     98template<class KeyClass, class ValueClass>
     99int Cache<KeyClass, ValueClass>::getMaxNumberOfEntries() const
     100{
     101  return _maxEntries;
     102}
     103
     104template<class KeyClass, class ValueClass>
     105int Cache<KeyClass, ValueClass>::getMaxWeight() const
     106{
     107  return _maxWeight;
     108}
     109
     110template<class KeyClass, class ValueClass>
     111bool Cache<KeyClass, ValueClass>::deleteLast(const KeyClass& key)
     112{
     113  if (_rank.size() == 0)
     114  {
     115    return false; /* nothing to do */
     116  };
     117  /* We need to perform the following (empty) loop in order to
     118     obtain a forward-iterator pointing to the last entry of _rank.
     119     Note: We cannot use rbegin() because we need the iterator for
     120     erasing the last entry which is only implemented for forward
     121     iterators by std::list. */
     122  list<int>::iterator itRank;
     123  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) { }
     124  itRank--; /* Now, this forward iterator points to the last list entry. */
     125  int deleteIndex = *itRank; /* index of (_key, _value)-pair with worst,
     126                                i.e., highest _rank */
     127  bool result = false;
     128
     129  /* now delete entries in _key and _value with index deleteIndex */
     130  int k = 0;
     131  typename list<KeyClass>::iterator itKey;
     132  typename list<ValueClass>::iterator itValue = _value.begin();
     133  typename list<int>::iterator itWeights = _weights.begin();
     134  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     135  {
     136    if (k == deleteIndex)
     137    {
     138      result = (key.compare(*itKey) == 0);
     139      break;
     140    }
     141    itValue++;
     142    itWeights++;
     143    k++;
     144  }
     145  _key.erase(itKey);
     146  int deleteWeight = *itWeights;
     147  _value.erase(itValue);
     148  _weights.erase(itWeights);
     149
     150  /* adjust total weight of this cache */
     151  _weight -= deleteWeight;
     152
     153  /* now delete last entry of _rank and decrement all those indices
     154  // in _rank by 1 which are larger than deleteIndex */
     155  _rank.erase(itRank);
     156  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     157  {
     158    if (*itRank > deleteIndex) *itRank -= 1;
     159  }
     160
     161  return result;
     162}
     163
     164template<class KeyClass, class ValueClass>
     165bool Cache<KeyClass, ValueClass>::put (const KeyClass& key,
     166                                       const ValueClass& value)
     167{
     168  bool keyWasContained = false;
     169  int oldIndexInKey = -1;
     170  int newIndexInKey = _key.size();  /* default to enter new (key, value)-pair
     171                                       is at the end of the two lists;
     172                                       only used in the case
     173                                       keyWasContained == false */
     174  int k = 0;
     175  typename list<KeyClass>::iterator itKey;
     176  // itOldValue will later only be used in the case keyWasContained == true: */
     177  typename list<ValueClass>::iterator itOldValue = _value.begin();
     178  /* itOldWeights will later only be used in the case
     179     keyWasContained == true */
     180  typename list<int>::iterator itOldWeights = _weights.begin();
     181  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     182  {
     183    int c = key.compare(*itKey);
     184    if (c == -1)
     185    {
     186      newIndexInKey = k;
     187      break;
     188    }
     189    if (c == 0)
     190    {
     191      keyWasContained = true;
     192      oldIndexInKey = k;
     193      break;
     194    }
     195    itOldValue++;
     196    itOldWeights++;
     197    k++;
     198  }
     199  int utility = value.getUtility();
     200  int newWeight = value.getWeight();
     201  k = 0;
     202  typename list<ValueClass>::iterator itValue = _value.begin();
     203  for (itValue = _value.begin(); itValue != _value.end(); itValue++)
     204  {
     205    if (itValue->getUtility() > utility) k++;
     206  }
     207  int newIndexInRank = k;
     208
     209  if (keyWasContained)
     210  {
     211    /* There was already a pair of the form (key --> *). */
     212
     213    /*adjusting the weight of the cache */
     214    ValueClass oldValue = *itOldValue;
     215    _weight += newWeight - *itOldWeights;
     216
     217    /* overwriting old value by argument value */
     218    itOldValue = _value.erase(itOldValue);
     219    itOldWeights = _weights.erase(itOldWeights);
     220    ValueClass myValueCopy = value;
     221    _value.insert(itOldValue, myValueCopy);
     222    _weights.insert(itOldWeights, newWeight);
     223
     224    int oldIndexInRank = -1;
     225    /* oldIndexInRank is to be the position in _rank such that
     226       _rank[oldIndexInRank] == oldIndexInKey, i.e.
     227       _key[_rank[oldIndexInRank]] == key: */
     228    list<int>::iterator itRank;
     229    k = 0;
     230    for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     231    {
     232      if (*itRank == oldIndexInKey)
     233      {
     234          oldIndexInRank = k;
     235      }
     236      k++;
     237    }
     238    /* Although the key stays the same, the ranking of the (key --> value)
     239       pair may be completely different from before. Thus, we need to repair
     240       the entries of _rank: */
     241    if (oldIndexInRank < newIndexInRank)
     242    {  /* first insert, then erase */
     243      k = 0;
     244      /* insert 'oldIndexInKey' at new position 'newIndexInRank': */
     245      for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     246      {
     247        if (k == newIndexInRank) break;
     248        k++;
     249      }
     250      _rank.insert(itRank, oldIndexInKey); /* note that this may also insert
     251                                              at position itRank == _rank.end(),
     252                                              i.e. when above loop did not
     253                                              terminate because of a 'break'
     254                                              statement */
     255      k = 0;
     256      /* erase 'oldIndexInKey' at old position 'oldIndexInRank': */
     257      for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     258      {
     259        if (k == oldIndexInRank)
     260        {
     261          _rank.erase(itRank);
     262          break;
    56263        }
    57         if (c == -1) return false;
    58         _itValue++;
    59     }
    60     return false;
    61 }
    62 
    63 template<class KeyClass, class ValueClass>
    64 ValueClass Cache<KeyClass, ValueClass>::getValue (const KeyClass& key) const {
    65     if (_itKey == _key.end())
    66         // _itKey refers to past-the-end element in the list
    67         // getValue has been called although hasKey produced no match
    68         assert(false);
    69 
    70     return *_itValue;
    71 }
    72 
    73 template<class KeyClass, class ValueClass>
    74 bool Cache<KeyClass, ValueClass>::shrink(const KeyClass& key) {
    75     // We need to return true iff the pair with given key needed to be erased
    76     // during the shrinking procedure. So far, we assume no:
    77     bool result = false;
    78     // Shrink until both bounds will be met again:
    79     while (int(_key.size()) > _maxEntries || _weight > _maxWeight) {
    80         if (deleteLast(key)) result = true;
    81     }
    82     return result;
    83 }
    84 
    85 template<class KeyClass, class ValueClass>
    86 int Cache<KeyClass, ValueClass>::getMaxNumberOfEntries() const {
    87     return _maxEntries;
    88 }
    89 
    90 template<class KeyClass, class ValueClass>
    91 int Cache<KeyClass, ValueClass>::getMaxWeight() const {
    92     return _maxWeight;
    93 }
    94 
    95 template<class KeyClass, class ValueClass>
    96 bool Cache<KeyClass, ValueClass>::deleteLast(const KeyClass& key) {
    97     if (_rank.size() == 0) {
    98         return false; // nothing to do
    99     };
    100     // We need to do the next empty loop in order to obtain a forward-iterator pointing to the last
    101     // entry of _rank.
    102     // Note: We cannot use rbegin() because we need the iterator for erasing the last entry which is
    103     // only implemented for forward iterators by std::list.
    104     list<int>::iterator itRank;
    105     for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) { }
    106     itRank--;  // Now, this forward iterator points to the last list entry.
    107     int deleteIndex = *itRank;   // index of (_key, _value)-pair with worst, i.e., highest _rank
    108     bool result = false;
    109 
    110     // now delete entries in _key and _value with index deleteIndex
    111     int k = 0;
    112     typename list<KeyClass>::iterator itKey;
    113     typename list<ValueClass>::iterator itValue = _value.begin();
    114     typename list<int>::iterator itWeights = _weights.begin();
    115     for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    116         if (k == deleteIndex) {
    117             result = (key.compare(*itKey) == 0);
     264        k++;
     265      }
     266    }
     267    else
     268    {  /* oldIndexInRank >= newIndexInRank */
     269      if (oldIndexInRank > newIndexInRank)
     270      { /* first erase, then insert */
     271        k = 0;
     272        /* erase 'oldIndexInKey' at old position 'oldIndexInRank': */
     273        for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     274        {
     275          if (k == oldIndexInRank)
     276          {
     277            _rank.erase(itRank);
    118278            break;
    119         }
    120         itValue++;
    121         itWeights++;
    122         k++;
    123     }
    124     _key.erase(itKey);
    125     int deleteWeight = *itWeights;
    126     _value.erase(itValue);
    127     _weights.erase(itWeights);
    128 
    129     // adjust total weight of this cache
    130     _weight -= deleteWeight;
    131 
    132     // now delete last entry of _rank and decrement all those indices
    133     // in _rank by 1 which were larger than deleteIndex
    134     _rank.erase(itRank);
    135     for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    136         if (*itRank > deleteIndex) *itRank -= 1;
    137     }
    138 
    139     return result;
    140 }
    141 
    142 template<class KeyClass, class ValueClass>
    143 bool Cache<KeyClass, ValueClass>::put (const KeyClass& key, const ValueClass& value) {
    144     bool keyWasContained = false;
    145     int oldIndexInKey = -1;
    146     int newIndexInKey = _key.size();  // default to enter new (key, value)-pair is at the end of the two lists
    147                                       // only used in the case keyWasContained == false
    148     int k = 0;
    149     typename list<KeyClass>::iterator itKey;
    150     typename list<ValueClass>::iterator itOldValue = _value.begin(); // will later only be used in the case keyWasContained == true
    151     typename list<int>::iterator itOldWeights = _weights.begin(); // will later only be used in the case keyWasContained == true
    152     for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    153         int c = key.compare(*itKey);
    154         if (c == -1) {
    155             newIndexInKey = k;
    156             break;
    157         }
    158         if (c == 0) {
    159             keyWasContained = true;
    160             oldIndexInKey = k;
    161             break;
    162         }
    163         itOldValue++;
    164         itOldWeights++;
    165         k++;
    166     }
    167     int utility = value.getUtility();
    168     int newWeight = value.getWeight();
    169     k = 0;
    170     typename list<ValueClass>::iterator itValue = _value.begin();
    171     for (itValue = _value.begin(); itValue != _value.end(); itValue++) {
    172         if (itValue->getUtility() > utility) k++;
    173     }
    174     int newIndexInRank = k;
    175 
    176     if (keyWasContained) {
    177         // There was already a pair of the form (key --> *).
    178 
    179         // adjusting the weight of the cache
    180         ValueClass oldValue = *itOldValue;
    181         _weight += newWeight - *itOldWeights;
    182 
    183         // overriding old value by argument value
    184         itOldValue = _value.erase(itOldValue);
    185         itOldWeights = _weights.erase(itOldWeights);
    186         ValueClass myValueCopy = value;
    187         _value.insert(itOldValue, myValueCopy);
    188         _weights.insert(itOldWeights, newWeight);
    189 
    190         int oldIndexInRank = -1;
    191         // oldIndexInRank is to be the position in _rank such that
    192         // _rank[oldIndexInRank] == oldIndexInKey, i.e.
    193         // _key[_rank[oldIndexInRank]] == key:
    194         list<int>::iterator itRank;
    195         k = 0;
    196         for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    197             if (*itRank == oldIndexInKey) {
    198                 oldIndexInRank = k;
    199             }
    200             k++;
    201         }
    202         // Although the key stays the same, the ranking of the (key --> value) pair can be
    203         // completely different from before. Thus, we need to repair the entries of _rank:
    204         if (oldIndexInRank < newIndexInRank) {  // first insert, then erase
    205             k = 0;
    206             // insert 'oldIndexInKey' at new position 'newIndexInRank':
    207             for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    208                 if (k == newIndexInRank) break;
    209                 k++;
    210             }
    211             _rank.insert(itRank, oldIndexInKey); // note that this may also insert at position itRank == _rank.end(), i.e.
    212                                                  // when above loop did not terminate due to 'break' statement
    213             k = 0;
    214             // erase 'oldIndexInKey' at old position 'oldIndexInRank':
    215             for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    216                 if (k == oldIndexInRank) {
    217                     _rank.erase(itRank);
    218                     break;
    219                 }
    220                 k++;
    221             }
    222         }
    223         else {  // oldIndexInRank >= newIndexInRank
    224             if (oldIndexInRank > newIndexInRank) { // first erase, then insert
    225                 k = 0;
    226                 // erase 'oldIndexInKey' at old position 'oldIndexInRank':
    227                 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    228                     if (k == oldIndexInRank) {
    229                         _rank.erase(itRank);
    230                         break;
    231                     }
    232                     k++;
    233                 }
    234                 k = 0;
    235                 // insert 'oldIndexInKey' at new position 'newIndexInRank':
    236                 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    237                     if (k == newIndexInRank) {
    238                         _rank.insert(itRank, oldIndexInKey);
    239                         break;
    240                     }
    241                     k++;
    242                 }
    243             }
    244         }
    245     }
    246     else {
    247         // There is no pair of the form (key --> *). We are about to insert a completely new
    248         // (key, value)-pair.
    249         // After this branch, we shall have _key[newIndexInKey] = key; _value[newIndexInKey] = value.
    250         // Note that, after the above computation, newIndexInKey contains the correct target position.
    251         // Let's make room for the assignment _rank[newIndexInRank] := newIndexInKey:
    252         list<int>::iterator itRank;
    253         for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    254             if (newIndexInKey <= *itRank) {
    255                 *itRank += 1;
    256             }
     279          }
     280          k++;
    257281        }
    258282        k = 0;
    259         for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    260             if (k == newIndexInRank) break;
    261             k++;
     283        /* insert 'oldIndexInKey' at new position 'newIndexInRank': */
     284        for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     285        {
     286          if (k == newIndexInRank)
     287          {
     288            _rank.insert(itRank, oldIndexInKey);
     289            break;
     290          }
     291          k++;
    262292        }
    263         _rank.insert(itRank, newIndexInKey);
    264         // let's insert new key and new value at index newIndexInKey:
    265         itValue = _value.begin();
    266         typename list<int>::iterator itWeights = _weights.begin();
    267         k = 0;
    268         for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    269             if (k == newIndexInKey) break;
    270             itValue++;
    271             itWeights++;
    272             k++;
    273         }
    274         KeyClass myKeyCopy = key;
    275         ValueClass myValueCopy = value;
    276         _key.insert(itKey, myKeyCopy);
    277         _value.insert(itValue, myValueCopy);
    278         _weights.insert(itWeights, newWeight);
    279         // adjusting the total weight of the cache:
    280         _weight += newWeight;
    281     };
    282     // We may now have to shrink the cache:
    283     bool result = shrink(key);  // true iff shrinking deletes the new (key, value)-pair
    284 
    285     assert(_rank.size() == _key.size());
    286     assert(_rank.size() == _value.size());
    287     return !result; // true iff the new (key --> value) pair is actually in the cache now
    288 }
    289 
    290 template<class KeyClass, class ValueClass>
    291 string Cache<KeyClass, ValueClass>::toString() const {
    292     char h[10];
    293     string s = "Cache:";
    294     s += "\n   entries: ";
    295     sprintf(h, "%d", getNumberOfEntries()); s += h;
    296     s += " of at most ";
    297     sprintf(h, "%d", getMaxNumberOfEntries()); s += h;
    298     s += "\n   weight: ";
    299     sprintf(h, "%d", getWeight()); s += h;
    300     s += " of at most ";
    301     sprintf(h, "%d", getMaxWeight()); s += h;
    302     if (_key.size() == 0) {
    303         s += "\n   no pairs, i.e. cache is empty";
    304     }
    305     else {
    306         int k = 1;
    307         s += "\n   (key --> value) pairs in ascending order of keys:";
    308         typename list<KeyClass>::const_iterator itKey;
    309         typename list<ValueClass>::const_iterator itValue = _value.begin();
    310         for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    311             s += "\n      ";
    312             sprintf(h, "%d", k); s += h;
    313             s += ". ";
    314             s += itKey->toString();
    315             s += " --> ";
    316             s += itValue->toString();
    317             itValue++;
    318             k++;
    319         }
    320         s += "\n   (key --> value) pairs in descending order of ranks:";
    321         list<int>::const_iterator itRank;
    322         int r = 1;
    323         for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) {
    324            int index = *itRank;
    325            itValue = _value.begin();
    326            k = 0;
    327            for (itKey = _key.begin(); itKey != _key.end(); itKey++) {
    328                if (k == index) break;
    329                k++;
    330                itValue++;
    331            }
    332            s += "\n      ";
    333            sprintf(h, "%d", r); s += h;
    334            s += ". ";
    335            s += itKey->toString();
    336            s += " --> ";
    337            s += itValue->toString();
    338            r++;
    339         }
    340     }
    341     return s;
    342 }
    343 
    344 template<class KeyClass, class ValueClass>
    345 void Cache<KeyClass, ValueClass>::print() const {
    346     cout << this->toString();
     293      }
     294    }
     295  }
     296  else
     297  {
     298    /* There is no pair of the form (key --> *). We are about to insert
     299       a completely new (key, value)-pair.
     300       After this "else" branch, we shall have _key[newIndexInKey] = key;
     301       _value[newIndexInKey] = value. Note that, after the above computation,
     302       newIndexInKey contains the correct target position.
     303       Let's make room for the assignment
     304       _rank[newIndexInRank] := newIndexInKey: */
     305    list<int>::iterator itRank;
     306    for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     307    {
     308      if (newIndexInKey <= *itRank)
     309      {
     310        *itRank += 1;
     311      }
     312    }
     313    k = 0;
     314    for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     315    {
     316      if (k == newIndexInRank) break;
     317      k++;
     318    }
     319    _rank.insert(itRank, newIndexInKey);
     320    /* let's insert new key and new value at index newIndexInKey: */
     321    itValue = _value.begin();
     322    typename list<int>::iterator itWeights = _weights.begin();
     323    k = 0;
     324    for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     325    {
     326      if (k == newIndexInKey) break;
     327      itValue++;
     328      itWeights++;
     329      k++;
     330    }
     331    KeyClass myKeyCopy = key;
     332    ValueClass myValueCopy = value;
     333    _key.insert(itKey, myKeyCopy);
     334    _value.insert(itValue, myValueCopy);
     335    _weights.insert(itWeights, newWeight);
     336    /* adjusting the total weight of the cache: */
     337    _weight += newWeight;
     338  };
     339  /* We may now have to shrink the cache: */
     340  bool result = shrink(key);  /* true iff shrinking deletes the
     341                                 new (key, value)-pair */
     342
     343  assert(_rank.size() == _key.size());
     344  assert(_rank.size() == _value.size());
     345  return !result; /* true iff the new (key --> value) pair is
     346                     actually in the cache now */
     347}
     348
     349template<class KeyClass, class ValueClass>
     350string Cache<KeyClass, ValueClass>::toString() const
     351{
     352  char h[10];
     353  string s = "Cache:";
     354  s += "\n   entries: ";
     355  sprintf(h, "%d", getNumberOfEntries()); s += h;
     356  s += " of at most ";
     357  sprintf(h, "%d", getMaxNumberOfEntries()); s += h;
     358  s += "\n   weight: ";
     359  sprintf(h, "%d", getWeight()); s += h;
     360  s += " of at most ";
     361  sprintf(h, "%d", getMaxWeight()); s += h;
     362  if (_key.size() == 0)
     363  {
     364    s += "\n   no pairs, i.e. cache is empty";
     365  }
     366  else
     367  {
     368    int k = 1;
     369    s += "\n   (key --> value) pairs in ascending order of keys:";
     370    typename list<KeyClass>::const_iterator itKey;
     371    typename list<ValueClass>::const_iterator itValue = _value.begin();
     372    for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     373    {
     374      s += "\n      ";
     375      sprintf(h, "%d", k); s += h;
     376      s += ". ";
     377      s += itKey->toString();
     378      s += " --> ";
     379      s += itValue->toString();
     380      itValue++;
     381      k++;
     382    }
     383    s += "\n   (key --> value) pairs in descending order of ranks:";
     384    list<int>::const_iterator itRank;
     385    int r = 1;
     386    for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
     387    {
     388     int index = *itRank;
     389     itValue = _value.begin();
     390     k = 0;
     391     for (itKey = _key.begin(); itKey != _key.end(); itKey++)
     392     {
     393         if (k == index) break;
     394         k++;
     395         itValue++;
     396     }
     397     s += "\n      ";
     398     sprintf(h, "%d", r); s += h;
     399     s += ". ";
     400     s += itKey->toString();
     401     s += " --> ";
     402     s += itValue->toString();
     403     r++;
     404    }
     405  }
     406  return s;
     407}
     408
     409template<class KeyClass, class ValueClass>
     410void Cache<KeyClass, ValueClass>::print() const
     411{
     412  cout << this->toString();
    347413}
    348414
    … …  
    351417
    352418template<class KeyClass, class ValueClass>
    353 Cache<KeyClass, ValueClass>::Cache(const Cache& c) {
    354     _rank = c._rank;
    355     _value = c._value;
    356     _weights = c._weights;
    357     _key = c._key;
    358     _weight = c._weight;
    359     _maxEntries = c._maxEntries;
    360     _maxWeight = c._maxWeight;
     419Cache<KeyClass, ValueClass>::Cache(const Cache& c)
     420{
     421  _rank = c._rank;
     422  _value = c._value;
     423  _weights = c._weights;
     424  _key = c._key;
     425  _weight = c._weight;
     426  _maxEntries = c._maxEntries;
     427  _maxWeight = c._maxWeight;
    361428}
    362429

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

  • 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

  • Singular/MinorInterface.cc

    r13d171b r68ec38  
    1515{
    1616  printf("\n");
    17   printf("\n   ~~~> performed %d monomial-monomial-additions,",          addsMon);
    18   printf("\n   ~~~> performed %d monomial-monomial-multiplications",     multsMon);
    19   printf("\n   ~~~> performed %d polynomial-polynomial-additions,",      addsPoly);
    20   printf("\n   ~~~> performed %d polynomial-polynomial-multiplications", multsPoly);
     17  printf("\n   ~~~> performed %d monomial-monomial-additions,",
     18         addsMon);
     19  printf("\n   ~~~> performed %d monomial-monomial-multiplications",
     20         multsMon);
     21  printf("\n   ~~~> performed %d polynomial-polynomial-additions,",
     22         addsPoly);
     23  printf("\n   ~~~> performed %d polynomial-polynomial-multiplications",
     24         multsPoly);
    2125  printf("\n");
    2226}
    … …  
    4751   after the call, zeroCounter contains the number of zero entries
    4852   in the matrix */
    49 bool arrayIsNumberArray (const poly* polyArray, const ideal& iSB, const int length, int* intArray, poly* nfPolyArray, int& zeroCounter)
     53bool arrayIsNumberArray (const poly* polyArray, const ideal iSB,
     54                         const int length, int* intArray,
     55                         poly* nfPolyArray, int& zeroCounter)
    5056{
    5157  int n = 0; if (currRing != 0) n = currRing->N;
    … …  
    7076          isConstant = false;
    7177      if (!isConstant) result = false;
    72       else {
     78      else
     79      {
    7380        intArray[i] = n_Int(pGetCoeff(nfPolyArray[i]), currRing);
    7481        if (characteristic != 0) intArray[i] = intArray[i] % characteristic;
    … …  
    8188
    8289/* special implementation for the case that the matrix has only number entries;
    83    if i is not the zero pointer, then it is assumed to contain a std basis, and 
     90   if i is not the zero pointer, then it is assumed to contain a std basis, and
    8491   the number entries of the matrix are then assumed to be reduced w.r.t. i and
    8592   modulo the characteristic of the gound field/ring;
    86    this method should also work when currRing == null, i.e. when no ring has been
    87    declared */
    88 ideal getMinorIdeal_Int (const int* intMatrix, const int rowCount, const int columnCount,
    89                          const int minorSize, const int k, const char* algorithm,
     93   this method should also work when currRing == null, i.e. when no ring has
     94   been declared */
     95ideal getMinorIdeal_Int (const int* intMatrix, const int rowCount,
     96                         const int columnCount, const int minorSize,
     97                         const int k, const char* algorithm,
    9098                         const ideal i, const bool allDifferent)
    9199{
    … …  
    93101  IntMinorProcessor mp;
    94102  mp.defineMatrix(rowCount, columnCount, intMatrix);
    95   int myRowIndices[rowCount]; for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
    96   int myColumnIndices[columnCount]; for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
     103  int myRowIndices[rowCount];
     104  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
     105  int myColumnIndices[columnCount];
     106  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
    97107  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
    98108  mp.setMinorSize(minorSize);
    … …  
    107117  ideal iii = idInit(1, 0);
    108118
    109   bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested, omitting zero minors */
     119  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested,
     120                                             omitting zero minors */
    110121  bool duplicatesOk = (allDifferent ? false : true);
    111122  int kk = ((k < 0) ? -k : k); /* absolute value of k */
    … …  
    118129    poly f = NULL;
    119130    if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
    120     if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk)) collectedMinors++;
     131    if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
     132      collectedMinors++;
    121133  }
    122134
    … …  
    134146   if i is not the zero pointer than it is assumed to be a std basis (ideal),
    135147   and the poly matrix is assumed to be already reduced w.r.t. i */
    136 ideal getMinorIdeal_Poly (const poly* polyMatrix, const int rowCount, const int columnCount,
    137                           const int minorSize, const int k, const char* algorithm,
     148ideal getMinorIdeal_Poly (const poly* polyMatrix, const int rowCount,
     149                          const int columnCount, const int minorSize,
     150                          const int k, const char* algorithm,
    138151                          const ideal i, const bool allDifferent)
    139152{
    … …  
    141154  PolyMinorProcessor mp;
    142155  mp.defineMatrix(rowCount, columnCount, polyMatrix);
    143   int myRowIndices[rowCount]; for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
    144   int myColumnIndices[columnCount]; for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
     156  int myRowIndices[rowCount];
     157  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
     158  int myColumnIndices[columnCount];
     159  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
    145160  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
    146161  mp.setMinorSize(minorSize);
    … …  
    154169  ideal iii = idInit(1, 0);
    155170
    156   bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested, omitting zero minors */
     171  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
     172                                             requested, omitting zero minors */
    157173  bool duplicatesOk = (allDifferent ? false : true);
    158174  int kk = ((k < 0) ? -k : k); /* absolute value of k */
    … …  
    164180    theMinor = mp.getNextMinor(algorithm, i);
    165181    f = theMinor.getResult();
    166     if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk, duplicatesOk)) collectedMinors++;
     182    if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f),
     183                              zeroOk, duplicatesOk))
     184      collectedMinors++;
    167185  }
    168186
    … …  
    176194}
    177195
    178 ideal getMinorIdeal_toBeDone (const matrix& mat, const int minorSize, const int k,
    179                               const char* algorithm, const ideal i, const bool allDifferent)
     196ideal getMinorIdeal_toBeDone (const matrix mat, const int minorSize,
     197                              const int k, const char* algorithm,
     198                              const ideal i, const bool allDifferent)
    180199{
    181200  int rowCount = mat->nrows;
    … …  
    185204  int zz = 0;
    186205
    187   /* divert to special implementations for pure number matrices and actual polynomial matrices: */
     206  /* divert to special implementations for pure number matrices and actual
     207     polynomial matrices: */
    188208  int*  myIntMatrix  = new int [rowCount * columnCount];
    189209  poly* nfPolyMatrix = new poly[rowCount * columnCount];
    190   if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount, myIntMatrix, nfPolyMatrix, zz))
    191     iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k, algorithm, i, allDifferent);
     210  if (arrayIsNumberArray(myPolyMatrix, i, rowCount * columnCount,
     211                         myIntMatrix, nfPolyMatrix, zz))
     212    iii = getMinorIdeal_Int(myIntMatrix, rowCount, columnCount, minorSize, k,
     213                            algorithm, i, allDifferent);
    192214  else
    193215  {
    … …  
    195217        && (!rField_is_Ring_Z()) && (!allDifferent))
    196218    {
    197       /* In this case, we call an optimized procedure, dating back to Wilfried Pohl.
    198          It may be used whenever
     219      /* In this case, we call an optimized procedure, dating back to
     220         Wilfried Pohl. It may be used whenever
    199221         - all minors are requested,
    200222         - requested minors need not be mutually distinct, and
    … …  
    205227    else
    206228    {
    207       iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize, k, algorithm, i, allDifferent);
     229      iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
     230                               k, algorithm, i, allDifferent);
    208231    }
    209232  }
    … …  
    219242/* When called with algorithm == "Bareiss", the coefficients are assumed
    220243   to come from a field or from a ring which does not have zero-divisors
    221    (other than 0).
     244   (other than 0), i.e. from an integral domain.
    222245   E.g. Bareiss may be used over fields or over Z but not over
    223246        Z/6 (which has non-zero zero divisors, namely 2 and 3). */
    224247ideal getMinorIdeal (const matrix mat, const int minorSize, const int k,
    225                      const char* algorithm, const ideal iSB, const bool allDifferent)
     248                     const char* algorithm, const ideal iSB,
     249                     const bool allDifferent)
    226250{
    227251  /* Note that this method should be replaced by getMinorIdeal_toBeDone,
    … …  
    242266  {
    243267    nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
    244     if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal, nfPolyMatrix[i]);
     268    if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
     269                                        nfPolyMatrix[i]);
    245270  }
    246271
    … …  
    254279       - coefficients come from a field (i.e., the ring Z is not
    255280         allowed for this implementation). */
    256     iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize, iSB));
     281    iii = (iSB == 0 ? idMinors(mat, minorSize) : idMinors(mat, minorSize,
     282                                                          iSB));
    257283  }
    258284  else
    259285  {
    260     iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize, k, algorithm, iSB, allDifferent);
     286    iii = getMinorIdeal_Poly(nfPolyMatrix, rowCount, columnCount, minorSize,
     287                             k, algorithm, iSB, allDifferent);
    261288  }
    262289
    … …  
    269296
    270297/* special implementation for the case that the matrix has only number entries;
    271    if i is not the zero pointer, then it is assumed to contain a std basis, and 
     298   if i is not the zero pointer, then it is assumed to contain a std basis, and
    272299   the number entries of the matrix are then assumed to be reduced w.r.t. i and
    273300   modulo the characteristic of the gound field/ring;
    274    this method should also work when currRing == null, i.e. when no ring has been
    275    declared */
    276 ideal getMinorIdealCache_Int(const int* intMatrix, const int rowCount, const int columnCount,
    277                              const int minorSize, const int k, const ideal i,
    278                              const int cacheStrategy, const int cacheN, const int cacheW,
    279                              const bool allDifferent)
     301   this method should also work when currRing == null, i.e. when no ring has
     302   been declared */
     303ideal getMinorIdealCache_Int(const int* intMatrix, const int rowCount,
     304                             const int columnCount, const int minorSize,
     305                             const int k, const ideal i,
     306                             const int cacheStrategy, const int cacheN,
     307                             const int cacheW, const bool allDifferent)
    280308{
    281309  /* setting up a MinorProcessor for matrices with integer entries: */
    282310  IntMinorProcessor mp;
    283311  mp.defineMatrix(rowCount, columnCount, intMatrix);
    284   int myRowIndices[rowCount]; for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
    285   int myColumnIndices[columnCount]; for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
     312  int myRowIndices[rowCount];
     313  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
     314  int myColumnIndices[columnCount];
     315  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
    286316  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
    287317  mp.setMinorSize(minorSize);
    … …  
    298328  ideal iii = idInit(1, 0);
    299329
    300   bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested, omitting zero minors */
     330  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
     331                                             requested, omitting zero minors */
    301332  bool duplicatesOk = (allDifferent ? false : true);
    302333  int kk = ((k < 0) ? -k : k); /* absolute value of k */
    … …  
    309340    poly f = NULL;
    310341    if (theMinor.getResult() != 0) f = pISet(theMinor.getResult());
    311     if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk)) collectedMinors++;
     342    if (idInsertPolyWithTests(iii, collectedMinors, f, zeroOk, duplicatesOk))
     343      collectedMinors++;
    312344  }
    313345
    … …  
    321353}
    322354
    323 /* special implementation for the case that the matrix has non-number, i.e. real
    324    poly entries;
    325    if i is not the zero pointer, then it is assumed to contain a std basis, and
    326    the entries of the matrix are then assumed to be reduced w.r.t. i */
    327 ideal getMinorIdealCache_Poly(const poly* polyMatrix, const int rowCount, const int columnCount,
    328                               const int minorSize, const int k, const ideal i,
    329                               const int cacheStrategy, const int cacheN, const int cacheW,
    330                               const bool allDifferent)
     355/* special implementation for the case that the matrix has non-number,
     356   i.e. real poly entries;
     357   if i is not the zero pointer, then it is assumed to contain a std basis,
     358   and the entries of the matrix are then assumed to be reduced w.r.t. i */
     359ideal getMinorIdealCache_Poly(const poly* polyMatrix, const int rowCount,
     360                              const int columnCount, const int minorSize,
     361                              const int k, const ideal i,
     362                              const int cacheStrategy, const int cacheN,
     363                              const int cacheW, const bool allDifferent)
    331364{
    332365  /* setting up a MinorProcessor for matrices with polynomial entries: */
    333366  PolyMinorProcessor mp;
    334367  mp.defineMatrix(rowCount, columnCount, polyMatrix);
    335   int myRowIndices[rowCount]; for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
    336   int myColumnIndices[columnCount]; for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
     368  int myRowIndices[rowCount];
     369  for (int j = 0; j < rowCount; j++) myRowIndices[j] = j;
     370  int myColumnIndices[columnCount];
     371  for (int j = 0; j < columnCount; j++) myColumnIndices[j] = j;
    337372  mp.defineSubMatrix(rowCount, myRowIndices, columnCount, myColumnIndices);
    338373  mp.setMinorSize(minorSize);
    … …  
    348383  ideal iii = idInit(1, 0);
    349384
    350   bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are requested, omitting zero minors */
     385  bool zeroOk = ((k < 0) ? true : false); /* for k = 0, all minors are
     386                                             requested, omitting zero minors */
    351387  bool duplicatesOk = (allDifferent ? false : true);
    352388  int kk = ((k < 0) ? -k : k); /* absolute value of k */
    … …  
    358394    theMinor = mp.getNextMinor(cch, i);
    359395    f = theMinor.getResult();
    360     if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk, duplicatesOk)) collectedMinors++;
     396    if (idInsertPolyWithTests(iii, collectedMinors, pCopy(f), zeroOk,
     397                              duplicatesOk))
     398      collectedMinors++;
    361399  }
    362400
    … …  
    370408}
    371409
    372 ideal getMinorIdealCache_toBeDone (const matrix mat, const int minorSize, const int k,
    373                                    const ideal& iSB, const int cacheStrategy,
    374                                    const int cacheN, const int cacheW,
    375                                    const bool allDifferent)
     410ideal getMinorIdealCache_toBeDone (const matrix mat, const int minorSize,
     411                                   const int k, const ideal iSB,
     412                                   const int cacheStrategy, const int cacheN,
     413                                   const int cacheW, const bool allDifferent)
    376414{
    377415  int rowCount = mat->nrows;
    … …  
    381419  int zz = 0;
    382420
    383   /* divert to special implementation when myPolyMatrix has only number entries: */
     421  /* divert to special implementation when myPolyMatrix has only number
     422     entries: */
    384423  int*  myIntMatrix  = new int [rowCount * columnCount];
    385424  poly* nfPolyMatrix = new poly[rowCount * columnCount];
    386   if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount, myIntMatrix, nfPolyMatrix, zz))
    387     iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount, minorSize, k, iSB, cacheStrategy, cacheN, cacheW, allDifferent);
     425  if (arrayIsNumberArray(myPolyMatrix, iSB, rowCount * columnCount,
     426                         myIntMatrix, nfPolyMatrix, zz))
     427    iii = getMinorIdealCache_Int(myIntMatrix, rowCount, columnCount,
     428                                 minorSize, k, iSB, cacheStrategy, cacheN,
     429                                 cacheW, allDifferent);
    388430  else
    389     iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount, minorSize, k, iSB, cacheStrategy, cacheN, cacheW, allDifferent);
     431    iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
     432                                  minorSize, k, iSB, cacheStrategy, cacheN,
     433                                  cacheW, allDifferent);
    390434
    391435  /* clean up */
    … …  
    419463  {
    420464    nfPolyMatrix[i] = pCopy(myPolyMatrix[i]);
    421     if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal, nfPolyMatrix[i]);
    422   }
    423 
    424   iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount, minorSize, k, iSB, cacheStrategy, cacheN, cacheW, allDifferent);
     465    if (iSB != 0) nfPolyMatrix[i] = kNF(iSB, currRing->qideal,
     466                                        nfPolyMatrix[i]);
     467  }
     468
     469  iii = getMinorIdealCache_Poly(nfPolyMatrix, rowCount, columnCount,
     470                                minorSize, k, iSB, cacheStrategy,
     471                                cacheN, cacheW, allDifferent);
    425472
    426473  /* clean up */
    … …  
    431478}
    432479
    433 ideal getMinorIdealHeuristic (const matrix mat, const int minorSize, const int k,
    434                               const ideal iSB, const bool allDifferent)
     480ideal getMinorIdealHeuristic (const matrix mat, const int minorSize,
     481                              const int k, const ideal iSB,
     482                              const bool allDifferent)
    435483{
    436484  int vars = 0; if (currRing != 0) vars = currRing->N;
    … …  
    446494
    447495     otherwise:
    448      if not all minors are requested                   -> Laplace without Caching
     496     if not all minors are requested                   -> Laplace, no Caching
    449497     otherwise:
    450498     minorSize >= 3 and vars <= 4 and
    … …  
    455503                                                       -> Laplace with Caching
    456504
    457      otherwise:                                        -> Laplace without Caching
     505     otherwise:                                        -> Laplace, no Caching
    458506  */
    459507
    … …  
    463511  if (currRingIsOverIntegralDomain())
    464512  { /* the field case or ring Z */
    465     if      (minorSize <= 2)                                           b = true;
    466     else if (vars <= 2)                                                b = true;
     513    if      (minorSize <= 2)                                     b = true;
     514    else if (vars <= 2)                                          b = true;
    467515    else if (currRingIsOverField() && (vars == 3)
    468              && (currRing->ch >= 2) && (currRing->ch <= 32003))        b = true;
     516             && (currRing->ch >= 2) && (currRing->ch <= 32003))  b = true;
    469517  }
    470518  if (!b)
    471519  { /* the non-Bareiss cases */
    472     if (k != 0) /* this means, not all minors are requested */         l = true;
     520    if (k != 0) /* this means, not all minors are requested */   l = true;
    473521    else
    474522    { /* k == 0, i.e., all minors are requested */
    475523      int minorCount = 1;
    476       for (int i = rowCount - minorSize + 1; i <= rowCount; i++) minorCount = minorCount * i;
     524      for (int i = rowCount - minorSize + 1; i <= rowCount; i++)
     525        minorCount = minorCount * i;
    477526      for (int i = 2; i <= minorSize; i++) minorCount = minorCount / i;
    478       for (int i = columnCount - minorSize + 1; i <= columnCount; i++) minorCount = minorCount * i;
     527      for (int i = columnCount - minorSize + 1; i <= columnCount; i++)
     528        minorCount = minorCount * i;
    479529      for (int i = 2; i <= minorSize; i++) minorCount = minorCount / i;
    480       /* now: minorCount = (rowCount over minorSize) * (columnCount over minorSize) */
    481       if      ((minorSize >= 3) && (vars <= 4) && (minorCount >= 100)) c = true;
    482       else if ((minorSize >= 3) && (vars >= 5) && (minorCount >= 40))  c = true;
    483       else                                                             l = true;
     530      /* now: minorCount =   (rowCount over minorSize)
     531                           * (columnCount over minorSize) */
     532      if      ((minorSize >= 3) && (vars <= 4)
     533               && (minorCount >= 100))                           c = true;
     534      else if ((minorSize >= 3) && (vars >= 5)
     535               && (minorCount >= 40))                            c = true;
     536      else                                                       l = true;
    484537    }
    485538  }
    486539
    487   if      (b)  return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB, allDifferent);
    488   else if (l)  return getMinorIdeal(mat, minorSize, k, "Laplace", iSB, allDifferent);
    489   else /* c */ return getMinorIdealCache(mat, minorSize, k, iSB, 3, 200, 100000, allDifferent);
    490 }
     540  if      (b)    return getMinorIdeal(mat, minorSize, k, "Bareiss", iSB,
     541                                      allDifferent);
     542  else if (l)    return getMinorIdeal(mat, minorSize, k, "Laplace", iSB,
     543                                      allDifferent);
     544  else /* (c) */ return getMinorIdealCache(mat, minorSize, k, iSB,
     545                                      3, 200, 100000, allDifferent);
     546}

  • Singular/MinorInterface.h

    r13d171b r68ec38  
    33
    44/* activate the next define if you want all basic operations
    5    counted and printed when one of the following methods
    6    is invoked
    7    (not fully implemented yet) */
     5   counted and printed when one of the methods documented
     6   herein will be invoked (not fully implemented yet) */
    87/* #define COUNT_AND_PRINT_OPERATIONS 1 */
    98
    … …  
    1918   "Laplace"; when a cache is used, the underlying algorithm
    2019   is automatically Laplace */
    21 ideal getMinorIdeal          (const matrix m, const int minorSize, const int k,
    22                               const char* algorithm, const ideal i,
     20   
     21/**
     22* Returns the specified set of minors (= subdeterminantes) of the
     23* given matrix. These minors form the set of generators of the ideal
     24* which is actually returned.<br>
     25* If k == 0, all non-zero minors will be computed. For k > 0, only
     26* the first k non-zero minors (to some fixed ordering among all minors)
     27* will be computed. Use k < 0 to compute the first |k| minors (including
     28* zero minors).<br>
     29* algorithm must be one of "Bareiss" and "Laplace".<br>
     30* i must be either NULL or an ideal capturing a standard basis. In the
     31* later case all minors will be reduced w.r.t. i.
     32* If allDifferent is true, each minor will be included as generator
     33* in the resulting ideal only once; otherwise as often as it occurs as
     34* minor value during the computation.
     35* @param m the matrix from which to compute minors
     36* @param minorSize the size of the minors to be computed
     37* @param k the number of minors to be computed
     38* @param algorithm the algorithm to be used for the computation
     39* @param i NULL or an ideal which encodes a standard basis
     40* @param allDifferent if true each minor is considered only once
     41* @return the ideal which has as generators the specified set of minors
     42*/
     43ideal getMinorIdeal (const matrix m, const int minorSize, const int k,
     44                     const char* algorithm, const ideal i,
     45                     const bool allDifferent);
     46
     47/**
     48* Returns the specified set of minors (= subdeterminantes) of the
     49* given matrix. These minors form the set of generators of the ideal
     50* which is actually returned.<br>
     51* If k == 0, all non-zero minors will be computed. For k > 0, only
     52* the first k non-zero minors (to some fixed ordering among all minors)
     53* will be computed. Use k < 0 to compute the first |k| minors (including
     54* zero minors).<br>
     55* The underlying algorithm is Laplace's algorithm with caching of certain
     56* subdeterminantes. The caching strategy can be set; see
     57* int MinorValue::getUtility () const in Minor.cc. cacheN is the maximum
     58* number of cached polynomials (=subdeterminantes); cacheW the maximum
     59* weight of the cache during all computations.<br>
     60* i must be either NULL or an ideal capturing a standard basis. In the
     61* later case all minors will be reduced w.r.t. i.
     62* If allDifferent is true, each minor will be included as generator
     63* in the resulting ideal only once; otherwise as often as it occurs as
     64* minor value during the computation.
     65* @param m the matrix from which to compute minors
     66* @param minorSize the size of the minors to be computed
     67* @param k the number of minors to be computed
     68* @param i NULL or an ideal which encodes a standard basis
     69* @param cacheStrategy one of {1, .., 5}; see Minor.cc
     70* @param cacheN maximum number of cached polynomials (=subdeterminantes)
     71* @param cacheW maximum weight of the cache
     72* @param allDifferent if true each minor is considered only once
     73* @return the ideal which has as generators the specified set of minors
     74*/
     75ideal getMinorIdealCache (const matrix m, const int minorSize, const int k,
     76                          const ideal i, const int cacheStrategy,
     77                          const int cacheN, const int cacheW,
     78                          const bool allDifferent);
     79
     80/**
     81* Returns the specified set of minors (= subdeterminantes) of the
     82* given matrix. These minors form the set of generators of the ideal
     83* which is actually returned.<br>
     84* If k == 0, all non-zero minors will be computed. For k > 0, only
     85* the first k non-zero minors (to some fixed ordering among all minors)
     86* will be computed. Use k < 0 to compute the first |k| minors (including
     87* zero minors).<br>
     88* The algorithm is heuristically chosen among "Bareiss", "Laplace",
     89* and Laplace with caching (of subdeterminants).<br>
     90* i must be either NULL or an ideal capturing a standard basis. In the
     91* later case all minors will be reduced w.r.t. i.
     92* If allDifferent is true, each minor will be included as generator
     93* in the resulting ideal only once; otherwise as often as it occurs as
     94* minor value during the computation.
     95* @param m the matrix from which to compute minors
     96* @param minorSize the size of the minors to be computed
     97* @param k the number of minors to be computed
     98* @param i NULL or an ideal which encodes a standard basis
     99* @param allDifferent if true each minor is considered only once
     100* @return the ideal which has as generators the specified set of minors
     101*/
     102ideal getMinorIdealHeuristic (const matrix m, const int minorSize,
     103                              const int k, const ideal i,
    23104                              const bool allDifferent);
    24 ideal getMinorIdealCache     (const matrix m, const int minorSize, const int k,
    25                               const ideal i, const int cacheStrategy,
    26                               const int cacheN, const int cacheW,
    27                               const bool allDifferent);
    28 ideal getMinorIdealHeuristic (const matrix m, const int minorSize, const int k,
    29                               const ideal i, const bool allDifferent);
    30105
    31106#endif

  • Singular/MinorProcessor.cc

    r13d171b r68ec38  
    77#include "kbuckets.h"
    88
    9 void MinorProcessor::print() const {
    10     PrintS(this->toString().c_str());
    11 }
    12 
    13 int MinorProcessor::getBestLine (const int k, const MinorKey& mk) const {
    14     // This method identifies the row or column with the most zeros.
    15     // The returned index (bestIndex) is absolute within the pre-defined matrix.
    16     // If some row has the most zeros, then the absolute (0-based) row index is returned.
    17     // If, contrariwise, some column has the most zeros, then -1 minus the absolute (0-based) column index is returned.
    18     int numberOfZeros = 0;
    19     int bestIndex = 100000;    // We start with an invalid row/column index.
    20     int maxNumberOfZeros = -1; // We update this variable whenever we find a new so-far optimal row or column.
    21     for (int r = 0; r < k; r++) {
    22         // iterate through all k rows of the momentary minor
    23         int absoluteR = mk.getAbsoluteRowIndex(r);
    24         numberOfZeros = 0;
    25         for (int c = 0; c < k; c++) {
    26             int absoluteC = mk.getAbsoluteColumnIndex(c);
    27             if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
    28         }
    29         if (numberOfZeros > maxNumberOfZeros) {
    30             // We found a new best line which is a row.
    31             bestIndex = absoluteR;
    32             maxNumberOfZeros = numberOfZeros;
    33         }
    34     };
    35     for (int c = 0; c < k; c++) {
    36         int absoluteC = mk.getAbsoluteColumnIndex(c);
    37         numberOfZeros = 0;
    38         for (int r = 0; r < k; r++) {
    39             int absoluteR = mk.getAbsoluteRowIndex(r);
    40             if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
    41         }
    42         if (numberOfZeros > maxNumberOfZeros) {
    43             // We found a new best line which is a column. So we transform the return value.
    44             // Note that we can easily get back absoluteC from bestLine: absoluteC = - 1 - bestLine.
    45             bestIndex = - absoluteC - 1;
    46             maxNumberOfZeros = numberOfZeros;
    47         }
    48     };
    49     return bestIndex;
    50 }
    51 
    52 void MinorProcessor::setMinorSize(const int minorSize) {
    53     _minorSize = minorSize;
    54     _minor.reset();
    55 }
    56 
    57 bool MinorProcessor::hasNextMinor() {
    58     return setNextKeys(_minorSize);
    59 }
    60 
    61 void MinorProcessor::getCurrentRowIndices(int* const target) const {
    62     return _minor.getAbsoluteRowIndices(target);
    63 }
    64 
    65 void MinorProcessor::getCurrentColumnIndices(int* const target) const {
    66     return _minor.getAbsoluteColumnIndices(target);
    67 }
    68 
    69 void MinorProcessor::defineSubMatrix(const int numberOfRows, const int* rowIndices,
    70                                      const int numberOfColumns, const int* columnIndices) {
    71     // The method assumes ascending row and column indices in the two argument arrays.
    72     // These indices are understood to be zero-based.
    73     // The method will set the two arrays of ints in _container.
    74     // Example: The indices 0, 2, 3, 7 will be converted to an array with one int
    75     // representing the binary number 10001101 (check bits from right to left).
    76 
    77     _containerRows = numberOfRows;
    78     int highestRowIndex = rowIndices[numberOfRows - 1];
    79     int rowBlockCount = (highestRowIndex / 32) + 1;
    80     unsigned int rowBlocks[rowBlockCount];
    81     for (int i = 0; i < rowBlockCount; i++) rowBlocks[i] = 0;
    82     for (int i = 0; i < numberOfRows; i++) {
    83         int blockIndex = rowIndices[i] / 32;
    84         int offset = rowIndices[i] % 32;
    85         rowBlocks[blockIndex] += (1 << offset);
    86     }
    87 
    88     _containerColumns = numberOfColumns;
    89     int highestColumnIndex = columnIndices[numberOfColumns - 1];
    90     int columnBlockCount = (highestColumnIndex / 32) + 1;
    91     unsigned int columnBlocks[columnBlockCount];
    92     for (int i = 0; i < columnBlockCount; i++) columnBlocks[i] = 0;
    93     for (int i = 0; i < numberOfColumns; i++) {
    94         int blockIndex = columnIndices[i] / 32;
    95         int offset = columnIndices[i] % 32;
    96         columnBlocks[blockIndex] += (1 << offset);
    97     }
    98 
    99     _container.set(rowBlockCount, rowBlocks, columnBlockCount, columnBlocks);
    100 }
    101 
    102 bool MinorProcessor::setNextKeys(const int k) {
    103     // This method moves _minor to the next valid kxk-minor within _container.
    104     // It returns true iff this is successful, i.e. iff _minor did not already encode the final kxk-minor.
    105     if (_minor.compare(MinorKey(0, 0, 0, 0)) == 0) {
    106         // This means that we haven't started yet. Thus, we are about to compute the first kxk-minor.
    107         _minor.selectFirstRows(k, _container);
    108         _minor.selectFirstColumns(k, _container);
    109         return true;
    110     }
    111     else if (_minor.selectNextColumns(k, _container)) {
    112         // Here we were able to pick a next subset of columns (within the same subset of rows).
    113         return true;
    114     }
    115     else if (_minor.selectNextRows(k, _container)) {
    116         // Here we were not able to pick a next subset of columns (within the same subset of rows).
    117         // But we could pick a next subset of rows. We must hence reset the subset of columns:
    118         _minor.selectFirstColumns(k, _container);
    119         return true;
    120     }
    121     else {
    122         // We were neither able to pick a next subset of columns nor of rows.
    123         // I.e., we have iterated through all sensible choices of subsets of rows and columns.
    124         return false;
    125     }
    126 }
    127 
    128 bool MinorProcessor::isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
     9void MinorProcessor::print() const
     10{
     11  PrintS(this->toString().c_str());
     12}
     13
     14int MinorProcessor::getBestLine (const int k, const MinorKey& mk) const
     15{
     16  /* This method identifies the row or column with the most zeros.
     17     The returned index (bestIndex) is absolute within the pre-
     18     defined matrix.
     19     If some row has the most zeros, then the absolute (0-based)
     20     row index is returned.
     21     If, contrariwise, some column has the most zeros, then -1 minus
     22     the absolute (0-based) column index is returned. */
     23  int numberOfZeros = 0;
     24  int bestIndex = 100000;    /* We start with an invalid row/column index. */
     25  int maxNumberOfZeros = -1; /* We update this variable whenever we find
     26                                a new so-far optimal row or column. */
     27  for (int r = 0; r < k; r++)
     28  {
     29    /* iterate through all k rows of the momentary minor */
     30    int absoluteR = mk.getAbsoluteRowIndex(r);
     31    numberOfZeros = 0;
     32    for (int c = 0; c < k; c++)
     33    {
     34      int absoluteC = mk.getAbsoluteColumnIndex(c);
     35      if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
     36    }
     37    if (numberOfZeros > maxNumberOfZeros)
     38    {
     39      /* We found a new best line which is a row. */
     40      bestIndex = absoluteR;
     41      maxNumberOfZeros = numberOfZeros;
     42    }
     43  };
     44  for (int c = 0; c < k; c++)
     45  {
     46    int absoluteC = mk.getAbsoluteColumnIndex(c);
     47    numberOfZeros = 0;
     48    for (int r = 0; r < k; r++)
     49    {
     50      int absoluteR = mk.getAbsoluteRowIndex(r);
     51      if (isEntryZero(absoluteR, absoluteC)) numberOfZeros++;
     52    }
     53    if (numberOfZeros > maxNumberOfZeros)
     54    {
     55      /* We found a new best line which is a column. So we transform
     56         the return value. Note that we can easily retrieve absoluteC
     57         from bestLine: absoluteC = - 1 - bestLine. */
     58      bestIndex = - absoluteC - 1;
     59      maxNumberOfZeros = numberOfZeros;
     60    }
     61  };
     62  return bestIndex;
     63}
     64
     65void MinorProcessor::setMinorSize(const int minorSize)
     66{
     67  _minorSize = minorSize;
     68  _minor.reset();
     69}
     70
     71bool MinorProcessor::hasNextMinor()
     72{
     73  return setNextKeys(_minorSize);
     74}
     75
     76void MinorProcessor::getCurrentRowIndices(int* const target) const
     77{
     78  return _minor.getAbsoluteRowIndices(target);
     79}
     80
     81void MinorProcessor::getCurrentColumnIndices(int* const target) const
     82{
     83  return _minor.getAbsoluteColumnIndices(target);
     84}
     85
     86void MinorProcessor::defineSubMatrix(const int numberOfRows,
     87                                     const int* rowIndices,
     88                                     const int numberOfColumns,
     89                                     const int* columnIndices)
     90{
     91  /* The method assumes ascending row and column indices in the
     92     two argument arrays. These indices are understood to be zero-based.
     93     The method will set the two arrays of ints in _container.
     94     Example: The indices 0, 2, 3, 7 will be converted to an array with
     95     one int representing the binary number 10001101
     96     (check bits from right to left). */
     97
     98  _containerRows = numberOfRows;
     99  int highestRowIndex = rowIndices[numberOfRows - 1];
     100  int rowBlockCount = (highestRowIndex / 32) + 1;
     101  unsigned int rowBlocks[rowBlockCount];
     102  for (int i = 0; i < rowBlockCount; i++) rowBlocks[i] = 0;
     103  for (int i = 0; i < numberOfRows; i++)
     104  {
     105    int blockIndex = rowIndices[i] / 32;
     106    int offset = rowIndices[i] % 32;
     107    rowBlocks[blockIndex] += (1 << offset);
     108  }
     109
     110  _containerColumns = numberOfColumns;
     111  int highestColumnIndex = columnIndices[numberOfColumns - 1];
     112  int columnBlockCount = (highestColumnIndex / 32) + 1;
     113  unsigned int columnBlocks[columnBlockCount];
     114  for (int i = 0; i < columnBlockCount; i++) columnBlocks[i] = 0;
     115  for (int i = 0; i < numberOfColumns; i++)
     116  {
     117    int blockIndex = columnIndices[i] / 32;
     118    int offset = columnIndices[i] % 32;
     119    columnBlocks[blockIndex] += (1 << offset);
     120  }
     121
     122  _container.set(rowBlockCount, rowBlocks, columnBlockCount, columnBlocks);
     123}
     124
     125bool MinorProcessor::setNextKeys(const int k)
     126{
     127  /* This method moves _minor to the next valid (k x k)-minor within
     128     _container. It returns true iff this is successful, i.e. iff
     129     _minor did not already encode the terminal (k x k)-minor. */
     130  if (_minor.compare(MinorKey(0, 0, 0, 0)) == 0)
     131  {
     132    /* This means that we haven't started yet. Thus, we are about
     133       to compute the first (k x k)-minor. */
     134    _minor.selectFirstRows(k, _container);
     135    _minor.selectFirstColumns(k, _container);
     136    return true;
     137  }
     138  else if (_minor.selectNextColumns(k, _container))
     139  {
     140    /* Here we were able to pick a next subset of columns
     141       within the same subset of rows. */
     142    return true;
     143  }
     144  else if (_minor.selectNextRows(k, _container))
     145  {
     146    /* Here we were not able to pick a next subset of columns
     147       within the same subset of rows. But we could pick a next
     148       subset of rows. We must hence reset the subset of columns: */
     149    _minor.selectFirstColumns(k, _container);
     150    return true;
     151  }
     152  else
     153  {
     154    /* We were neither able to pick a next subset
     155       of columns nor of rows. I.e., we have iterated through
     156       all sensible choices of subsets of rows and columns. */
     157    return false;
     158  }
     159}
     160
     161bool MinorProcessor::isEntryZero (const int absoluteRowIndex,
     162                                  const int absoluteColumnIndex) const
    129163{
    130164  assume(false);
    … …  
    138172}
    139173
    140 int MinorProcessor::IOverJ(const int i, const int j) {
    141     // This is a non-recursive implementation.
    142     assert(i >= 0 && j >= 0 && i >= j);
    143     if (j == 0 || i == j) return 1;
    144     int result = 1;
    145     for (int k = i - j + 1; k <= i; k++) result *= k;
    146     // Here, we have result = (i - j + 1) * ... * i.
    147     for (int k = 2; k <= j; k++) result /= k;
    148     // Here, we have result = (i - j + 1) * ... * i / 1 / 2 ... / j = i! / j! / (i - j)!.
    149     return result;
    150 }
    151 
    152 int MinorProcessor::Faculty(const int i) {
    153     // This is a non-recursive implementation.
    154     assert(i >= 0);
    155     int result = 1;
    156     for (int j = 1; j <= i; j++) result *= j;
    157     // Here, we have result = 1 * 2 * ... * i = i!
    158     return result;
    159 }
    160 
    161 int MinorProcessor::NumberOfRetrievals (const int rows, const int columns, const int containerMinorSize,
    162                         const int minorSize, const bool multipleMinors) {
    163     // This method computes the number of potential retrievals of a single minor when computing
    164     // all minors of a given size within a matrix of given size.
    165     int result = 0;
    166     if (multipleMinors) {
    167         // Here, we would like to compute all minors of size
    168         // containerMinorSize x containerMinorSize in a matrix of size rows x columns.
    169         // Then, we need to retrieve any minor of size minorSize x minorSize exactly
    170         // n times, where n is as follows:
    171         result = IOverJ(rows - minorSize, containerMinorSize - minorSize)
    172                * IOverJ(columns - minorSize, containerMinorSize - minorSize)
    173                * Faculty(containerMinorSize - minorSize);
    174     }
    175     else {
    176         // Here, we would like to compute just one minor of size
    177         // containerMinorSize x containerMinorSize. Then, we need to retrieve
    178         // any minor of size minorSize x minorSize exactly
    179         // (containerMinorSize - minorSize)! times:
    180         result = Faculty(containerMinorSize - minorSize);
    181     }
    182     return result;
    183 }
    184 
    185 MinorProcessor::MinorProcessor () {
    186     _container = MinorKey(0, 0, 0, 0);
    187     _minor = MinorKey(0, 0, 0, 0);
    188     _containerRows = 0;
    189     _containerColumns = 0;
    190     _minorSize = 0;
    191     _rows = 0;
    192     _columns = 0;
    193 }
    194 
    195 IntMinorProcessor::IntMinorProcessor () {
    196     _intMatrix = 0;
    197 }
    198 
    199 string IntMinorProcessor::toString () const {
    200     char h[32];
    201     string t = "";
    202     string s = "IntMinorProcessor:";
    203     s += "\n   matrix: ";
    204     sprintf(h, "%d", _rows); s += h;
    205     s += " x ";
    206     sprintf(h, "%d", _columns); s += h;
    207     for (int r = 0; r < _rows; r++) {
    208         s += "\n      ";
    209         for (int c = 0; c < _columns; c++) {
    210             sprintf(h, "%d", getEntry(r, c)); t = h;
    211             for (int k = 0; k < int(4 - strlen(h)); k++) s += " ";
    212             s += t;
    213         }
    214     }
    215     int myIndexArray[500];
    216     s += "\n   considered submatrix has row indices: ";
    217     _container.getAbsoluteRowIndices(myIndexArray);
    218     for (int k = 0; k < _containerRows; k++) {
    219         if (k != 0) s += ", ";
    220         sprintf(h, "%d", myIndexArray[k]); s += h;
    221     }
    222     s += " (first row of matrix has index 0)";
    223     s += "\n   considered submatrix has column indices: ";
    224     _container.getAbsoluteColumnIndices(myIndexArray);
    225     for (int k = 0; k < _containerColumns; k++) {
    226         if (k != 0) s += ", ";
    227         sprintf(h, "%d", myIndexArray[k]); s += h;
    228     }
    229     s += " (first column of matrix has index 0)";
    230     s += "\n   size of considered minor(s): ";
    231     sprintf(h, "%d", _minorSize); s += h;
    232     s += "x";
    233     s += h;
    234     return s;
    235 }
    236 
    237 IntMinorProcessor::~IntMinorProcessor() {
    238     // free memory of _intMatrix
    239     delete [] _intMatrix; _intMatrix = 0;
    240 }
    241 
    242 bool IntMinorProcessor::isEntryZero (const int absoluteRowIndex, const int absoluteColumnIndex) const
     174int MinorProcessor::IOverJ(const int i, const int j)
     175{
     176  /* This is a non-recursive implementation. */
     177  assert(i >= 0 && j >= 0 && i >= j);
     178  if (j == 0 || i == j) return 1;
     179  int result = 1;
     180  for (int k = i - j + 1; k <= i; k++) result *= k;
     181  /* Now, result = (i - j + 1) * ... * i. */
     182  for (int k = 2; k <= j; k++) result /= k;
     183  /* Now, result = (i - j + 1) * ... * i / 1 / 2 ...
     184     ... / j = i! / j! / (i - j)!. */
     185  return result;
     186}
     187
     188int MinorProcessor::Faculty(const int i)
     189{
     190  /* This is a non-recursive implementation. */
     191  assert(i >= 0);
     192  int result = 1;
     193  for (int j = 1; j <= i; j++) result *= j;
     194  // Now, result = 1 * 2 * ... * i = i!
     195  return result;
     196}
     197
     198int MinorProcessor::NumberOfRetrievals (const int rows, const int columns,
     199                                        const int containerMinorSize,
     200                                        const int minorSize,
     201                                        const bool multipleMinors)
     202{
     203  /* This method computes the number of potential retrievals
     204     of a single minor when computing all minors of a given size
     205     within a matrix of given size. */
     206  int result = 0;
     207  if (multipleMinors)
     208  {
     209    /* Here, we would like to compute all minors of size
     210       containerMinorSize x containerMinorSize in a matrix
     211       of size rows x columns.
     212       Then, we need to retrieve any minor of size
     213       minorSize x minorSize exactly n times, where n is as
     214       follows: */
     215    result = IOverJ(rows - minorSize, containerMinorSize - minorSize)
     216           * IOverJ(columns - minorSize, containerMinorSize - minorSize)
     217           * Faculty(containerMinorSize - minorSize);
     218  }
     219  else
     220  {
     221    /* Here, we would like to compute just one minor of size
     222       containerMinorSize x containerMinorSize. Then, we need
     223       to retrieve any minor of size minorSize x minorSize exactly
     224       (containerMinorSize - minorSize)! times: */
     225    result = Faculty(containerMinorSize - minorSize);
     226  }
     227  return result;
     228}
     229
     230MinorProcessor::MinorProcessor ()
     231{
     232  _container = MinorKey(0, 0, 0, 0);
     233  _minor = MinorKey(0, 0, 0, 0);
     234  _containerRows = 0;
     235  _containerColumns = 0;
     236  _minorSize = 0;
     237  _rows = 0;
     238  _columns = 0;
     239}
     240
     241IntMinorProcessor::IntMinorProcessor ()
     242{
     243  _intMatrix = 0;
     244}
     245
     246string IntMinorProcessor::toString () const
     247{
     248  char h[32];
     249  string t = "";
     250  string s = "IntMinorProcessor:";
     251  s += "\n   matrix: ";
     252  sprintf(h, "%d", _rows); s += h;
     253  s += " x ";
     254  sprintf(h, "%d", _columns); s += h;
     255  for (int r = 0; r < _rows; r++)
     256  {
     257    s += "\n      ";
     258    for (int c = 0; c < _columns; c++)
     259    {
     260      sprintf(h, "%d", getEntry(r, c)); t = h;
     261      for (int k = 0; k < int(4 - strlen(h)); k++) s += " ";
     262      s += t;
     263    }
     264  }
     265  int myIndexArray[500];
     266  s += "\n   considered submatrix has row indices: ";
     267  _container.getAbsoluteRowIndices(myIndexArray);
     268  for (int k = 0; k < _containerRows; k++)
     269  {
     270    if (k != 0) s += ", ";
     271    sprintf(h, "%d", myIndexArray[k]); s += h;
     272  }
     273  s += " (first row of matrix has index 0)";
     274  s += "\n   considered submatrix has column indices: ";
     275  _container.getAbsoluteColumnIndices(myIndexArray);
     276  for (int k = 0; k < _containerColumns; k++)
     277  {
     278    if (k != 0) s += ", ";
     279    sprintf(h, "%d", myIndexArray[k]); s += h;
     280  }
     281  s += " (first column of matrix has index 0)";
     282  s += "\n   size of considered minor(s): ";
     283  sprintf(h, "%d", _minorSize); s += h;
     284  s += "x";
     285  s += h;
     286  return s;
     287}
     288
     289IntMinorProcessor::~IntMinorProcessor()
     290{
     291  /* free memory of _intMatrix */
     292  delete [] _intMatrix; _intMatrix = 0;
     293}
     294
     295bool IntMinorProcessor::isEntryZero (const int absoluteRowIndex,
     296                                     const int absoluteColumnIndex) const
    243297{
    244298  return getEntry(absoluteRowIndex, absoluteColumnIndex) == 0;
    245299}
    246300
    247 void IntMinorProcessor::defineMatrix (const int numberOfRows, const int numberOfColumns, const int* matrix) {
    248     // free memory of _intMatrix
    249     delete [] _intMatrix; _intMatrix = 0;
    250 
    251     _rows = numberOfRows;
    252     _columns = numberOfColumns;
    253 
    254     // allocate memory for new entries in _intMatrix
    255     int n = _rows * _columns;
    256     _intMatrix = new int[n];
    257 
    258     // copying values from one-dimensional method parameter "matrix"
    259     for (int i = 0; i < n; i++)
    260       _intMatrix[i] = matrix[i];
    261 }
    262 
    263 IntMinorValue IntMinorProcessor::getMinor(const int dimension, const int* rowIndices, const int* columnIndices,
    264                                           Cache<MinorKey, IntMinorValue>& c, const int characteristic, const ideal& iSB) {
     301void IntMinorProcessor::defineMatrix (const int numberOfRows,
     302                                      const int numberOfColumns,
     303                                      const int* matrix)
     304{
     305  /* free memory of _intMatrix */
     306  delete [] _intMatrix; _intMatrix = 0;
     307
     308  _rows = numberOfRows;
     309  _columns = numberOfColumns;
     310
     311  /* allocate memory for new entries in _intMatrix */
     312  int n = _rows * _columns;
     313  _intMatrix = new int[n];
     314
     315  /* copying values from one-dimensional method
     316     parameter "matrix" */
     317  for (int i = 0; i < n; i++)
     318    _intMatrix[i] = matrix[i];
     319}