source: git/kernel/linear_algebra/Cache.h @ aa8a7e

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