1#ifndef CACHE_IMPLEMENTATION_H
2#define CACHE_IMPLEMENTATION_H
9template<
class KeyClass,
class ValueClass>
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;
63 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
65 int c = key.compare(*itKey);
71 if (c == -1)
return false;
77template<
class KeyClass,
class ValueClass>
89template<
class KeyClass,
class ValueClass>
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;
128 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++) { }
130 int deleteIndex = *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();
139 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
141 if (
k == deleteIndex)
143 result = (key.compare(*itKey) == 0);
151 int deleteWeight = *itWeights;
161 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
163 if (*itRank > deleteIndex) *itRank -= 1;
169template<
class KeyClass,
class ValueClass>
171 const ValueClass& value)
173 bool keyWasContained =
false;
174 int oldIndexInKey = -1;
175 int newIndexInKey =
_key.size();
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();
186 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
188 int c = key.compare(*itKey);
196 keyWasContained =
true;
204 int utility = value.getUtility();
205 int newWeight = value.getWeight();
207 typename std::list<ValueClass>::iterator itValue =
_value.begin();
208 for (itValue =
_value.begin(); itValue !=
_value.end(); itValue++)
210 if (itValue->getUtility() > utility)
k++;
212 int newIndexInRank =
k;
219 ValueClass oldValue = *itOldValue;
220 _weight += newWeight - *itOldWeights;
223 itOldValue =
_value.erase(itOldValue);
224 itOldWeights =
_weights.erase(itOldWeights);
225 ValueClass myValueCopy = value;
226 _value.insert(itOldValue, myValueCopy);
227 _weights.insert(itOldWeights, newWeight);
229 int oldIndexInRank = -1;
233 std::list<int>::iterator itRank;
235 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
237 if (*itRank == oldIndexInKey)
246 if (oldIndexInRank < newIndexInRank)
250 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
252 if (
k == newIndexInRank)
break;
255 _rank.insert(itRank, oldIndexInKey);
262 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
264 if (
k == oldIndexInRank)
274 if (oldIndexInRank > newIndexInRank)
278 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
280 if (
k == oldIndexInRank)
289 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
291 if (
k == newIndexInRank)
293 _rank.insert(itRank, oldIndexInKey);
310 std::list<int>::iterator itRank;
311 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
313 if (newIndexInKey <= *itRank)
319 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
321 if (
k == newIndexInRank)
break;
324 _rank.insert(itRank, newIndexInKey);
327 typename std::list<int>::iterator itWeights =
_weights.begin();
329 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
331 if (
k == newIndexInKey)
break;
336 KeyClass myKeyCopy = key;
337 ValueClass myValueCopy = value;
338 _key.insert(itKey, myKeyCopy);
339 _value.insert(itValue, myValueCopy);
340 _weights.insert(itWeights, newWeight);
354template<
class KeyClass,
class ValueClass>
358 std::string
s =
"Cache:";
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();
377 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
380 snprintf(
h,12,
"%d",
k);
s +=
h;
382 s += itKey->toString();
384 s += itValue->toString();
388 s +=
"\n (key --> value) pairs in descending order of ranks:";
389 std::list<int>::const_iterator itRank;
391 for (itRank =
_rank.begin(); itRank !=
_rank.end(); itRank++)
396 for (itKey =
_key.begin(); itKey !=
_key.end(); itKey++)
403 snprintf(
h,12,
"%d", r);
s +=
h;
405 s += itKey->toString();
407 s += itValue->toString();
414template<
class KeyClass,
class ValueClass>
420template<
class KeyClass,
class ValueClass>
423template<
class KeyClass,
class ValueClass>
std::string toString(const gfan::ZCone *const c)
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}.
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...
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...
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)