LEMON/LEMON-main Changeset - r711:28cfac049a6a

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r711:28cfac049a6a

« 710:f1fe0d

712:6d5f54 »

r711:28cfac049a6a

Wed, 08 Jul 2009 17:47:01

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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

0 4 0

default

4 files changed with 97 insertions and 97 deletions:

lemon/bin_heap.h

lemon/bucket_heap.h

lemon/fib_heap.h

lemon/radix_heap.h

↑ Collapse diff ↑

lemon/bin_heap.h

Show inline comments

@@ -125,10 +125,10 @@
 		    static int parent(int i) { return (i-1)/2; }
-		    static int second_child(int i) { return 2*i+2; }
+		    static int secondChild(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
-		    int bubble_up(int hole, Pair p) {
+		    int bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
@@ -141,6 +141,6 @@
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		    int bubbleDown(int hole, Pair p, int length) {
 		      int child = secondChild(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
@@ -151,5 +151,5 @@
 		        move(_data[child], hole);
 		        hole = child;
-		        child = second_child(hole);
+		        child = secondChild(hole);
+		      }
 		      child--;
@@ -179,5 +179,5 @@
 		      int n = _data.size();
 		      _data.resize(n+1);
-		      bubble_up(n, p);
+		      bubbleUp(n, p);
+		    }
@@ -215,5 +215,5 @@
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
-		        bubble_down(0, _data[n], n);
+		        bubbleDown(0, _data[n], n);
+		      }
 		      _data.pop_back();
@@ -231,6 +231,6 @@
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
 		        if ( bubbleUp(h, _data[n]) == h) {
 		          bubbleDown(h, _data[n], n);
+		        }
+		      }
@@ -262,8 +262,8 @@
+		      }
 		      else if( _comp(p, _data[idx].second) ) {
-		        bubble_up(idx, Pair(i,p));
+		        bubbleUp(idx, Pair(i,p));
+		      }
 		      else {
-		        bubble_down(idx, Pair(i,p), _data.size());
+		        bubbleDown(idx, Pair(i,p), _data.size());
+		      }
+		    }
@@ -277,5 +277,5 @@
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
-		      bubble_up(idx, Pair(i,p));
+		      bubbleUp(idx, Pair(i,p));
+		    }
@@ -288,5 +288,5 @@
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
-		      bubble_down(idx, Pair(i,p), _data.size());
+		      bubbleDown(idx, Pair(i,p), _data.size());
+		    }

lemon/bucket_heap.h

Show inline comments

@@ -143,5 +143,5 @@
 		  private:
-		    void relocate_last(int idx) {
+		    void relocateLast(int idx) {
 		      if (idx + 1 < int(_data.size())) {
 		        _data[idx] = _data.back();
@@ -244,5 +244,5 @@
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
@@ -257,5 +257,5 @@
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }

lemon/fib_heap.h

Show inline comments

@@ -189,5 +189,5 @@
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree!=0 ) {
-		          makeroot(_data[_minimum].child);
+		          makeRoot(_data[_minimum].child);
 		          _minimum=_data[_minimum].child;
 		          balance();
@@ -202,5 +202,5 @@
 		          int last_child=_data[child].left_neighbor;
-		          makeroot(child);
+		          makeRoot(child);
 		          _data[left].right_neighbor=child;
@@ -373,5 +373,5 @@
+		    }
-		    void makeroot(int c) {
+		    void makeRoot(int c) {
 		      int s=c;
 		      do {

lemon/radix_heap.h

Show inline comments

@@ -59,8 +59,8 @@
 		    /// RadixHeap with a priority smaller than the last erased one.
 		    /// \see RadixHeap
-		    class UnderFlowPriorityError : public Exception {
+		    class PriorityUnderflowError : public Exception {
 		    public:
 		      virtual const char* what() const throw() {
-		        return "lemon::RadixHeap::UnderFlowPriorityError";
+		        return "lemon::RadixHeap::PriorityUnderflowError";
+		      }
 		    };
@@ -95,6 +95,6 @@
 		    };
 		    std::vector<RadixItem> data;
 		    std::vector<RadixBox> boxes;
 		    std::vector<RadixItem> _data;
 		    std::vector<RadixBox> _boxes;
 		    ItemIntMap &_iim;
@@ -113,7 +113,7 @@
 		      : _iim(map)
+		    {
 		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
-		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
+		      _boxes.push_back(RadixBox(minimum, 1));
 		      _boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
@@ -123,10 +123,10 @@
 		    ///
 		    /// This function returns the number of items stored in the heap.
-		    int size() const { return data.size(); }
+		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
-		    bool empty() const { return data.empty(); }
+		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
@@ -140,8 +140,8 @@
 		    /// \param capacity The capacity of the heap.
 		    void clear(int minimum = 0, int capacity = 0) {
 		      data.clear(); boxes.clear();
 		      boxes.push_back(RadixBox(minimum, 1));
 		      boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(boxes.size() - 1, capacity + minimum - 1)) {
 		      _data.clear(); _boxes.clear();
 		      _boxes.push_back(RadixBox(minimum, 1));
 		      _boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
@@ -151,20 +151,20 @@
 		    bool upper(int box, Prio pr) {
-		      return pr < boxes[box].min;
+		      return pr < _boxes[box].min;
+		    }
 		    bool lower(int box, Prio pr) {
-		      return pr >= boxes[box].min + boxes[box].size;
+		      return pr >= _boxes[box].min + _boxes[box].size;
+		    }
 		    // Remove item from the box list
 		    void remove(int index) {
 		      if (data[index].prev >= 0) {
 		        data[data[index].prev].next = data[index].next;
 		      if (_data[index].prev >= 0) {
 		        _data[_data[index].prev].next = _data[index].next;
 		      } else {
-		        boxes[data[index].box].first = data[index].next;
+		        _boxes[_data[index].box].first = _data[index].next;
+		      }
 		      if (data[index].next >= 0) {
 		        data[data[index].next].prev = data[index].prev;
 		      if (_data[index].next >= 0) {
 		        _data[_data[index].next].prev = _data[index].prev;
+		      }
+		    }
@@ -172,28 +172,28 @@
 		    // Insert item into the box list
 		    void insert(int box, int index) {
 		      if (boxes[box].first == -1) {
 		        boxes[box].first = index;
-		        data[index].next = data[index].prev = -1;
+		      if (_boxes[box].first == -1) {
 		        _boxes[box].first = index;
 		        _data[index].next = _data[index].prev = -1;
 		      } else {
 		        data[index].next = boxes[box].first;
 		        data[boxes[box].first].prev = index;
 		        data[index].prev = -1;
 		        boxes[box].first = index;
 		        _data[index].next = _boxes[box].first;
 		        _data[_boxes[box].first].prev = index;
 		        _data[index].prev = -1;
 		        _boxes[box].first = index;
+		      }
-		      data[index].box = box;
+		      _data[index].box = box;
+		    }
 		    // Add a new box to the box list
 		    void extend() {
 		      int min = boxes.back().min + boxes.back().size;
 		      int bs = 2 * boxes.back().size;
-		      boxes.push_back(RadixBox(min, bs));
+		      int min = _boxes.back().min + _boxes.back().size;
 		      int bs = 2 * _boxes.back().size;
 		      _boxes.push_back(RadixBox(min, bs));
+		    }
 		    // Move an item up into the proper box.
 		    void bubble_up(int index) {
 		      if (!lower(data[index].box, data[index].prio)) return;
 		    void bubbleUp(int index) {
 		      if (!lower(_data[index].box, _data[index].prio)) return;
 		      remove(index);
-		      int box = findUp(data[index].box, data[index].prio);
+		      int box = findUp(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
@@ -202,5 +202,5 @@
 		    int findUp(int start, int pr) {
 		      while (lower(start, pr)) {
-		        if (++start == int(boxes.size())) {
+		        if (++start == int(_boxes.size())) {
 		          extend();
+		        }
@@ -210,8 +210,8 @@
 		    // Move an item down into the proper box
 		    void bubble_down(int index) {
 		      if (!upper(data[index].box, data[index].prio)) return;
 		    void bubbleDown(int index) {
 		      if (!upper(_data[index].box, _data[index].prio)) return;
 		      remove(index);
-		      int box = findDown(data[index].box, data[index].prio);
+		      int box = findDown(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
@@ -220,5 +220,5 @@
 		    int findDown(int start, int pr) {
 		      while (upper(start, pr)) {
-		        if (--start < 0) throw UnderFlowPriorityError();
+		        if (--start < 0) throw PriorityUnderflowError();
+		      }
 		      return start;
@@ -228,5 +228,5 @@
 		    int findFirst() {
 		      int first = 0;
-		      while (boxes[first].first == -1) ++first;
+		      while (_boxes[first].first == -1) ++first;
 		      return first;
+		    }
@@ -234,7 +234,7 @@
 		    // Gives back the minimum priority of the given box
 		    int minValue(int box) {
 		      int min = data[boxes[box].first].prio;
 		      for (int k = boxes[box].first; k != -1; k = data[k].next) {
-		        if (data[k].prio < min) min = data[k].prio;
+		      int min = _data[_boxes[box].first].prio;
 		      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
 		        if (_data[k].prio < min) min = _data[k].prio;
+		      }
 		      return min;
@@ -247,29 +247,29 @@
 		      int min = minValue(box);
 		      for (int i = 0; i <= box; ++i) {
 		        boxes[i].min = min;
 		        min += boxes[i].size;
 		        _boxes[i].min = min;
 		        min += _boxes[i].size;
+		      }
-		      int curr = boxes[box].first, next;
+		      int curr = _boxes[box].first, next;
 		      while (curr != -1) {
 		        next = data[curr].next;
 		        bubble_down(curr);
 		        next = _data[curr].next;
 		        bubbleDown(curr);
 		        curr = next;
+		      }
+		    }
 		    void relocate_last(int index) {
 		      if (index != int(data.size()) - 1) {
 		        data[index] = data.back();
 		        if (data[index].prev != -1) {
-		          data[data[index].prev].next = index;
+		    void relocateLast(int index) {
 		      if (index != int(_data.size()) - 1) {
 		        _data[index] = _data.back();
 		        if (_data[index].prev != -1) {
 		          _data[_data[index].prev].next = index;
 		        } else {
-		          boxes[data[index].box].first = index;
+		          _boxes[_data[index].box].first = index;
+		        }
 		        if (data[index].next != -1) {
 		          data[data[index].next].prev = index;
 		        if (_data[index].next != -1) {
 		          _data[_data[index].next].prev = index;
+		        }
-		        _iim[data[index].item] = index;
+		        _iim[_data[index].item] = index;
+		      }
-		      data.pop_back();
+		      _data.pop_back();
+		    }
@@ -285,11 +285,11 @@
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void push(const Item &i, const Prio &p) {
-		      int n = data.size();
+		      int n = _data.size();
 		      _iim.set(i, n);
 		      data.push_back(RadixItem(i, p));
 		      while (lower(boxes.size() - 1, p)) {
 		      _data.push_back(RadixItem(i, p));
 		      while (lower(_boxes.size() - 1, p)) {
 		        extend();
+		      }
-		      int box = findDown(boxes.size() - 1, p);
+		      int box = findDown(_boxes.size() - 1, p);
 		      insert(box, n);
+		    }
@@ -301,5 +301,5 @@
 		    Item top() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].item;
+		      return _data[_boxes[0].first].item;
+		    }
@@ -310,5 +310,5 @@
 		    Prio prio() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].prio;
+		      return _data[_boxes[0].first].prio;
+		     }
@@ -319,8 +319,8 @@
 		    void pop() {
 		      moveDown();
 		      int index = boxes[0].first;
 		      _iim[data[index].item] = POST_HEAP;
 		      int index = _boxes[0].first;
 		      _iim[_data[index].item] = POST_HEAP;
 		      remove(index);
-		      relocate_last(index);
+		      relocateLast(index);
+		    }
@@ -335,5 +335,5 @@
 		      _iim[i] = POST_HEAP;
 		      remove(index);
-		      relocate_last(index);
+		      relocateLast(index);
+		   }
@@ -345,5 +345,5 @@
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
-		      return data[idx].prio;
+		      return _data[idx].prio;
+		    }
@@ -363,10 +363,10 @@
 		        push(i, p);
+		      }
 		      else if( p >= data[idx].prio ) {
 		        data[idx].prio = p;
-		        bubble_up(idx);
+		      else if( p >= _data[idx].prio ) {
 		        _data[idx].prio = p;
 		        bubbleUp(idx);
 		      } else {
 		        data[idx].prio = p;
 		        bubble_down(idx);
 		        _data[idx].prio = p;
 		        bubbleDown(idx);
+		      }
+		    }
@@ -381,6 +381,6 @@
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_down(idx);
 		      _data[idx].prio = p;
 		      bubbleDown(idx);
+		    }
@@ -393,6 +393,6 @@
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_up(idx);
 		      _data[idx].prio = p;
 		      bubbleUp(idx);
+		    }

0 comments (0 inline)

RhodeCode

Login to your account