COIN-OR::LEMON - Graph Library

Changeset 711:28cfac049a6a in lemon-1.2 for lemon/radix_heap.h


Ignore:
Timestamp:
07/08/09 17:47:01 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Unify member names in heaps (#299)

The following renamings are made.

Public members:

Private members:

  • bubble_up() -> bubbleUp()
  • bubble_down() -> bubbleDown()
  • second_child() -> secondChild()
  • makeroot() -> makeRoot()
  • relocate_last() -> relocateLast()
  • data -> _data
  • boxes -> _boxes
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/radix_heap.h

    r710 r711  
    5959    /// RadixHeap with a priority smaller than the last erased one.
    6060    /// \see RadixHeap
    61     class UnderFlowPriorityError : public Exception {
     61    class PriorityUnderflowError : public Exception {
    6262    public:
    6363      virtual const char* what() const throw() {
    64         return "lemon::RadixHeap::UnderFlowPriorityError";
     64        return "lemon::RadixHeap::PriorityUnderflowError";
    6565      }
    6666    };
     
    9595    };
    9696
    97     std::vector<RadixItem> data;
    98     std::vector<RadixBox> boxes;
     97    std::vector<RadixItem> _data;
     98    std::vector<RadixBox> _boxes;
    9999
    100100    ItemIntMap &_iim;
     
    113113      : _iim(map)
    114114    {
    115       boxes.push_back(RadixBox(minimum, 1));
    116       boxes.push_back(RadixBox(minimum + 1, 1));
    117       while (lower(boxes.size() - 1, capacity + minimum - 1)) {
     115      _boxes.push_back(RadixBox(minimum, 1));
     116      _boxes.push_back(RadixBox(minimum + 1, 1));
     117      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
    118118        extend();
    119119      }
     
    123123    ///
    124124    /// This function returns the number of items stored in the heap.
    125     int size() const { return data.size(); }
     125    int size() const { return _data.size(); }
    126126
    127127    /// \brief Check if the heap is empty.
    128128    ///
    129129    /// This function returns \c true if the heap is empty.
    130     bool empty() const { return data.empty(); }
     130    bool empty() const { return _data.empty(); }
    131131
    132132    /// \brief Make the heap empty.
     
    140140    /// \param capacity The capacity of the heap.
    141141    void clear(int minimum = 0, int capacity = 0) {
    142       data.clear(); boxes.clear();
    143       boxes.push_back(RadixBox(minimum, 1));
    144       boxes.push_back(RadixBox(minimum + 1, 1));
    145       while (lower(boxes.size() - 1, capacity + minimum - 1)) {
     142      _data.clear(); _boxes.clear();
     143      _boxes.push_back(RadixBox(minimum, 1));
     144      _boxes.push_back(RadixBox(minimum + 1, 1));
     145      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
    146146        extend();
    147147      }
     
    151151
    152152    bool upper(int box, Prio pr) {
    153       return pr < boxes[box].min;
     153      return pr < _boxes[box].min;
    154154    }
    155155
    156156    bool lower(int box, Prio pr) {
    157       return pr >= boxes[box].min + boxes[box].size;
     157      return pr >= _boxes[box].min + _boxes[box].size;
    158158    }
    159159
    160160    // Remove item from the box list
    161161    void remove(int index) {
    162       if (data[index].prev >= 0) {
    163         data[data[index].prev].next = data[index].next;
     162      if (_data[index].prev >= 0) {
     163        _data[_data[index].prev].next = _data[index].next;
    164164      } else {
    165         boxes[data[index].box].first = data[index].next;
    166       }
    167       if (data[index].next >= 0) {
    168         data[data[index].next].prev = data[index].prev;
     165        _boxes[_data[index].box].first = _data[index].next;
     166      }
     167      if (_data[index].next >= 0) {
     168        _data[_data[index].next].prev = _data[index].prev;
    169169      }
    170170    }
     
    172172    // Insert item into the box list
    173173    void insert(int box, int index) {
    174       if (boxes[box].first == -1) {
    175         boxes[box].first = index;
    176         data[index].next = data[index].prev = -1;
     174      if (_boxes[box].first == -1) {
     175        _boxes[box].first = index;
     176        _data[index].next = _data[index].prev = -1;
    177177      } else {
    178         data[index].next = boxes[box].first;
    179         data[boxes[box].first].prev = index;
    180         data[index].prev = -1;
    181         boxes[box].first = index;
    182       }
    183       data[index].box = box;
     178        _data[index].next = _boxes[box].first;
     179        _data[_boxes[box].first].prev = index;
     180        _data[index].prev = -1;
     181        _boxes[box].first = index;
     182      }
     183      _data[index].box = box;
    184184    }
    185185
    186186    // Add a new box to the box list
    187187    void extend() {
    188       int min = boxes.back().min + boxes.back().size;
    189       int bs = 2 * boxes.back().size;
    190       boxes.push_back(RadixBox(min, bs));
     188      int min = _boxes.back().min + _boxes.back().size;
     189      int bs = 2 * _boxes.back().size;
     190      _boxes.push_back(RadixBox(min, bs));
    191191    }
    192192
    193193    // Move an item up into the proper box.
    194     void bubble_up(int index) {
    195       if (!lower(data[index].box, data[index].prio)) return;
     194    void bubbleUp(int index) {
     195      if (!lower(_data[index].box, _data[index].prio)) return;
    196196      remove(index);
    197       int box = findUp(data[index].box, data[index].prio);
     197      int box = findUp(_data[index].box, _data[index].prio);
    198198      insert(box, index);
    199199    }
     
    202202    int findUp(int start, int pr) {
    203203      while (lower(start, pr)) {
    204         if (++start == int(boxes.size())) {
     204        if (++start == int(_boxes.size())) {
    205205          extend();
    206206        }
     
    210210
    211211    // Move an item down into the proper box
    212     void bubble_down(int index) {
    213       if (!upper(data[index].box, data[index].prio)) return;
     212    void bubbleDown(int index) {
     213      if (!upper(_data[index].box, _data[index].prio)) return;
    214214      remove(index);
    215       int box = findDown(data[index].box, data[index].prio);
     215      int box = findDown(_data[index].box, _data[index].prio);
    216216      insert(box, index);
    217217    }
     
    220220    int findDown(int start, int pr) {
    221221      while (upper(start, pr)) {
    222         if (--start < 0) throw UnderFlowPriorityError();
     222        if (--start < 0) throw PriorityUnderflowError();
    223223      }
    224224      return start;
     
    228228    int findFirst() {
    229229      int first = 0;
    230       while (boxes[first].first == -1) ++first;
     230      while (_boxes[first].first == -1) ++first;
    231231      return first;
    232232    }
     
    234234    // Gives back the minimum priority of the given box
    235235    int minValue(int box) {
    236       int min = data[boxes[box].first].prio;
    237       for (int k = boxes[box].first; k != -1; k = data[k].next) {
    238         if (data[k].prio < min) min = data[k].prio;
     236      int min = _data[_boxes[box].first].prio;
     237      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
     238        if (_data[k].prio < min) min = _data[k].prio;
    239239      }
    240240      return min;
     
    247247      int min = minValue(box);
    248248      for (int i = 0; i <= box; ++i) {
    249         boxes[i].min = min;
    250         min += boxes[i].size;
    251       }
    252       int curr = boxes[box].first, next;
     249        _boxes[i].min = min;
     250        min += _boxes[i].size;
     251      }
     252      int curr = _boxes[box].first, next;
    253253      while (curr != -1) {
    254         next = data[curr].next;
    255         bubble_down(curr);
     254        next = _data[curr].next;
     255        bubbleDown(curr);
    256256        curr = next;
    257257      }
    258258    }
    259259
    260     void relocate_last(int index) {
    261       if (index != int(data.size()) - 1) {
    262         data[index] = data.back();
    263         if (data[index].prev != -1) {
    264           data[data[index].prev].next = index;
     260    void relocateLast(int index) {
     261      if (index != int(_data.size()) - 1) {
     262        _data[index] = _data.back();
     263        if (_data[index].prev != -1) {
     264          _data[_data[index].prev].next = index;
    265265        } else {
    266           boxes[data[index].box].first = index;
     266          _boxes[_data[index].box].first = index;
    267267        }
    268         if (data[index].next != -1) {
    269           data[data[index].next].prev = index;
     268        if (_data[index].next != -1) {
     269          _data[_data[index].next].prev = index;
    270270        }
    271         _iim[data[index].item] = index;
    272       }
    273       data.pop_back();
     271        _iim[_data[index].item] = index;
     272      }
     273      _data.pop_back();
    274274    }
    275275
     
    285285    /// \warning This method may throw an \c UnderFlowPriorityException.
    286286    void push(const Item &i, const Prio &p) {
    287       int n = data.size();
     287      int n = _data.size();
    288288      _iim.set(i, n);
    289       data.push_back(RadixItem(i, p));
    290       while (lower(boxes.size() - 1, p)) {
     289      _data.push_back(RadixItem(i, p));
     290      while (lower(_boxes.size() - 1, p)) {
    291291        extend();
    292292      }
    293       int box = findDown(boxes.size() - 1, p);
     293      int box = findDown(_boxes.size() - 1, p);
    294294      insert(box, n);
    295295    }
     
    301301    Item top() const {
    302302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    303       return data[boxes[0].first].item;
     303      return _data[_boxes[0].first].item;
    304304    }
    305305
     
    310310    Prio prio() const {
    311311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    312       return data[boxes[0].first].prio;
     312      return _data[_boxes[0].first].prio;
    313313     }
    314314
     
    319319    void pop() {
    320320      moveDown();
    321       int index = boxes[0].first;
    322       _iim[data[index].item] = POST_HEAP;
     321      int index = _boxes[0].first;
     322      _iim[_data[index].item] = POST_HEAP;
    323323      remove(index);
    324       relocate_last(index);
     324      relocateLast(index);
    325325    }
    326326
     
    335335      _iim[i] = POST_HEAP;
    336336      remove(index);
    337       relocate_last(index);
     337      relocateLast(index);
    338338   }
    339339
     
    345345    Prio operator[](const Item &i) const {
    346346      int idx = _iim[i];
    347       return data[idx].prio;
     347      return _data[idx].prio;
    348348    }
    349349
     
    363363        push(i, p);
    364364      }
    365       else if( p >= data[idx].prio ) {
    366         data[idx].prio = p;
    367         bubble_up(idx);
     365      else if( p >= _data[idx].prio ) {
     366        _data[idx].prio = p;
     367        bubbleUp(idx);
    368368      } else {
    369         data[idx].prio = p;
    370         bubble_down(idx);
     369        _data[idx].prio = p;
     370        bubbleDown(idx);
    371371      }
    372372    }
     
    381381    void decrease(const Item &i, const Prio &p) {
    382382      int idx = _iim[i];
    383       data[idx].prio = p;
    384       bubble_down(idx);
     383      _data[idx].prio = p;
     384      bubbleDown(idx);
    385385    }
    386386
     
    393393    void increase(const Item &i, const Prio &p) {
    394394      int idx = _iim[i];
    395       data[idx].prio = p;
    396       bubble_up(idx);
     395      _data[idx].prio = p;
     396      bubbleUp(idx);
    397397    }
    398398
Note: See TracChangeset for help on using the changeset viewer.