118 if (_rank.size() == 0)
127 std::list<int>::iterator itRank;
128 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) { }
130 int deleteIndex = *itRank;
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++)
141 if (
k == deleteIndex)
143 result = (key.compare(*itKey) == 0);
151 int deleteWeight = *itWeights;
152 _value.erase(itValue);
153 _weights.erase(itWeights);
156 _weight -= deleteWeight;
161 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
163 if (*itRank > deleteIndex) *itRank -= 1;
171 const ValueClass& value)
173 bool keyWasContained =
false;
174 int oldIndexInKey = -1;
175 int newIndexInKey = _key.size();
180 typename std::list<KeyClass>::iterator itKey;
182 typename std::list<ValueClass>::iterator itOldValue = _value.begin();
185 typename std::list<int>::iterator itOldWeights = _weights.begin();
186 for (itKey = _key.begin(); itKey != _key.end(); itKey++)
188 int c = key.compare(*itKey);
196 keyWasContained =
true;
204 int utility = value.getUtility();
205 int newWeight = value.getWeight();
207 typename std::list<ValueClass>::iterator itValue = _value.begin();
208 for (itValue = _value.begin(); itValue != _value.end(); itValue++)
210 if (itValue->getUtility() > utility)
k++;
212 int newIndexInRank =
k;
219 ValueClass oldValue = *itOldValue;
220 _weight += newWeight - *itOldWeights;
223 itOldValue = _value.erase(itOldValue);
224 itOldWeights = _weights.erase(itOldWeights);
225 ValueClass myValueCopy = value;
226 _value.insert(itOldValue, myValueCopy);
227 _weights.insert(itOldWeights, newWeight);
229 int oldIndexInRank = -1;
233 std::list<int>::iterator itRank;
235 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
237 if (*itRank == oldIndexInKey)
246 if (oldIndexInRank < newIndexInRank)
250 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
252 if (
k == newIndexInRank)
break;
255 _rank.insert(itRank, oldIndexInKey);
262 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
264 if (
k == oldIndexInRank)
274 if (oldIndexInRank > newIndexInRank)
278 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
280 if (
k == oldIndexInRank)
289 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
291 if (
k == newIndexInRank)
293 _rank.insert(itRank, oldIndexInKey);
310 std::list<int>::iterator itRank;
311 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
313 if (newIndexInKey <= *itRank)
319 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
321 if (
k == newIndexInRank)
break;
324 _rank.insert(itRank, newIndexInKey);
326 itValue = _value.begin();
327 typename std::list<int>::iterator itWeights = _weights.begin();
329 for (itKey = _key.begin(); itKey != _key.end(); itKey++)
331 if (
k == newIndexInKey)
break;
336 KeyClass myKeyCopy = key;
337 ValueClass myValueCopy = value;
338 _key.insert(itKey, myKeyCopy);
339 _value.insert(itValue, myValueCopy);
340 _weights.insert(itWeights, newWeight);
342 _weight += newWeight;
345 bool result = shrink(key);
348 assume(_rank.size() == _key.size());
349 assume(_rank.size() == _value.size());
358 std::string
s =
"Cache:";
360 sprintf(
h,
"%d", getNumberOfEntries());
s +=
h;
362 sprintf(
h,
"%d", getMaxNumberOfEntries());
s +=
h;
364 sprintf(
h,
"%d", getWeight());
s +=
h;
366 sprintf(
h,
"%d", getMaxWeight());
s +=
h;
367 if (_key.size() == 0)
369 s +=
"\n no pairs, i.e. cache is empty";
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++)
380 sprintf(
h,
"%d",
k);
s +=
h;
382 s += itKey->toString();
384 s += itValue->toString();
388 s +=
"\n (key --> value) pairs in descending order of ranks:";
389 std::list<int>::const_iterator itRank;
391 for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
394 itValue = _value.begin();
396 for (itKey = _key.begin(); itKey != _key.end(); itKey++)
403 sprintf(
h,
"%d", r);
s +=
h;
405 s += itKey->toString();
407 s += itValue->toString();