Unify member names in heaps (#299)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 08 Jul 2009 17:47:01 +0200
changeset 75828cfac049a6a
parent 757 f1fe0ddad6f7
child 759 6d5f547e5bfb
Unify member names in heaps (#299)

The following renamings are made.

Public members:
- UnderFlowPriorityError -> PriorityUnderflowError
("underflow" is only one word)

Private members:
- bubble_up() -> bubbleUp()
- bubble_down() -> bubbleDown()
- second_child() -> secondChild()
- makeroot() -> makeRoot()
- relocate_last() -> relocateLast()
- data -> _data
- boxes -> _boxes
lemon/bin_heap.h
lemon/bucket_heap.h
lemon/fib_heap.h
lemon/radix_heap.h
     1.1 --- a/lemon/bin_heap.h	Wed Jul 08 17:22:36 2009 +0200
     1.2 +++ b/lemon/bin_heap.h	Wed Jul 08 17:47:01 2009 +0200
     1.3 @@ -124,12 +124,12 @@
     1.4    private:
     1.5      static int parent(int i) { return (i-1)/2; }
     1.6  
     1.7 -    static int second_child(int i) { return 2*i+2; }
     1.8 +    static int secondChild(int i) { return 2*i+2; }
     1.9      bool less(const Pair &p1, const Pair &p2) const {
    1.10        return _comp(p1.second, p2.second);
    1.11      }
    1.12  
    1.13 -    int bubble_up(int hole, Pair p) {
    1.14 +    int bubbleUp(int hole, Pair p) {
    1.15        int par = parent(hole);
    1.16        while( hole>0 && less(p,_data[par]) ) {
    1.17          move(_data[par],hole);
    1.18 @@ -140,8 +140,8 @@
    1.19        return hole;
    1.20      }
    1.21  
    1.22 -    int bubble_down(int hole, Pair p, int length) {
    1.23 -      int child = second_child(hole);
    1.24 +    int bubbleDown(int hole, Pair p, int length) {
    1.25 +      int child = secondChild(hole);
    1.26        while(child < length) {
    1.27          if( less(_data[child-1], _data[child]) ) {
    1.28            --child;
    1.29 @@ -150,7 +150,7 @@
    1.30            goto ok;
    1.31          move(_data[child], hole);
    1.32          hole = child;
    1.33 -        child = second_child(hole);
    1.34 +        child = secondChild(hole);
    1.35        }
    1.36        child--;
    1.37        if( child<length && less(_data[child], p) ) {
    1.38 @@ -178,7 +178,7 @@
    1.39      void push(const Pair &p) {
    1.40        int n = _data.size();
    1.41        _data.resize(n+1);
    1.42 -      bubble_up(n, p);
    1.43 +      bubbleUp(n, p);
    1.44      }
    1.45  
    1.46      /// \brief Insert an item into the heap with the given priority.
    1.47 @@ -214,7 +214,7 @@
    1.48        int n = _data.size()-1;
    1.49        _iim.set(_data[0].first, POST_HEAP);
    1.50        if (n > 0) {
    1.51 -        bubble_down(0, _data[n], n);
    1.52 +        bubbleDown(0, _data[n], n);
    1.53        }
    1.54        _data.pop_back();
    1.55      }
    1.56 @@ -230,8 +230,8 @@
    1.57        int n = _data.size()-1;
    1.58        _iim.set(_data[h].first, POST_HEAP);
    1.59        if( h < n ) {
    1.60 -        if ( bubble_up(h, _data[n]) == h) {
    1.61 -          bubble_down(h, _data[n], n);
    1.62 +        if ( bubbleUp(h, _data[n]) == h) {
    1.63 +          bubbleDown(h, _data[n], n);
    1.64          }
    1.65        }
    1.66        _data.pop_back();
    1.67 @@ -261,10 +261,10 @@
    1.68          push(i,p);
    1.69        }
    1.70        else if( _comp(p, _data[idx].second) ) {
    1.71 -        bubble_up(idx, Pair(i,p));
    1.72 +        bubbleUp(idx, Pair(i,p));
    1.73        }
    1.74        else {
    1.75 -        bubble_down(idx, Pair(i,p), _data.size());
    1.76 +        bubbleDown(idx, Pair(i,p), _data.size());
    1.77        }
    1.78      }
    1.79  
    1.80 @@ -276,7 +276,7 @@
    1.81      /// \pre \e i must be stored in the heap with priority at least \e p.
    1.82      void decrease(const Item &i, const Prio &p) {
    1.83        int idx = _iim[i];
    1.84 -      bubble_up(idx, Pair(i,p));
    1.85 +      bubbleUp(idx, Pair(i,p));
    1.86      }
    1.87  
    1.88      /// \brief Increase the priority of an item to the given value.
    1.89 @@ -287,7 +287,7 @@
    1.90      /// \pre \e i must be stored in the heap with priority at most \e p.
    1.91      void increase(const Item &i, const Prio &p) {
    1.92        int idx = _iim[i];
    1.93 -      bubble_down(idx, Pair(i,p), _data.size());
    1.94 +      bubbleDown(idx, Pair(i,p), _data.size());
    1.95      }
    1.96  
    1.97      /// \brief Return the state of an item.
     2.1 --- a/lemon/bucket_heap.h	Wed Jul 08 17:22:36 2009 +0200
     2.2 +++ b/lemon/bucket_heap.h	Wed Jul 08 17:47:01 2009 +0200
     2.3 @@ -142,7 +142,7 @@
     2.4  
     2.5    private:
     2.6  
     2.7 -    void relocate_last(int idx) {
     2.8 +    void relocateLast(int idx) {
     2.9        if (idx + 1 < int(_data.size())) {
    2.10          _data[idx] = _data.back();
    2.11          if (_data[idx].prev != -1) {
    2.12 @@ -243,7 +243,7 @@
    2.13        int idx = _first[_minimum];
    2.14        _iim[_data[idx].item] = -2;
    2.15        unlace(idx);
    2.16 -      relocate_last(idx);
    2.17 +      relocateLast(idx);
    2.18      }
    2.19  
    2.20      /// \brief Remove the given item from the heap.
    2.21 @@ -256,7 +256,7 @@
    2.22        int idx = _iim[i];
    2.23        _iim[_data[idx].item] = -2;
    2.24        unlace(idx);
    2.25 -      relocate_last(idx);
    2.26 +      relocateLast(idx);
    2.27      }
    2.28  
    2.29      /// \brief The priority of the given item.
     3.1 --- a/lemon/fib_heap.h	Wed Jul 08 17:22:36 2009 +0200
     3.2 +++ b/lemon/fib_heap.h	Wed Jul 08 17:47:01 2009 +0200
     3.3 @@ -188,7 +188,7 @@
     3.4        if ( _data[_minimum].left_neighbor==_minimum ) {
     3.5          _data[_minimum].in=false;
     3.6          if ( _data[_minimum].degree!=0 ) {
     3.7 -          makeroot(_data[_minimum].child);
     3.8 +          makeRoot(_data[_minimum].child);
     3.9            _minimum=_data[_minimum].child;
    3.10            balance();
    3.11          }
    3.12 @@ -201,7 +201,7 @@
    3.13            int child=_data[_minimum].child;
    3.14            int last_child=_data[child].left_neighbor;
    3.15  
    3.16 -          makeroot(child);
    3.17 +          makeRoot(child);
    3.18  
    3.19            _data[left].right_neighbor=child;
    3.20            _data[child].left_neighbor=left;
    3.21 @@ -372,7 +372,7 @@
    3.22        } while ( s != m );
    3.23      }
    3.24  
    3.25 -    void makeroot(int c) {
    3.26 +    void makeRoot(int c) {
    3.27        int s=c;
    3.28        do {
    3.29          _data[s].parent=-1;
     4.1 --- a/lemon/radix_heap.h	Wed Jul 08 17:22:36 2009 +0200
     4.2 +++ b/lemon/radix_heap.h	Wed Jul 08 17:47:01 2009 +0200
     4.3 @@ -58,10 +58,10 @@
     4.4      /// This exception is thrown when an item is inserted into a
     4.5      /// RadixHeap with a priority smaller than the last erased one.
     4.6      /// \see RadixHeap
     4.7 -    class UnderFlowPriorityError : public Exception {
     4.8 +    class PriorityUnderflowError : public Exception {
     4.9      public:
    4.10        virtual const char* what() const throw() {
    4.11 -        return "lemon::RadixHeap::UnderFlowPriorityError";
    4.12 +        return "lemon::RadixHeap::PriorityUnderflowError";
    4.13        }
    4.14      };
    4.15  
    4.16 @@ -94,8 +94,8 @@
    4.17        RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
    4.18      };
    4.19  
    4.20 -    std::vector<RadixItem> data;
    4.21 -    std::vector<RadixBox> boxes;
    4.22 +    std::vector<RadixItem> _data;
    4.23 +    std::vector<RadixBox> _boxes;
    4.24  
    4.25      ItemIntMap &_iim;
    4.26  
    4.27 @@ -112,9 +112,9 @@
    4.28      RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
    4.29        : _iim(map)
    4.30      {
    4.31 -      boxes.push_back(RadixBox(minimum, 1));
    4.32 -      boxes.push_back(RadixBox(minimum + 1, 1));
    4.33 -      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
    4.34 +      _boxes.push_back(RadixBox(minimum, 1));
    4.35 +      _boxes.push_back(RadixBox(minimum + 1, 1));
    4.36 +      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
    4.37          extend();
    4.38        }
    4.39      }
    4.40 @@ -122,12 +122,12 @@
    4.41      /// \brief The number of items stored in the heap.
    4.42      ///
    4.43      /// This function returns the number of items stored in the heap.
    4.44 -    int size() const { return data.size(); }
    4.45 +    int size() const { return _data.size(); }
    4.46  
    4.47      /// \brief Check if the heap is empty.
    4.48      ///
    4.49      /// This function returns \c true if the heap is empty.
    4.50 -    bool empty() const { return data.empty(); }
    4.51 +    bool empty() const { return _data.empty(); }
    4.52  
    4.53      /// \brief Make the heap empty.
    4.54      ///
    4.55 @@ -139,10 +139,10 @@
    4.56      /// \param minimum The minimum value of the heap.
    4.57      /// \param capacity The capacity of the heap.
    4.58      void clear(int minimum = 0, int capacity = 0) {
    4.59 -      data.clear(); boxes.clear();
    4.60 -      boxes.push_back(RadixBox(minimum, 1));
    4.61 -      boxes.push_back(RadixBox(minimum + 1, 1));
    4.62 -      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
    4.63 +      _data.clear(); _boxes.clear();
    4.64 +      _boxes.push_back(RadixBox(minimum, 1));
    4.65 +      _boxes.push_back(RadixBox(minimum + 1, 1));
    4.66 +      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
    4.67          extend();
    4.68        }
    4.69      }
    4.70 @@ -150,58 +150,58 @@
    4.71    private:
    4.72  
    4.73      bool upper(int box, Prio pr) {
    4.74 -      return pr < boxes[box].min;
    4.75 +      return pr < _boxes[box].min;
    4.76      }
    4.77  
    4.78      bool lower(int box, Prio pr) {
    4.79 -      return pr >= boxes[box].min + boxes[box].size;
    4.80 +      return pr >= _boxes[box].min + _boxes[box].size;
    4.81      }
    4.82  
    4.83      // Remove item from the box list
    4.84      void remove(int index) {
    4.85 -      if (data[index].prev >= 0) {
    4.86 -        data[data[index].prev].next = data[index].next;
    4.87 +      if (_data[index].prev >= 0) {
    4.88 +        _data[_data[index].prev].next = _data[index].next;
    4.89        } else {
    4.90 -        boxes[data[index].box].first = data[index].next;
    4.91 +        _boxes[_data[index].box].first = _data[index].next;
    4.92        }
    4.93 -      if (data[index].next >= 0) {
    4.94 -        data[data[index].next].prev = data[index].prev;
    4.95 +      if (_data[index].next >= 0) {
    4.96 +        _data[_data[index].next].prev = _data[index].prev;
    4.97        }
    4.98      }
    4.99  
   4.100      // Insert item into the box list
   4.101      void insert(int box, int index) {
   4.102 -      if (boxes[box].first == -1) {
   4.103 -        boxes[box].first = index;
   4.104 -        data[index].next = data[index].prev = -1;
   4.105 +      if (_boxes[box].first == -1) {
   4.106 +        _boxes[box].first = index;
   4.107 +        _data[index].next = _data[index].prev = -1;
   4.108        } else {
   4.109 -        data[index].next = boxes[box].first;
   4.110 -        data[boxes[box].first].prev = index;
   4.111 -        data[index].prev = -1;
   4.112 -        boxes[box].first = index;
   4.113 +        _data[index].next = _boxes[box].first;
   4.114 +        _data[_boxes[box].first].prev = index;
   4.115 +        _data[index].prev = -1;
   4.116 +        _boxes[box].first = index;
   4.117        }
   4.118 -      data[index].box = box;
   4.119 +      _data[index].box = box;
   4.120      }
   4.121  
   4.122      // Add a new box to the box list
   4.123      void extend() {
   4.124 -      int min = boxes.back().min + boxes.back().size;
   4.125 -      int bs = 2 * boxes.back().size;
   4.126 -      boxes.push_back(RadixBox(min, bs));
   4.127 +      int min = _boxes.back().min + _boxes.back().size;
   4.128 +      int bs = 2 * _boxes.back().size;
   4.129 +      _boxes.push_back(RadixBox(min, bs));
   4.130      }
   4.131  
   4.132      // Move an item up into the proper box.
   4.133 -    void bubble_up(int index) {
   4.134 -      if (!lower(data[index].box, data[index].prio)) return;
   4.135 +    void bubbleUp(int index) {
   4.136 +      if (!lower(_data[index].box, _data[index].prio)) return;
   4.137        remove(index);
   4.138 -      int box = findUp(data[index].box, data[index].prio);
   4.139 +      int box = findUp(_data[index].box, _data[index].prio);
   4.140        insert(box, index);
   4.141      }
   4.142  
   4.143      // Find up the proper box for the item with the given priority
   4.144      int findUp(int start, int pr) {
   4.145        while (lower(start, pr)) {
   4.146 -        if (++start == int(boxes.size())) {
   4.147 +        if (++start == int(_boxes.size())) {
   4.148            extend();
   4.149          }
   4.150        }
   4.151 @@ -209,17 +209,17 @@
   4.152      }
   4.153  
   4.154      // Move an item down into the proper box
   4.155 -    void bubble_down(int index) {
   4.156 -      if (!upper(data[index].box, data[index].prio)) return;
   4.157 +    void bubbleDown(int index) {
   4.158 +      if (!upper(_data[index].box, _data[index].prio)) return;
   4.159        remove(index);
   4.160 -      int box = findDown(data[index].box, data[index].prio);
   4.161 +      int box = findDown(_data[index].box, _data[index].prio);
   4.162        insert(box, index);
   4.163      }
   4.164  
   4.165      // Find down the proper box for the item with the given priority
   4.166      int findDown(int start, int pr) {
   4.167        while (upper(start, pr)) {
   4.168 -        if (--start < 0) throw UnderFlowPriorityError();
   4.169 +        if (--start < 0) throw PriorityUnderflowError();
   4.170        }
   4.171        return start;
   4.172      }
   4.173 @@ -227,15 +227,15 @@
   4.174      // Find the first non-empty box
   4.175      int findFirst() {
   4.176        int first = 0;
   4.177 -      while (boxes[first].first == -1) ++first;
   4.178 +      while (_boxes[first].first == -1) ++first;
   4.179        return first;
   4.180      }
   4.181  
   4.182      // Gives back the minimum priority of the given box
   4.183      int minValue(int box) {
   4.184 -      int min = data[boxes[box].first].prio;
   4.185 -      for (int k = boxes[box].first; k != -1; k = data[k].next) {
   4.186 -        if (data[k].prio < min) min = data[k].prio;
   4.187 +      int min = _data[_boxes[box].first].prio;
   4.188 +      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
   4.189 +        if (_data[k].prio < min) min = _data[k].prio;
   4.190        }
   4.191        return min;
   4.192      }
   4.193 @@ -246,31 +246,31 @@
   4.194        if (box == 0) return;
   4.195        int min = minValue(box);
   4.196        for (int i = 0; i <= box; ++i) {
   4.197 -        boxes[i].min = min;
   4.198 -        min += boxes[i].size;
   4.199 +        _boxes[i].min = min;
   4.200 +        min += _boxes[i].size;
   4.201        }
   4.202 -      int curr = boxes[box].first, next;
   4.203 +      int curr = _boxes[box].first, next;
   4.204        while (curr != -1) {
   4.205 -        next = data[curr].next;
   4.206 -        bubble_down(curr);
   4.207 +        next = _data[curr].next;
   4.208 +        bubbleDown(curr);
   4.209          curr = next;
   4.210        }
   4.211      }
   4.212  
   4.213 -    void relocate_last(int index) {
   4.214 -      if (index != int(data.size()) - 1) {
   4.215 -        data[index] = data.back();
   4.216 -        if (data[index].prev != -1) {
   4.217 -          data[data[index].prev].next = index;
   4.218 +    void relocateLast(int index) {
   4.219 +      if (index != int(_data.size()) - 1) {
   4.220 +        _data[index] = _data.back();
   4.221 +        if (_data[index].prev != -1) {
   4.222 +          _data[_data[index].prev].next = index;
   4.223          } else {
   4.224 -          boxes[data[index].box].first = index;
   4.225 +          _boxes[_data[index].box].first = index;
   4.226          }
   4.227 -        if (data[index].next != -1) {
   4.228 -          data[data[index].next].prev = index;
   4.229 +        if (_data[index].next != -1) {
   4.230 +          _data[_data[index].next].prev = index;
   4.231          }
   4.232 -        _iim[data[index].item] = index;
   4.233 +        _iim[_data[index].item] = index;
   4.234        }
   4.235 -      data.pop_back();
   4.236 +      _data.pop_back();
   4.237      }
   4.238  
   4.239    public:
   4.240 @@ -284,13 +284,13 @@
   4.241      /// \pre \e i must not be stored in the heap.
   4.242      /// \warning This method may throw an \c UnderFlowPriorityException.
   4.243      void push(const Item &i, const Prio &p) {
   4.244 -      int n = data.size();
   4.245 +      int n = _data.size();
   4.246        _iim.set(i, n);
   4.247 -      data.push_back(RadixItem(i, p));
   4.248 -      while (lower(boxes.size() - 1, p)) {
   4.249 +      _data.push_back(RadixItem(i, p));
   4.250 +      while (lower(_boxes.size() - 1, p)) {
   4.251          extend();
   4.252        }
   4.253 -      int box = findDown(boxes.size() - 1, p);
   4.254 +      int box = findDown(_boxes.size() - 1, p);
   4.255        insert(box, n);
   4.256      }
   4.257  
   4.258 @@ -300,7 +300,7 @@
   4.259      /// \pre The heap must be non-empty.
   4.260      Item top() const {
   4.261        const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   4.262 -      return data[boxes[0].first].item;
   4.263 +      return _data[_boxes[0].first].item;
   4.264      }
   4.265  
   4.266      /// \brief The minimum priority.
   4.267 @@ -309,7 +309,7 @@
   4.268      /// \pre The heap must be non-empty.
   4.269      Prio prio() const {
   4.270        const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
   4.271 -      return data[boxes[0].first].prio;
   4.272 +      return _data[_boxes[0].first].prio;
   4.273       }
   4.274  
   4.275      /// \brief Remove the item having minimum priority.
   4.276 @@ -318,10 +318,10 @@
   4.277      /// \pre The heap must be non-empty.
   4.278      void pop() {
   4.279        moveDown();
   4.280 -      int index = boxes[0].first;
   4.281 -      _iim[data[index].item] = POST_HEAP;
   4.282 +      int index = _boxes[0].first;
   4.283 +      _iim[_data[index].item] = POST_HEAP;
   4.284        remove(index);
   4.285 -      relocate_last(index);
   4.286 +      relocateLast(index);
   4.287      }
   4.288  
   4.289      /// \brief Remove the given item from the heap.
   4.290 @@ -334,7 +334,7 @@
   4.291        int index = _iim[i];
   4.292        _iim[i] = POST_HEAP;
   4.293        remove(index);
   4.294 -      relocate_last(index);
   4.295 +      relocateLast(index);
   4.296     }
   4.297  
   4.298      /// \brief The priority of the given item.
   4.299 @@ -344,7 +344,7 @@
   4.300      /// \pre \e i must be in the heap.
   4.301      Prio operator[](const Item &i) const {
   4.302        int idx = _iim[i];
   4.303 -      return data[idx].prio;
   4.304 +      return _data[idx].prio;
   4.305      }
   4.306  
   4.307      /// \brief Set the priority of an item or insert it, if it is
   4.308 @@ -362,12 +362,12 @@
   4.309        if( idx < 0 ) {
   4.310          push(i, p);
   4.311        }
   4.312 -      else if( p >= data[idx].prio ) {
   4.313 -        data[idx].prio = p;
   4.314 -        bubble_up(idx);
   4.315 +      else if( p >= _data[idx].prio ) {
   4.316 +        _data[idx].prio = p;
   4.317 +        bubbleUp(idx);
   4.318        } else {
   4.319 -        data[idx].prio = p;
   4.320 -        bubble_down(idx);
   4.321 +        _data[idx].prio = p;
   4.322 +        bubbleDown(idx);
   4.323        }
   4.324      }
   4.325  
   4.326 @@ -380,8 +380,8 @@
   4.327      /// \warning This method may throw an \c UnderFlowPriorityException.
   4.328      void decrease(const Item &i, const Prio &p) {
   4.329        int idx = _iim[i];
   4.330 -      data[idx].prio = p;
   4.331 -      bubble_down(idx);
   4.332 +      _data[idx].prio = p;
   4.333 +      bubbleDown(idx);
   4.334      }
   4.335  
   4.336      /// \brief Increase the priority of an item to the given value.
   4.337 @@ -392,8 +392,8 @@
   4.338      /// \pre \e i must be stored in the heap with priority at most \e p.
   4.339      void increase(const Item &i, const Prio &p) {
   4.340        int idx = _iim[i];
   4.341 -      data[idx].prio = p;
   4.342 -      bubble_up(idx);
   4.343 +      _data[idx].prio = p;
   4.344 +      bubbleUp(idx);
   4.345      }
   4.346  
   4.347      /// \brief Return the state of an item.