Public Member Functions | Private Member Functions | Private Attributes
Cache< KeyClass, ValueClass > Class Template Reference

Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and values, respectively. More...

#include <Cache.h>

Public Member Functions

 Cache ()
 A constructor for class Cache. More...
 
 ~Cache ()
 A destructor for class Cache. More...
 
 Cache (const Cache &c)
 Copy implementation for class Cache. More...
 
 Cache (const int maxEntries, const int maxWeight)
 A user-suited constructor for class Cache. More...
 
int getWeight () const
 A method for retrieving the momentary weight of the cache. More...
 
int getNumberOfEntries () const
 A method for retrieving the momentary number of (key –> value) pairs in the cache. More...
 
int getMaxNumberOfEntries () const
 A method for retrieving the maximum number of (key –> value) pairs in the cache. More...
 
int getMaxWeight () const
 A method for retrieving the maximum weight of the cache. More...
 
bool hasKey (const KeyClass &key) const
 Checks whether the cache contains a pair (k –> v) such that k equals the given key. More...
 
ValueClass getValue (const KeyClass &key) const
 Returns the value for a given key. More...
 
bool put (const KeyClass &key, const ValueClass &value)
 Inserts the pair (key –> value) in the cache. More...
 
void clear ()
 Clears the cache so that it has no entry. More...
 
std::string toString () const
 A method for providing a printable version of the represented cache, including all contained (key –> value) pairs. More...
 
void print () const
 A method for printing a string representation of the given cache to std::cout. More...
 

Private Member Functions

int getIndexInKey (const KeyClass &key) const
 A method for providing the index of a given key in the vector _key. More...
 
int getIndexInRank (const ValueClass &value) const
 A method for providing the index of a given value in the vector _rank. More...
 
bool shrink (const KeyClass &key)
 A method for shrinking the given cache so that it meet the bounds on the maximum number of entries and total weight again. More...
 
bool deleteLast (const KeyClass &key)
 A method for deleting the least-ranked cache entry. More...
 

Private Attributes

std::list< int > _rank
 A bijection on the set {0, ..., _key.size() - 1}. More...
 
std::list< KeyClass > _key
 _key is sorted in ascending order, i.e., j < i ==> _key(j) < _key(i), where the right-hand side comparator "<" needs to be implemented in KeyClass. More...
 
std::list< ValueClass > _value
 _value captures the actual objects of interest;
_value[i] corresponds to _key[i] and may be retrieved by calling Cache::getValue (const KeyClass&) const with the argument _key[i]). More...
 
std::list< int > _weights
 container for the weights of all cached values More...
 
std::list< KeyClass >::const_iterator _itKey
 a pointer to some element of _key; We make this mutable so that methods which leave the cache unmodified but which alter _itKey can still be declared as const, as the user would expect for these methods. More...
 
std::list< ValueClass >::const_iterator _itValue
 a pointer to some element of _value; We make this mutable so that methods which leave the cache unmodified but which alter _itValue can still be declared as const, as the user would expect for these methods. More...
 
int _weight
 for storing the momentary weight of the given cache;
This is the sum of _value[i].getWeight() over all i, i.e., over all cached values. More...
 
int _maxEntries
 the bound for the number of cached key –> value pairs;
The cache will automatically ensure that this bound will never be exceeded; see Cache::shrink (const KeyClass&) and Cache::deleteLast (). More...
 
int _maxWeight
 the bound on total cache weight;
The cache will automatically ensure that this bound will never be exceeded; see see Cache::shrink (const KeyClass&) and Cache::deleteLast (). More...
 

Detailed Description

template<class KeyClass, class ValueClass>
class Cache< KeyClass, ValueClass >

Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and values, respectively.

Each entry of the cache is of the form key –> value, where key is an instance of some KeyClass, and value an instance of some ValueClass.

This implementation comes with the possibility to define bounds on both the number of cached pairs key –> value and on the total weight of the cache.
Here, the weight of a cache is defined as the sum of weights of all cached values, where the weight of each value needs to be implemented in the actual class ValueClass. An example for the weight of a cached value may simply be its size in bytes, or may capture some other useful notion of how heavy the value is. E.g., when caching polynomials, the weight may be defined to be equal to the number of its monomials.

The key –> value pairs of a cache are being stored in two standard lists _key and _value of equal length L.
In order to enable a fast value lookup, the vector _key maintains an ordering such that
i < j ==> _key[i] < _key[j],
where the right-hand side comparator < needs to be implemented by class KeyClass. Note that this ordering allows for value lookup in time O(log(L)), when given a specific key.

In addition to _key and _value, there is a third book-keeping structure in Cache: The vector _rank of integers captures ranking information among all cached values. More concretely,
_rank : {0, 1, 2, ..., L - 1} –> {0, 1, 2, ..., L - 1}
is a bijection with the semantic
_rank[s] < _rank[t] :<==> _value[_rank[s]] < _value[_rank[t]],
where the right-hand side comparator < needs to be implemented by class ValueClass. The intention here is that any relation _rank[s] < _rank[t] is to imply that the key-value pair _key[_rank[t]] –> _value[_rank[t]] will be kept at least as long in cache as _key[_rank[s]] –> _value[_rank[s]]. (I.e., loosely speaking, the higher the rank, the longer a pair is going to be cached.)

Whenever the cache becomes either too large (in terms of number of entries), or too heavy (in terms of accumulated weight), it will automatically shrink until both bounds will have been re-established. To this end, the key –> value pair with least value rank will be erased from the cache. This process is repeated until the cache is small enough again, in terms of both the number of entries and the weight. (Note that it may be necessary to erase numerous pairs after inserting just one key –> value when this value's weight is unproportionally high.)

In order to make the above procedures work, the two template classes KeyClass and ValueClass need to implement the following methods:
bool KeyClass::operator< (const KeyClass& key),
bool KeyClass::operator== (const KeyClass& key),
bool ValueClass::operator< (const ValueClass& key),
bool ValueClass::operator== (const ValueClass& key),
int ValueClass::getWeight ().

Author
Frank Seelisch, http://www.mathematik.uni-kl.de/~seelisch

Definition at line 68 of file Cache.h.

Constructor & Destructor Documentation

◆ Cache() [1/3]

template<class KeyClass , class ValueClass >
Cache< KeyClass, ValueClass >::Cache ( )

A constructor for class Cache.

The method makes sure that all member vectors be empty.

Definition at line 421 of file CacheImplementation.h.

421 { }

◆ ~Cache()

template<class KeyClass , class ValueClass >
Cache< KeyClass, ValueClass >::~Cache ( )

A destructor for class Cache.

The method clears all member vectors. (This includes that destructors are invoked, accordingly.)

Definition at line 45 of file CacheImplementation.h.

46 {
47  _rank.clear();
48  _key.clear();
49  _value.clear();
50  _weights.clear();
51 }
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
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
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

◆ Cache() [2/3]

template<class KeyClass , class ValueClass >
Cache< KeyClass, ValueClass >::Cache ( const Cache< KeyClass, ValueClass > &  c)

Copy implementation for class Cache.

Apart from copying all flat members, all vectors are being deep-copied.

Definition at line 424 of file CacheImplementation.h.

425 {
426  _rank = c._rank;
427  _value = c._value;
428  _weights = c._weights;
429  _key = c._key;
430  _weight = c._weight;
433 }
int _maxEntries
the bound for the number of cached key –> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130
int _maxWeight
the bound on total cache weight; The cache will automatically ensure that this bound will never be e...
Definition: Cache.h:138
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
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
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].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

◆ Cache() [3/3]

template<class KeyClass , class ValueClass >
Cache< KeyClass, ValueClass >::Cache ( const int  maxEntries,
const int  maxWeight 
)

A user-suited constructor for class Cache.

The method makes sure that all member vectors be empty. Moreover, the user can provide bounds for the maximum number of entries in the cache, and for the total weight of the cache.

Parameters
maxEntriesthe (positive) maximum number of pairs (key –> value) in the cache
maxWeightthe (positive) maximum weight of the cache

Definition at line 10 of file CacheImplementation.h.

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 }
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 _maxEntries
the bound for the number of cached key –> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130
int _maxWeight
the bound on total cache weight; The cache will automatically ensure that this bound will never be e...
Definition: Cache.h:138
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
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
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
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].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

Member Function Documentation

◆ clear()

template<class KeyClass , class ValueClass >
void Cache< KeyClass, ValueClass >::clear ( )

Clears the cache so that it has no entry.

This method will also enforce destruction of all former entries of the cache.

Definition at line 36 of file CacheImplementation.h.

37 {
38  _rank.clear();
39  _key.clear();
40  _value.clear();
41  _weights.clear();
42 }
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
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
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

◆ deleteLast()

template<class KeyClass , class ValueClass >
bool Cache< KeyClass, ValueClass >::deleteLast ( const KeyClass &  key)
private

A method for deleting the least-ranked cache entry.

The method returns true iff the deleted pair (k –> v) satisfies k == key.

Parameters
keyan instance of KeyClass
Returns
true iff a pair (key –> *) was deleted

Definition at line 116 of file CacheImplementation.h.

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 }
int k
Definition: cfEzgcd.cc:93
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
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
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
return result
Definition: facAbsBiFact.cc:76
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

◆ getIndexInKey()

template<class KeyClass, class ValueClass>
int Cache< KeyClass, ValueClass >::getIndexInKey ( const KeyClass &  key) const
private

A method for providing the index of a given key in the vector _key.

Either _key contains the given key, then its index will be returned. Otherwise the position in _key, at which the given key should be placed (with respect to the ordering in _key) is returned.

Parameters
keyan instance of KeyClass
Returns
the actual or would-be index of key in _key
See also
Cache::hasKey (const KeyClass&) const

◆ getIndexInRank()

template<class KeyClass, class ValueClass>
int Cache< KeyClass, ValueClass >::getIndexInRank ( const ValueClass &  value) const
private

A method for providing the index of a given value in the vector _rank.

Based on the rank of the given value, the position in _rank at which the given value should be inserted, is returned. (The method also works, when the given value is already contained in the cache.)

Parameters
valuean instance of ValueClass
Returns
the actual or would-be index of value in _rank

◆ getMaxNumberOfEntries()

template<class KeyClass , class ValueClass >
int Cache< KeyClass, ValueClass >::getMaxNumberOfEntries ( ) const

A method for retrieving the maximum number of (key –> value) pairs in the cache.

Returns
the maximum number of cached values of the cache
See also
Cache::getNumberOfEntries () const
Cache::Cache (const int, const int)

Definition at line 104 of file CacheImplementation.h.

105 {
106  return _maxEntries;
107 }
int _maxEntries
the bound for the number of cached key –> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130

◆ getMaxWeight()

template<class KeyClass , class ValueClass >
int Cache< KeyClass, ValueClass >::getMaxWeight ( ) const

A method for retrieving the maximum weight of the cache.

Returns
the maximum weight of the cache
See also
Cache::getWeight () const
Cache::Cache (const int, const int)

Definition at line 110 of file CacheImplementation.h.

111 {
112  return _maxWeight;
113 }
int _maxWeight
the bound on total cache weight; The cache will automatically ensure that this bound will never be e...
Definition: Cache.h:138

◆ getNumberOfEntries()

template<class KeyClass , class ValueClass >
int Cache< KeyClass, ValueClass >::getNumberOfEntries ( ) const

A method for retrieving the momentary number of (key –> value) pairs in the cache.

The return value will always be less than or equal to the result of Cache::getMaxNumberOfEntries () const.

Returns
the momentary number of cached values of the cache
See also
Cache::getMaxNumberOfEntries () const

Definition at line 30 of file CacheImplementation.h.

31 {
32  return _rank.size();
33 }
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77

◆ getValue()

template<class KeyClass , class ValueClass >
ValueClass Cache< KeyClass, ValueClass >::getValue ( const KeyClass &  key) const

Returns the value for a given key.

The method assumes that there is actually an entry of the form (key –> *) in the cache. This can be checked before using Cache::hasKey (const KeyClass&) const. (Note that calling both methods in direct succession does not result in extra computational efforts.)

Assertions
If the given key is not contained in the cache, program execution will be stopped.
Parameters
keythe key, for which the corresponding value is to be returned
Returns
the value corresponding to the given key
See also
Cache::hasKey (const KeyClass&) const

Definition at line 78 of file CacheImplementation.h.

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 }
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
#define assume(x)
Definition: mod2.h:394
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
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

◆ getWeight()

template<class KeyClass , class ValueClass >
int Cache< KeyClass, ValueClass >::getWeight ( ) const

A method for retrieving the momentary weight of the cache.

The return value will always be less than or equal to the result of Cache::getMaxWeight () const.
Semantically, the total weight of a cache is the sum of weights of all cached values.

Returns
the momentary weight of the cache
See also
Cache::getMaxWeight () const
MinorValue::getWeight () const

Definition at line 24 of file CacheImplementation.h.

25 {
26  return _weight;
27 }
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

◆ hasKey()

template<class KeyClass , class ValueClass >
bool Cache< KeyClass, ValueClass >::hasKey ( const KeyClass &  key) const

Checks whether the cache contains a pair (k –> v) such that k equals the given key.

If so, the method returns true; false otherwise. In order to make Cache::getValue (const KeyClass&) const work properly, the user is strongly adviced to always check key containment by means of Cache::hasKey (const KeyClass&) const. (The implementation at hand ensures that invoking hasKey and getValue does not result in extra computational efforts.)

Parameters
keythe key for which containment is to be checked
Returns
true iff the cache contains the given key
See also
Cache::getValue (const KeyClass&) const

Definition at line 54 of file CacheImplementation.h.

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 }
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
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
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
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

◆ print()

template<class KeyClass , class ValueClass >
void Cache< KeyClass, ValueClass >::print ( ) const

A method for printing a string representation of the given cache to std::cout.

This includes string representations of all contained (key –> value) pairs.

Definition at line 415 of file CacheImplementation.h.

416 {
417  PrintS(this->toString().c_str());
418 }
std::string toString() const
A method for providing a printable version of the represented cache, including all contained (key –>...
void PrintS(const char *s)
Definition: reporter.cc:284

◆ put()

template<class KeyClass , class ValueClass >
bool Cache< KeyClass, ValueClass >::put ( const KeyClass &  key,
const ValueClass &  value 
)

Inserts the pair (key –> value) in the cache.

If there is already some entry (key –> value'), then value will be replaced by value'. As putting some new pair in the cache may result in a violation of the maximal number of entries or the weight of the cache, or both, Cache::put (const KeyClass&, const ValueClass&) will always finalize by calling the private method Cache::shrink(const KeyClass&), in order to re-establish both bounds. Note that this may even result in deleting the newly inserted pair (key –> value).
Because of that undesirable but possible effect, the method returns whether the pair is actually contained in the cache after invokation of Cache::put (const KeyClass&, const ValueClass&).

Parameters
keyan instance of KeyClass
valuean instance of ValueClass
Returns
whether the pair (key –> value) is contained in the modified cache
See also
Cache::getValue (const KeyClass&) const

Definition at line 170 of file CacheImplementation.h.

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 }
int k
Definition: cfEzgcd.cc:93
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
#define assume(x)
Definition: mod2.h:394
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 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
return result
Definition: facAbsBiFact.cc:76
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

◆ shrink()

template<class KeyClass , class ValueClass >
bool Cache< KeyClass, ValueClass >::shrink ( const KeyClass &  key)
private

A method for shrinking the given cache so that it meet the bounds on the maximum number of entries and total weight again.

The method returns true iff the process of shrinking deleted a pair (k –> v) from the cache such that k equals the given key.

Parameters
keyan instance of KeyClass
Returns
true iff shrinking deleted a pair (key –> *)

Definition at line 90 of file CacheImplementation.h.

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 }
int _maxEntries
the bound for the number of cached key –> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130
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.
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
return result
Definition: facAbsBiFact.cc:76
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122

◆ toString()

template<class KeyClass , class ValueClass >
std::string Cache< KeyClass, ValueClass >::toString ( ) const

A method for providing a printable version of the represented cache, including all contained (key –> value) pairs.

Returns
a printable version of the given instance as instance of class string

Definition at line 355 of file CacheImplementation.h.

356 {
357  char h[12];
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 }
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define string
Definition: libparse.cc:1250
int k
Definition: cfEzgcd.cc:93
int getNumberOfEntries() const
A method for retrieving the momentary number of (key –> value) pairs in the cache.
const ring r
Definition: syzextra.cc:208
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
int getMaxNumberOfEntries() const
A method for retrieving the maximum number of (key –> value) pairs in the cache. ...
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
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
int getMaxWeight() const
A method for retrieving the maximum weight of the cache.
int getWeight() const
A method for retrieving the momentary weight of the cache.
static Poly * h
Definition: janet.cc:978
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

Field Documentation

◆ _itKey

template<class KeyClass, class ValueClass>
std::list<KeyClass>::const_iterator Cache< KeyClass, ValueClass >::_itKey
mutableprivate

a pointer to some element of _key; We make this mutable so that methods which leave the cache unmodified but which alter _itKey can still be declared as const, as the user would expect for these methods.

Definition at line 106 of file Cache.h.

◆ _itValue

template<class KeyClass, class ValueClass>
std::list<ValueClass>::const_iterator Cache< KeyClass, ValueClass >::_itValue
mutableprivate

a pointer to some element of _value; We make this mutable so that methods which leave the cache unmodified but which alter _itValue can still be declared as const, as the user would expect for these methods.

Definition at line 114 of file Cache.h.

◆ _key

template<class KeyClass, class ValueClass>
std::list<KeyClass> Cache< KeyClass, ValueClass >::_key
private

_key is sorted in ascending order, i.e., j < i ==> _key(j) < _key(i), where the right-hand side comparator "<" needs to be implemented in KeyClass.

Definition at line 85 of file Cache.h.

◆ _maxEntries

template<class KeyClass, class ValueClass>
int Cache< KeyClass, ValueClass >::_maxEntries
private

the bound for the number of cached key –> value pairs;
The cache will automatically ensure that this bound will never be exceeded; see Cache::shrink (const KeyClass&) and Cache::deleteLast ().

Definition at line 130 of file Cache.h.

◆ _maxWeight

template<class KeyClass, class ValueClass>
int Cache< KeyClass, ValueClass >::_maxWeight
private

the bound on total cache weight;
The cache will automatically ensure that this bound will never be exceeded; see see Cache::shrink (const KeyClass&) and Cache::deleteLast ().

Definition at line 138 of file Cache.h.

◆ _rank

template<class KeyClass, class ValueClass>
std::list<int> Cache< KeyClass, ValueClass >::_rank
private

A bijection on the set {0, ..., _key.size() - 1}.


Semantically, _rank(j) > _rank(i) means that the pair key(_rank(j)) –> value(_rank(j)) will be cached at least as long as the pair key(_rank(i)) –> value(_rank(i)).

Definition at line 77 of file Cache.h.

◆ _value

template<class KeyClass, class ValueClass>
std::list<ValueClass> Cache< KeyClass, ValueClass >::_value
private

_value captures the actual objects of interest;
_value[i] corresponds to _key[i] and may be retrieved by calling Cache::getValue (const KeyClass&) const with the argument _key[i]).

Definition at line 93 of file Cache.h.

◆ _weight

template<class KeyClass, class ValueClass>
int Cache< KeyClass, ValueClass >::_weight
private

for storing the momentary weight of the given cache;
This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.

Equivalently, this is equal to all weights stored in _weights.

Definition at line 122 of file Cache.h.

◆ _weights

template<class KeyClass, class ValueClass>
std::list<int> Cache< KeyClass, ValueClass >::_weights
private

container for the weights of all cached values

Definition at line 98 of file Cache.h.


The documentation for this class was generated from the following files: