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