Changeset 68ec38 in git for Singular/CacheImplementation.h


Ignore:
Timestamp:
Feb 2, 2010, 2:22:24 PM (14 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
13e38971987d79bd6f926205a82e193ea34b07bd
Parents:
13d171b75aff221780f5e6852dfb845024c5771b
Message:
documentation and style guide conformance

git-svn-id: file:///usr/local/Singular/svn/trunk@12501 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/CacheImplementation.h

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