1#ifndef CACHE_IMPLEMENTATION_H
2#define CACHE_IMPLEMENTATION_H
9template<
class KeyClass,
class ValueClass>
19 _itValue = _value.end();
23template<
class KeyClass,
class ValueClass>
29template<
class KeyClass,
class ValueClass>
35template<
class KeyClass,
class ValueClass>
44template<
class KeyClass,
class ValueClass>
53template<
class KeyClass,
class ValueClass>
57 typename std::list<KeyClass>::const_iterator
itKey;
58 _itValue = _value.begin();
65 int c = key.compare(*
itKey);
71 if (c == -1)
return false;
77template<
class KeyClass,
class ValueClass>
80 if (_itKey == _key.end())
89template<
class KeyClass,
class ValueClass>
96 while (
int(_key.size()) > _maxEntries || _weight > _maxWeight)
98 if (deleteLast(key))
result =
true;
103template<
class KeyClass,
class ValueClass>
109template<
class KeyClass,
class ValueClass>
115template<
class KeyClass,
class ValueClass>
118 if (_rank.size() == 0)
127 std::list<int>::iterator
itRank;
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();
169template<
class KeyClass,
class ValueClass>
180 typename std::list<KeyClass>::iterator
itKey;
182 typename std::list<ValueClass>::iterator
itOldValue = _value.begin();
185 typename std::list<int>::iterator
itOldWeights = _weights.begin();
188 int c = key.compare(*
itKey);
204 int utility = value.getUtility();
207 typename std::list<ValueClass>::iterator
itValue = _value.begin();
233 std::list<int>::iterator
itRank;
310 std::list<int>::iterator
itRank;
327 typename std::list<int>::iterator
itWeights = _weights.begin();
345 bool result = shrink(key);
348 assume(_rank.size() == _key.size());
349 assume(_rank.size() == _value.size());
354template<
class KeyClass,
class ValueClass>
358 std::string
s =
"Cache:";
360 sprintf(
h,
"%d", getNumberOfEntries());
s +=
h;
362 sprintf(
h,
"%d", getMaxNumberOfEntries());
s +=
h;
367 if (_key.size() == 0)
369 s +=
"\n no pairs, i.e. cache is empty";
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();
388 s +=
"\n (key --> value) pairs in descending order of ranks:";
389 std::list<int>::const_iterator
itRank;
414template<
class KeyClass,
class ValueClass>
420template<
class KeyClass,
class ValueClass>
423template<
class KeyClass,
class ValueClass>
std::string toString(const gfan::ZCone *const c)
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
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
std::list< ValueClass > _value
_value captures the actual objects of interest; _value[i] corresponds to _key[i] and may be retrieve...
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}.
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...
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...
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...
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i]....
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.
const CanonicalForm int s
static int index(p_Length length, p_Ord ord)
void PrintS(const char *s)