source: git/Singular/CacheImplementation.h @ 4b5098

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