Changeset 606:c5fd2d996909 in lemon for lemon/bin_heap.h

Timestamp:

03/29/09 23:08:20 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Various doc improvements (#248)

• Rename all the ugly template parameters (too long and/or starting with an underscore).
• Rename function parameters starting with an underscore.
• Extend the doc for many classes.
• Use LaTeX-style O(...) expressions only for the complicated ones.
• A lot of small unification changes.
• Small fixes.
• Some other improvements.

File:

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

lemon/bin_heap.h

@@ -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 Compare 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 Comp specifies the ordering of the priorities.
+  ///In a heap one can change the priority of an item, add or erase an
+  ///item, etc.
   ///
-  ///\tparam _Prio Type of the priority of the items.
-  ///\tparam _ItemIntMap A read and writable Item int map, used internally
+  ///\tparam PR Type of the priority of the items.
+  ///\tparam IM A read and writable item map with int values, used internally
   ///to handle the cross references.
-  ///\tparam _Compare A class for the ordering of the priorities. The
-  ///default is \c std::less<_Prio>.
+  ///\tparam Comp A functor class for the ordering of the priorities.
+  ///The default is \c std::less<PR>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename _Prio, typename _ItemIntMap,
-            typename _Compare = std::less<_Prio> >
+  template <typename PR, typename IM, typename Comp = std::less<PR> >
   class BinHeap {
 
   public:
     ///\e
-    typedef _ItemIntMap ItemIntMap;
-    ///\e
-    typedef _Prio Prio;
+    typedef IM ItemIntMap;
+    ///\e
+    typedef PR Prio;
     ///\e
     typedef typename ItemIntMap::Key Item;
@@ -62 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef _Compare Compare;
+    typedef Comp Compare;
 
     /// \brief Type to represent the items states.
@@ -70 +71 @@
     /// heap's point of view, but may be useful to the user.
     ///
-    /// The ItemIntMap \e should be initialized in such way that it maps
-    /// PRE_HEAP (-1) to any element to be put in the heap...
+    /// 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.
     enum State {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
+      IN_HEAP = 0,    ///< \e
+      PRE_HEAP = -1,  ///< \e
+      POST_HEAP = -2  ///< \e
     };
 
   private:
-    std::vector<Pair> data;
-    Compare comp;
-    ItemIntMap &iim;
+    std::vector<Pair> _data;
+    Compare _comp;
+    ItemIntMap &_iim;
 
   public:
@@ -87 +88 @@
     ///
     /// The constructor.
-    /// \param _iim should be given to the constructor, since it is used
+    /// \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
     /// internally to handle the cross references. The value of the map
     /// should be PRE_HEAP (-1) for each element.
-    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) {}
+    ///
+    /// \param comp The comparator function object.
+    BinHeap(ItemIntMap &map, const Compare &comp)
+      : _iim(map), _comp(comp) {}
 
 
@@ -107 +108 @@
     ///
     /// \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.
@@ -121 +122 @@
     /// each item to \c PRE_HEAP.
     void clear() {
-      data.clear();
+      _data.clear();
     }
 
@@ -129 +130 @@
     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);
@@ -146 +147 @@
       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;
       }
@@ -166 +167 @@
 
     void move(const Pair &p, int i) {
-      data[i] = p;
-      iim.set(p.first, i);
+      _data[i] = p;
+      _iim.set(p.first, i);
     }
 
@@ -176 +177 @@
     /// \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);
     }
@@ -194 +195 @@
     /// \pre The heap must be nonempty.
     Item top() const {
-      return data[0].first;
+      return _data[0].first;
     }
 
@@ -202 +203 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      return data[0].second;
+      return _data[0].second;
     }
 
@@ -211 +212 @@
     /// \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();
     }
 
@@ -225 +226 @@
     /// \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();
     }
 
@@ -240 +241 @@
     ///
     /// 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;
     }
 
@@ -255 +256 @@
     /// \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());
       }
     }
@@ -270 +271 @@
     ///
     /// 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.
+    void decrease(const Item &i, const Prio &p) {
+      int idx = _iim[i];
+      bubble_up(idx, Pair(i,p));
+    }
+
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p.
     /// \param i The item.
     /// \param p The priority.
-    void decrease(const Item &i, const Prio &p) {
-      int idx = iim[i];
-      bubble_up(idx, Pair(i,p));
-    }
-
-    /// \brief Increases the priority of \c i to \c p.
-    ///
-    /// This method sets the priority of item \c i to \c p.
     /// \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());
     }
 
@@ -300 +301 @@
     /// \param i The item.
     State state(const Item &i) const {
-      int s = iim[i];
+      int s = _iim[i];
       if( s>=0 )
         s=0;
@@ -320 +321 @@
           erase(i);
         }
-        iim[i] = st;
+        _iim[i] = st;
         break;
       case IN_HEAP:
@@ -334 +335 @@
     /// 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;
     }