My Project
Loading...
Searching...
No Matches
Cache.h
Go to the documentation of this file.
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 */
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 */
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 */
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 advised 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 invocation 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
327
328#endif
329/* CACHE_H */
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:69
Cache()
A constructor for class Cache.
std::string toString() const
A method for providing a printable version of the represented cache, including all contained (key -->...
int getIndexInKey(const KeyClass &key) const
A method for providing the index of a given key in the vector _key.
int getNumberOfEntries() const
A method for retrieving the momentary number of (key --> value) pairs in the cache.
void print() const
A method for printing a string representation of the given cache to std::cout.
void clear()
Clears the cache so that it has no entry.
~Cache()
A destructor for class Cache.
std::list< int > _weights
container for the weights of all cached values
Definition: Cache.h:98
int getIndexInRank(const ValueClass &value) const
A method for providing the index of a given value in the vector _rank.
std::list< ValueClass > _value
_value captures the actual objects of interest; _value[i] corresponds to _key[i] and may be retrieve...
Definition: Cache.h:93
bool put(const KeyClass &key, const ValueClass &value)
Inserts the pair (key --> value) in the cache.
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
std::list< KeyClass >::const_iterator _itKey
a pointer to some element of _key; We make this mutable so that methods which leave the cache unmodif...
Definition: Cache.h:106
int getWeight() const
A method for retrieving the momentary weight of the cache.
std::list< ValueClass >::const_iterator _itValue
a pointer to some element of _value; We make this mutable so that methods which leave the cache unmod...
Definition: Cache.h:114
int _maxWeight
the bound on total cache weight; The cache will automatically ensure that this bound will never be e...
Definition: Cache.h:138
bool deleteLast(const KeyClass &key)
A method for deleting the least-ranked cache entry.
int _maxEntries
the bound for the number of cached key --> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130
int getMaxWeight() const
A method for retrieving the maximum weight of the cache.
bool hasKey(const KeyClass &key) const
Checks whether the cache contains a pair (k --> v) such that k equals the given key.
bool shrink(const KeyClass &key)
A method for shrinking the given cache so that it meet the bounds on the maximum number of entries an...
std::list< KeyClass > _key
_key is sorted in ascending order, i.e., j < i ==> _key(j) < _key(i), where the right-hand side compa...
Definition: Cache.h:85
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i]....
Definition: Cache.h:122
int getMaxNumberOfEntries() const
A method for retrieving the maximum number of (key --> value) pairs in the cache.
ValueClass getValue(const KeyClass &key) const
Returns the value for a given key.