Changeset 730:9f529abcaebf in lemon for lemon/radix_heap.h

Timestamp:

06/11/09 23:13:24 (15 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Children:

733:7439dc5fe1b9, 738:9e54e3b27db0, 740:7bda7860e0a8, 743:c9b9da1a90a0, 748:d1a9224f1e30, 756:0747f332c478, 760:4ac30454f1c1, 765:703ebf476a1d, 805:b31e130db13d

Phase:

public

Message:

Unification of names in heaps (#50)

File:

• lemon/radix_heap.h (modified) (14 diffs)

lemon/radix_heap.h

@@ -42 +42 @@
   /// item's priority.
   ///
-  /// \param _ItemIntMap A read and writable Item int map, used internally
+  /// \param IM A read and writable Item int map, used internally
   /// to handle the cross references.
   ///
   /// \see BinHeap
   /// \see Dijkstra
-  template <typename _ItemIntMap>
+  template <typename IM>
   class RadixHeap {
 
   public:
-    typedef typename _ItemIntMap::Key Item;
+    typedef typename IM::Key Item;
     typedef int Prio;
-    typedef _ItemIntMap ItemIntMap;
+    typedef IM ItemIntMap;
 
     /// \brief Exception thrown by RadixHeap.
@@ -100 +100 @@
     std::vector<RadixBox> boxes;
 
-    ItemIntMap &iim;
+    ItemIntMap &_iim;
 
 
@@ -108 +108 @@
     /// The constructor.
     ///
-    /// \param _iim It should be given to the constructor, since it is used
+    /// \param map It should be given to the constructor, since it is used
     /// internally to handle the cross references. The value of the map
     /// should be PRE_HEAP (-1) for each element.
@@ -114 +114 @@
     /// \param minimal The initial minimal value of the heap.
     /// \param capacity It determines the initial capacity of the heap.
-    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
-      : iim(_iim) {
+    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
+      : _iim(map) {
       boxes.push_back(RadixBox(minimal, 1));
       boxes.push_back(RadixBox(minimal + 1, 1));
@@ -269 +269 @@
           data[data[index].next].prev = index;
         }
-        iim[data[index].item] = index;
+        _iim[data[index].item] = index;
       }
       data.pop_back();
@@ -283 +283 @@
     void push(const Item &i, const Prio &p) {
       int n = data.size();
-      iim.set(i, n);
+      _iim.set(i, n);
       data.push_back(RadixItem(i, p));
       while (lower(boxes.size() - 1, p)) {
@@ -317 +317 @@
       moveDown();
       int index = boxes[0].first;
-      iim[data[index].item] = POST_HEAP;
+      _iim[data[index].item] = POST_HEAP;
       remove(index);
       relocate_last(index);
@@ -328 +328 @@
     /// \param i The item to erase.
     void erase(const Item &i) {
-      int index = iim[i];
-      iim[i] = POST_HEAP;
+      int index = _iim[i];
+      _iim[i] = POST_HEAP;
       remove(index);
       relocate_last(index);
@@ -340 +340 @@
     /// \param i The item.
     Prio operator[](const Item &i) const {
-      int idx = iim[i];
+      int idx = _iim[i];
       return data[idx].prio;
     }
@@ -353 +353 @@
     /// \param p The priority.
     void set(const Item &i, const Prio &p) {
-      int idx = iim[i];
+      int idx = _iim[i];
       if( idx < 0 ) {
         push(i, p);
@@ -375 +375 @@
     /// \param p The priority.
     void decrease(const Item &i, const Prio &p) {
-      int idx = iim[i];
+      int idx = _iim[i];
       data[idx].prio = p;
       bubble_down(idx);
@@ -387 +387 @@
     /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
-      int idx = iim[i];
+      int idx = _iim[i];
       data[idx].prio = p;
       bubble_up(idx);
@@ -401 +401 @@
     /// \param i The item.
     State state(const Item &i) const {
-      int s = iim[i];
+      int s = _iim[i];
       if( s >= 0 ) s = 0;
       return State(s);
@@ -420 +420 @@
           erase(i);
         }
-        iim[i] = st;
+        _iim[i] = st;
         break;
       case IN_HEAP: