source: git/Singular/Cache.h @ 60dcbbc

spielwiese
Last change on this file since 60dcbbc was f0fd47, checked in by Hans Schönemann <hannes@…>, 14 years ago
unix format git-svn-id: file:///usr/local/Singular/svn/trunk@12533 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 13.2 KB
Line 
1#ifndef CACHE_H
2#define CACHE_H
3
4#include <iostream>
5#include <string>
6#include <list>
7#include <assert.h>
8
9using namespace std;
10
11/*! \class Cache
12    \brief Class Cache is a template-implementation of a cache with
13    arbitrary classes for representing keys and values, respectively.
14
15    Each entry of the cache is of the form <em>key --> value</em>,
16    where \e key is an instance of some \c KeyClass, and \e value
17    an instance of some \c ValueClass.<br><br>
18    This implementation comes with the possibility to define bounds
19    on both the number of cached pairs <em>key --> value</em> and on
20    the total \e weight of the cache.<br>
21    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 each value
23    needs to be implemented in the actual class \c ValueClass.
24    An example for the weight of a cached value
25    may simply be its size in bytes, or may capture some other useful notion
26    of how \e heavy the value is. E.g., when caching polynomials, the \e weight
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>
30    In order to enable a fast
31    value lookup, the vector \c _key maintains an ordering such that<br>
32    <em> i < j  ==>  _key[i] < _key[j],</em><br>
33    where the right-hand side comparator
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>
40    <em>_rank : {0, 1, 2, ..., L - 1} --> {0, 1, 2, ..., L - 1}</em><br>
41    is a bijection with the semantic<br>
42    <em>_rank[s] < _rank[t] :<==> _value[_rank[s]] < _value[_rank[t]],</em><br>
43    where the right-hand side comparator \e < needs to be
44    implemented by class \c ValueClass. The intention here is that any relation
45    <em>_rank[s] < _rank[t]</em>
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>
62    <c>bool KeyClass::operator< (const KeyClass& key),</c><br>
63    <c>bool KeyClass::operator== (const KeyClass& key),</c><br>
64    <c>bool ValueClass::operator< (const ValueClass& key),</c><br>
65    <c>bool ValueClass::operator== (const ValueClass& key),</c><br>
66    <c>int ValueClass::getWeight ().</c>
67    \author Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch
68*/
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;
325};
326
327#include <CacheImplementation.h>
328
329#endif
330/* CACHE_H */
Note: See TracBrowser for help on using the repository browser.