COIN-OR::LEMON - Graph Library

Changeset 758:28cfac049a6a in lemon


Ignore:
Timestamp:
07/08/09 17:47:01 (9 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
Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r757 r758  
    125125    static int parent(int i) { return (i-1)/2; }
    126126
    127     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    128128    bool less(const Pair &p1, const Pair &p2) const {
    129129      return _comp(p1.second, p2.second);
    130130    }
    131131
    132     int bubble_up(int hole, Pair p) {
     132    int bubbleUp(int hole, Pair p) {
    133133      int par = parent(hole);
    134134      while( hole>0 && less(p,_data[par]) ) {
     
    141141    }
    142142
    143     int bubble_down(int hole, Pair p, int length) {
    144       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    145145      while(child < length) {
    146146        if( less(_data[child-1], _data[child]) ) {
     
    151151        move(_data[child], hole);
    152152        hole = child;
    153         child = second_child(hole);
     153        child = secondChild(hole);
    154154      }
    155155      child--;
     
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubble_up(n, p);
     181      bubbleUp(n, p);
    182182    }
    183183
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubble_down(0, _data[n], n);
     217        bubbleDown(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
     
    231231      _iim.set(_data[h].first, POST_HEAP);
    232232      if( h < n ) {
    233         if ( bubble_up(h, _data[n]) == h) {
    234           bubble_down(h, _data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    235235        }
    236236      }
     
    262262      }
    263263      else if( _comp(p, _data[idx].second) ) {
    264         bubble_up(idx, Pair(i,p));
     264        bubbleUp(idx, Pair(i,p));
    265265      }
    266266      else {
    267         bubble_down(idx, Pair(i,p), _data.size());
     267        bubbleDown(idx, Pair(i,p), _data.size());
    268268      }
    269269    }
     
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubble_up(idx, Pair(i,p));
     279      bubbleUp(idx, Pair(i,p));
    280280    }
    281281
     
    288288    void increase(const Item &i, const Prio &p) {
    289289      int idx = _iim[i];
    290       bubble_down(idx, Pair(i,p), _data.size());
     290      bubbleDown(idx, Pair(i,p), _data.size());
    291291    }
    292292
  • lemon/bucket_heap.h

    r757 r758  
    143143  private:
    144144
    145     void relocate_last(int idx) {
     145    void relocateLast(int idx) {
    146146      if (idx + 1 < int(_data.size())) {
    147147        _data[idx] = _data.back();
     
    244244      _iim[_data[idx].item] = -2;
    245245      unlace(idx);
    246       relocate_last(idx);
     246      relocateLast(idx);
    247247    }
    248248
     
    257257      _iim[_data[idx].item] = -2;
    258258      unlace(idx);
    259       relocate_last(idx);
     259      relocateLast(idx);
    260260    }
    261261
  • lemon/fib_heap.h

    r757 r758  
    189189        _data[_minimum].in=false;
    190190        if ( _data[_minimum].degree!=0 ) {
    191           makeroot(_data[_minimum].child);
     191          makeRoot(_data[_minimum].child);
    192192          _minimum=_data[_minimum].child;
    193193          balance();
     
    202202          int last_child=_data[child].left_neighbor;
    203203
    204           makeroot(child);
     204          makeRoot(child);
    205205
    206206          _data[left].right_neighbor=child;
     
    373373    }
    374374
    375     void makeroot(int c) {
     375    void makeRoot(int c) {
    376376      int s=c;
    377377      do {
  • lemon/radix_heap.h

    r757 r758  
    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.