Changeset 209:765619b7cbb2 in lemon for lemon/bin_heap.h

Timestamp:

07/13/08 20:51:02 (17 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Phase:

public

Message:

Apply unify-sources.sh to the source tree

File:

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

lemon/bin_heap.h

@@ -1 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
  * Copyright (C) 2003-2008
@@ -49 +49 @@
   ///\sa Dijkstra
   template <typename _Prio, typename _ItemIntMap,
-            typename _Compare = std::less<_Prio> >
+            typename _Compare = std::less<_Prio> >
   class BinHeap {
 
@@ -91 +91 @@
     /// should be PRE_HEAP (-1) for each element.
     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
-    
+
     /// \brief The constructor.
     ///
@@ -100 +100 @@
     ///
     /// \param _comp The comparator function object.
-    BinHeap(ItemIntMap &_iim, const Compare &_comp) 
+    BinHeap(ItemIntMap &_iim, const Compare &_comp)
       : iim(_iim), comp(_comp) {}
 
@@ -108 +108 @@
     /// \brief Returns the number of items stored in the heap.
     int size() const { return data.size(); }
-    
+
     /// \brief Checks if the heap stores no items.
     ///
@@ -115 +115 @@
 
     /// \brief Make empty this heap.
-    /// 
+    ///
     /// Make empty this heap. It does not change the cross reference map.
     /// If you want to reuse what is not surely empty you should first clear
     /// the heap and after that you should set the cross reference map for
     /// each item to \c PRE_HEAP.
-    void clear() { 
-      data.clear(); 
+    void clear() {
+      data.clear();
     }
 
@@ -135 +135 @@
       int par = parent(hole);
       while( hole>0 && less(p,data[par]) ) {
-        move(data[par],hole);
-        hole = par;
-        par = parent(hole);
+        move(data[par],hole);
+        hole = par;
+        par = parent(hole);
       }
       move(p, hole);
@@ -146 +146 @@
       int child = second_child(hole);
       while(child < length) {
-        if( less(data[child-1], data[child]) ) {
-          --child;
-        }
-        if( !less(data[child], p) )
-          goto ok;
-        move(data[child], hole);
-        hole = child;
-        child = second_child(hole);
+        if( less(data[child-1], data[child]) ) {
+          --child;
+        }
+        if( !less(data[child], p) )
+          goto ok;
+        move(data[child], hole);
+        hole = child;
+        child = second_child(hole);
       }
       child--;
       if( child<length && less(data[child], p) ) {
-        move(data[child], hole);
-        hole=child;
+        move(data[child], hole);
+        hole=child;
       }
     ok:
@@ -182 +182 @@
 
     /// \brief Insert an item into the heap with the given heap.
-    ///    
-    /// Adds \c i to the heap with priority \c p. 
+    ///
+    /// Adds \c i to the heap with priority \c p.
     /// \param i The item to insert.
     /// \param p The priority of the item.
@@ -191 +191 @@
     ///
     /// This method returns the item with minimum priority relative to \c
-    /// Compare.  
-    /// \pre The heap must be nonempty.  
+    /// Compare.
+    /// \pre The heap must be nonempty.
     Item top() const {
       return data[0].first;
@@ -208 +208 @@
     ///
     /// This method deletes the item with minimum priority relative to \c
-    /// Compare from the heap.  
-    /// \pre The heap must be non-empty.  
+    /// Compare from the heap.
+    /// \pre The heap must be non-empty.
     void pop() {
       int n = data.size()-1;
       iim.set(data[0].first, POST_HEAP);
       if (n > 0) {
-        bubble_down(0, data[n], n);
+        bubble_down(0, data[n], n);
       }
       data.pop_back();
@@ -229 +229 @@
       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();
     }
 
-    
+
     /// \brief Returns the priority of \c i.
     ///
-    /// This function returns the priority of item \c i.  
+    /// This function returns the priority of item \c i.
     /// \pre \c i must be in the heap.
     /// \param i The item.
@@ -247 +247 @@
     }
 
-    /// \brief \c i gets to the heap with priority \c p independently 
+    /// \brief \c i gets to the heap with priority \c p independently
     /// if \c i was already there.
     ///
@@ -257 +257 @@
       int idx = iim[i];
       if( idx < 0 ) {
-        push(i,p);
+        push(i,p);
       }
       else if( comp(p, data[idx].second) ) {
-        bubble_up(idx, Pair(i,p));
+        bubble_up(idx, Pair(i,p));
       }
       else {
-        bubble_down(idx, Pair(i,p), data.size());
+        bubble_down(idx, Pair(i,p), data.size());
       }
     }
@@ -278 +278 @@
       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. 
+    /// 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.
@@ -291 +291 @@
     }
 
-    /// \brief Returns if \c item is in, has already been in, or has 
+    /// \brief Returns if \c item is in, has already been in, or has
     /// never been in the heap.
     ///
@@ -302 +302 @@
       int s = iim[i];
       if( s>=0 )
-        s=0;
+        s=0;
       return State(s);
     }
@@ -312 +312 @@
     /// better time complexity.
     /// \param i The item.
-    /// \param st The state. It should not be \c IN_HEAP. 
+    /// \param st The state. It should not be \c IN_HEAP.
     void state(const Item& i, State st) {
       switch (st) {
@@ -341 +341 @@
 
   }; // class BinHeap
-  
+
 } // namespace lemon