Changeset 68ec38 in git for Singular/Cache.h


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

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

Legend:

Unmodified
Added
Removed

  • Singular/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
Note: See TracChangeset for help on using the changeset viewer.