Changes in lemon/bin_heap.h [631:33c6b6e755cd:209:765619b7cbb2] in lemon

File:

• lemon/bin_heap.h (modified) (22 diffs)

lemon/bin_heap.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -34 +34 @@
   ///\brief A Binary Heap implementation.
   ///
-  ///This class implements the \e binary \e heap data structure. 
-  /// 
-  ///A \e heap is a data structure for storing items with specified values
-  ///called \e priorities in such a way that finding the item with minimum
-  ///priority is efficient. \c Comp specifies the ordering of the priorities.
-  ///In a heap one can change the priority of an item, add or erase an
-  ///item, etc.
+  ///This class implements the \e binary \e heap data structure. A \e heap
+  ///is a data structure for storing items with specified values called \e
+  ///priorities in such a way that finding the item with minimum priority is
+  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
+  ///one can change the priority of an item, add or erase an item, etc.
   ///
-  ///\tparam PR Type of the priority of the items.
-  ///\tparam IM A read and writable item map with int values, used internally
+  ///\tparam _Prio Type of the priority of the items.
+  ///\tparam _ItemIntMap A read and writable Item int map, used internally
   ///to handle the cross references.
-  ///\tparam Comp A functor class for the ordering of the priorities.
-  ///The default is \c std::less<PR>.
+  ///\tparam _Compare A class for the ordering of the priorities. The
+  ///default is \c std::less<_Prio>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename PR, typename IM, typename Comp = std::less<PR> >
+  template <typename _Prio, typename _ItemIntMap,
+            typename _Compare = std::less<_Prio> >
   class BinHeap {
 
   public:
     ///\e
-    typedef IM ItemIntMap;
-    ///\e
-    typedef PR Prio;
+    typedef _ItemIntMap ItemIntMap;
+    ///\e
+    typedef _Prio Prio;
     ///\e
     typedef typename ItemIntMap::Key Item;
@@ -63 +62 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef Comp Compare;
+    typedef _Compare Compare;
 
     /// \brief Type to represent the items states.
@@ -71 +70 @@
     /// heap's point of view, but may be useful to the user.
     ///
-    /// The item-int map must be initialized in such way that it assigns
-    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
+    /// The ItemIntMap \e should be initialized in such way that it maps
+    /// PRE_HEAP (-1) to any element to be put in the heap...
     enum State {
-      IN_HEAP = 0,    ///< = 0.
-      PRE_HEAP = -1,  ///< = -1.
-      POST_HEAP = -2  ///< = -2.
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
     };
 
   private:
-    std::vector<Pair> _data;
-    Compare _comp;
-    ItemIntMap &_iim;
+    std::vector<Pair> data;
+    Compare comp;
+    ItemIntMap &iim;
 
   public:
@@ -88 +87 @@
     ///
     /// The constructor.
-    /// \param map should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
-    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
-
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param map should be given to the constructor, since it is used
+    /// \param _iim 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.
-    ///
-    /// \param comp The comparator function object.
-    BinHeap(ItemIntMap &map, const Compare &comp)
-      : _iim(map), _comp(comp) {}
+    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _iim 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.
+    ///
+    /// \param _comp The comparator function object.
+    BinHeap(ItemIntMap &_iim, const Compare &_comp)
+      : iim(_iim), comp(_comp) {}
 
 
@@ -108 +107 @@
     ///
     /// \brief Returns the number of items stored in the heap.
-    int size() const { return _data.size(); }
+    int size() const { return data.size(); }
 
     /// \brief Checks if the heap stores no items.
     ///
     /// Returns \c true if and only if the heap stores no items.
-    bool empty() const { return _data.empty(); }
+    bool empty() const { return data.empty(); }
 
     /// \brief Make empty this heap.
@@ -122 +121 @@
     /// each item to \c PRE_HEAP.
     void clear() {
-      _data.clear();
+      data.clear();
     }
 
@@ -130 +129 @@
     static int second_child(int i) { return 2*i+2; }
     bool less(const Pair &p1, const Pair &p2) const {
-      return _comp(p1.second, p2.second);
+      return comp(p1.second, p2.second);
     }
 
     int bubble_up(int hole, Pair p) {
       int par = parent(hole);
-      while( hole>0 && less(p,_data[par]) ) {
-        move(_data[par],hole);
+      while( hole>0 && less(p,data[par]) ) {
+        move(data[par],hole);
         hole = par;
         par = parent(hole);
@@ -147 +146 @@
       int child = second_child(hole);
       while(child < length) {
-        if( less(_data[child-1], _data[child]) ) {
+        if( less(data[child-1], data[child]) ) {
           --child;
         }
-        if( !less(_data[child], p) )
+        if( !less(data[child], p) )
           goto ok;
-        move(_data[child], hole);
+        move(data[child], hole);
         hole = child;
         child = second_child(hole);
       }
       child--;
-      if( child<length && less(_data[child], p) ) {
-        move(_data[child], hole);
+      if( child<length && less(data[child], p) ) {
+        move(data[child], hole);
         hole=child;
       }
@@ -167 +166 @@
 
     void move(const Pair &p, int i) {
-      _data[i] = p;
-      _iim.set(p.first, i);
+      data[i] = p;
+      iim.set(p.first, i);
     }
 
@@ -177 +176 @@
     /// \param p The pair to insert.
     void push(const Pair &p) {
-      int n = _data.size();
-      _data.resize(n+1);
+      int n = data.size();
+      data.resize(n+1);
       bubble_up(n, p);
     }
@@ -195 +194 @@
     /// \pre The heap must be nonempty.
     Item top() const {
-      return _data[0].first;
+      return data[0].first;
     }
 
@@ -203 +202 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      return _data[0].second;
+      return data[0].second;
     }
 
@@ -212 +211 @@
     /// \pre The heap must be non-empty.
     void pop() {
-      int n = _data.size()-1;
-      _iim.set(_data[0].first, POST_HEAP);
+      int n = data.size()-1;
+      iim.set(data[0].first, POST_HEAP);
       if (n > 0) {
-        bubble_down(0, _data[n], n);
-      }
-      _data.pop_back();
+        bubble_down(0, data[n], n);
+      }
+      data.pop_back();
     }
 
@@ -226 +225 @@
     /// \pre The item should be in the heap.
     void erase(const Item &i) {
-      int h = _iim[i];
-      int n = _data.size()-1;
-      _iim.set(_data[h].first, POST_HEAP);
+      int h = iim[i];
+      int n = data.size()-1;
+      iim.set(data[h].first, POST_HEAP);
       if( h < n ) {
-        if ( bubble_up(h, _data[n]) == h) {
-          bubble_down(h, _data[n], n);
+        if ( bubble_up(h, data[n]) == h) {
+          bubble_down(h, data[n], n);
         }
       }
-      _data.pop_back();
+      data.pop_back();
     }
 
@@ -241 +240 @@
     ///
     /// This function returns the priority of item \c i.
-    /// \param i The item.
     /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
-      int idx = _iim[i];
-      return _data[idx].second;
+      int idx = iim[i];
+      return data[idx].second;
     }
 
@@ -256 +255 @@
     /// \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);
       }
-      else if( _comp(p, _data[idx].second) ) {
+      else if( comp(p, data[idx].second) ) {
         bubble_up(idx, Pair(i,p));
       }
       else {
-        bubble_down(idx, Pair(i,p), _data.size());
+        bubble_down(idx, Pair(i,p), data.size());
       }
     }
@@ -271 +270 @@
     ///
     /// This method decreases the priority of item \c i to \c p.
-    /// \param i The item.
-    /// \param p The priority.
     /// \pre \c i must be stored in the heap with priority at least \c
     /// p relative to \c Compare.
+    /// \param i The item.
+    /// \param p The priority.
     void decrease(const Item &i, const Prio &p) {
-      int idx = _iim[i];
+      int idx = iim[i];
       bubble_up(idx, Pair(i,p));
     }
@@ -283 +282 @@
     ///
     /// This method sets the priority of item \c i to \c p.
-    /// \param i The item.
-    /// \param p The priority.
     /// \pre \c i must be stored in the heap with priority at most \c
     /// p relative to \c Compare.
+    /// \param i The item.
+    /// \param p The priority.
     void increase(const Item &i, const Prio &p) {
-      int idx = _iim[i];
-      bubble_down(idx, Pair(i,p), _data.size());
+      int idx = iim[i];
+      bubble_down(idx, Pair(i,p), data.size());
     }
 
@@ -301 +300 @@
     /// \param i The item.
     State state(const Item &i) const {
-      int s = _iim[i];
+      int s = iim[i];
       if( s>=0 )
         s=0;
@@ -321 +320 @@
           erase(i);
         }
-        _iim[i] = st;
+        iim[i] = st;
         break;
       case IN_HEAP:
@@ -335 +334 @@
     /// with the same prioriority as prevoiusly the \c i item.
     void replace(const Item& i, const Item& j) {
-      int idx = _iim[i];
-      _iim.set(i, _iim[j]);
-      _iim.set(j, idx);
-      _data[idx].first = j;
+      int idx = iim[i];
+      iim.set(i, iim[j]);
+      iim.set(j, idx);
+      data[idx].first = j;
     }