source: git/Singular/CacheImplementation.h @ e2afced

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