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

@@ -126,3 +126,3 @@
-		    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 {
@@ -131,3 +131,3 @@
-		    int bubble_up(int hole, Pair p) {
+		    int bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
@@ -142,4 +142,4 @@
 		    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) {
@@ -152,3 +152,3 @@
 		        hole = child;
-		        child = second_child(hole);
+		        child = secondChild(hole);
+		      }
@@ -180,3 +180,3 @@
 		      _data.resize(n+1);
-		      bubble_up(n, p);
+		      bubbleUp(n, p);
+		    }
@@ -216,3 +216,3 @@
 		      if (n > 0) {
-		        bubble_down(0, _data[n], n);
+		        bubbleDown(0, _data[n], n);
+		      }
@@ -232,4 +232,4 @@
 		      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);
+		        }
@@ -263,6 +263,6 @@
 		      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());
+		      }
@@ -278,3 +278,3 @@
 		      int idx = _iim[i];
-		      bubble_up(idx, Pair(i,p));
+		      bubbleUp(idx, Pair(i,p));
+		    }
@@ -289,3 +289,3 @@
 		      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

@@ -144,3 +144,3 @@
-		    void relocate_last(int idx) {
+		    void relocateLast(int idx) {
 		      if (idx + 1 < int(_data.size())) {
@@ -245,3 +245,3 @@
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
@@ -258,3 +258,3 @@
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }

lemon/fib_heap.h

Show inline comments

@@ -190,3 +190,3 @@
 		        if ( _data[_minimum].degree!=0 ) {
-		          makeroot(_data[_minimum].child);
+		          makeRoot(_data[_minimum].child);
 		          _minimum=_data[_minimum].child;
@@ -203,3 +203,3 @@
-		          makeroot(child);
+		          makeRoot(child);
@@ -374,3 +374,3 @@
-		    void makeroot(int c) {
+		    void makeRoot(int c) {
 		      int s=c;

lemon/radix_heap.h

Show inline comments

@@ -60,6 +60,6 @@
 		    /// \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";
+		      }
@@ -96,4 +96,4 @@
 		    std::vector<RadixItem> data;
 		    std::vector<RadixBox> boxes;
 		    std::vector<RadixItem> _data;
 		    std::vector<RadixBox> _boxes;
@@ -114,5 +114,5 @@
+		    {
 		      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();
@@ -124,3 +124,3 @@
 		    /// This function returns the number of items stored in the heap.
-		    int size() const { return data.size(); }
+		    int size() const { return _data.size(); }
@@ -129,3 +129,3 @@
 		    /// This function returns \c true if the heap is empty.
-		    bool empty() const { return data.empty(); }
+		    bool empty() const { return _data.empty(); }
@@ -141,6 +141,6 @@
 		    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();
@@ -152,3 +152,3 @@
 		    bool upper(int box, Prio pr) {
-		      return pr < boxes[box].min;
+		      return pr < _boxes[box].min;
+		    }
@@ -156,3 +156,3 @@
 		    bool lower(int box, Prio pr) {
-		      return pr >= boxes[box].min + boxes[box].size;
+		      return pr >= _boxes[box].min + _boxes[box].size;
+		    }
@@ -161,9 +161,9 @@
 		    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;
+		      }
@@ -173,12 +173,12 @@
 		    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;
+		    }
@@ -187,5 +187,5 @@
 		    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));
+		    }
@@ -193,6 +193,6 @@
 		    // 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);
@@ -203,3 +203,3 @@
 		      while (lower(start, pr)) {
-		        if (++start == int(boxes.size())) {
+		        if (++start == int(_boxes.size())) {
 		          extend();
@@ -211,6 +211,6 @@
 		    // 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);
@@ -221,3 +221,3 @@
 		      while (upper(start, pr)) {
-		        if (--start < 0) throw UnderFlowPriorityError();
+		        if (--start < 0) throw PriorityUnderflowError();
+		      }
@@ -229,3 +229,3 @@
 		      int first = 0;
-		      while (boxes[first].first == -1) ++first;
+		      while (_boxes[first].first == -1) ++first;
 		      return first;
@@ -235,5 +235,5 @@
 		    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;
+		      }
@@ -248,9 +248,9 @@
 		      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;
@@ -259,16 +259,16 @@
 		    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();
+		    }
@@ -286,9 +286,9 @@
 		    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);
@@ -302,3 +302,3 @@
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].item;
+		      return _data[_boxes[0].first].item;
+		    }
@@ -311,3 +311,3 @@
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-		      return data[boxes[0].first].prio;
+		      return _data[_boxes[0].first].prio;
+		     }
@@ -320,6 +320,6 @@
 		      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);
+		    }
@@ -336,3 +336,3 @@
 		      remove(index);
-		      relocate_last(index);
+		      relocateLast(index);
+		   }
@@ -346,3 +346,3 @@
 		      int idx = _iim[i];
-		      return data[idx].prio;
+		      return _data[idx].prio;
+		    }
@@ -364,8 +364,8 @@
+		      }
 		      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);
+		      }
@@ -382,4 +382,4 @@
 		      int idx = _iim[i];
 		      data[idx].prio = p;
 		      bubble_down(idx);
 		      _data[idx].prio = p;
 		      bubbleDown(idx);
+		    }
@@ -394,4 +394,4 @@
 		      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