source: git/Singular/CacheImplementation.h @ 308a766

spielwiese
Last change on this file since 308a766 was 308a766, checked in by Oleksandr Motsak <motsak@…>, 11 years ago
Fixing Frank's Minor stuff add: forward declarations fix: includes fix: assert -> assume fix: cout, printf -> use Print(S) fix: removed using namespace std: in headers use std::
  • Property mode set to 100644
File size: 12.5 KB
RevLine 
[f0fd47]1#ifndef CACHE_IMPLEMENTATION_H
2#define CACHE_IMPLEMENTATION_H
3
[308a766]4#include <reporter/reporter.h>
5
[3d9165]6#include <cstdio> // for sprintf
7#include <iostream>
8
[f0fd47]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>
24int Cache<KeyClass, ValueClass>::getWeight() const
25{
26  return _weight;
27}
28
29template<class KeyClass, class ValueClass>
30int Cache<KeyClass, ValueClass>::getNumberOfEntries() const
31{
32  return _rank.size();
33}
34
35template<class KeyClass, class ValueClass>
36void Cache<KeyClass, ValueClass>::clear()
37{
38  _rank.clear();
39  _key.clear();
40  _value.clear();
41  _weights.clear();
42}
43
44template<class KeyClass, class ValueClass>
45Cache<KeyClass, ValueClass>::~Cache()
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
[308a766]57   typename std::list<KeyClass>::const_iterator itKey;
[f0fd47]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 */
[308a766]84    assume(false);
[f0fd47]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>
104int Cache<KeyClass, ValueClass>::getMaxNumberOfEntries() const
105{
106  return _maxEntries;
107}
108
109template<class KeyClass, class ValueClass>
110int Cache<KeyClass, ValueClass>::getMaxWeight() const
111{
112  return _maxWeight;
113}
114
115template<class KeyClass, class ValueClass>
116bool Cache<KeyClass, ValueClass>::deleteLast(const KeyClass& key)
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. */
[308a766]127   std::list<int>::iterator itRank;
[f0fd47]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;
[308a766]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();
[f0fd47]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;
[308a766]180  typename std::list<KeyClass>::iterator itKey;
[f0fd47]181  // itOldValue will later only be used in the case keyWasContained == true: */
[308a766]182  typename std::list<ValueClass>::iterator itOldValue = _value.begin();
[f0fd47]183  /* itOldWeights will later only be used in the case
184     keyWasContained == true */
[308a766]185  typename std::list<int>::iterator itOldWeights = _weights.begin();
[f0fd47]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;
[308a766]207  typename std::list<ValueClass>::iterator itValue = _value.begin();
[f0fd47]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: */
[308a766]233    std::list<int>::iterator itRank;
[f0fd47]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: */
[308a766]310    std::list<int>::iterator itRank;
[f0fd47]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();
[308a766]327    typename std::list<int>::iterator itWeights = _weights.begin();
[f0fd47]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
[308a766]348  assume(_rank.size() == _key.size());
349  assume(_rank.size() == _value.size());
[f0fd47]350  return !result; /* true iff the new (key --> value) pair is
351                     actually in the cache now */
352}
353
354template<class KeyClass, class ValueClass>
[308a766]355std::string Cache<KeyClass, ValueClass>::toString() const
[f0fd47]356{
357  char h[10];
[308a766]358  std::string s = "Cache:";
[f0fd47]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:";
[308a766]375    typename std::list<KeyClass>::const_iterator itKey;
376    typename std::list<ValueClass>::const_iterator itValue = _value.begin();
[f0fd47]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:";
[308a766]389    std::list<int>::const_iterator itRank;
[f0fd47]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>
415void Cache<KeyClass, ValueClass>::print() const
416{
[308a766]417  PrintS(this->toString().c_str());
[f0fd47]418}
419
420template<class KeyClass, class ValueClass>
421Cache<KeyClass, ValueClass>::Cache() { }
422
423template<class KeyClass, class ValueClass>
424Cache<KeyClass, ValueClass>::Cache(const Cache& c)
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 */
Note: See TracBrowser for help on using the repository browser.