source: git/Singular/CacheImplementation.h @ 020ef9

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