Changeset 2547:f393a8162688 in lemon-0.x for lemon/bin_heap.h

Timestamp:

12/27/07 14:40:16 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424

Message:

Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

File:

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

lemon/bin_heap.h

@@ -40 +40 @@
   ///one can change the priority of an item, add or erase an item, etc.
   ///
-  ///\param Prio Type of the priority of the items.
-  ///\param ItemIntMap A read and writable Item int map, used internally
+  ///\param _Prio Type of the priority of the items.
+  ///\param _ItemIntMap A read and writable Item int map, used internally
   ///to handle the cross references.
-  ///\param Compare A class for the ordering of the priorities. The
-  ///default is \c std::less<Prio>.
+  ///\param _Compare A class for the ordering of the priorities. The
+  ///default is \c std::less<_Prio>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename Prio, typename ItemIntMap,
-            typename Compare = std::less<Prio> >
+  template <typename _Prio, typename _ItemIntMap,
+            typename _Compare = std::less<_Prio> >
   class BinHeap {
 
   public:
-    typedef typename ItemIntMap::Key         ItemType;
-    typedef Prio                             PrioType;
-    typedef std::pair<ItemType,PrioType>     PairType;
-    typedef ItemIntMap                       ItemIntMapType;
-    typedef Compare                          PrioCompare;
+    typedef _ItemIntMap ItemIntMap;
+    typedef _Prio Prio;
+    typedef typename ItemIntMap::Key Item;
+    typedef std::pair<Item,Prio> Pair;
+    typedef _Compare Compare;
 
     /// \brief Type to represent the items states.
@@ -67 +67 @@
     /// 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_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
@@ -74 +74 @@
 
   private:
-    std::vector<PairType> data;
+    std::vector<Pair> data;
     Compare comp;
     ItemIntMap &iim;
@@ -123 +123 @@
 
     static int second_child(int i) { return 2*i+2; }
-    bool less(const PairType &p1, const PairType &p2) const {
+    bool less(const Pair &p1, const Pair &p2) const {
       return comp(p1.second, p2.second);
     }
 
-    int bubble_up(int hole, PairType p) {
+    int bubble_up(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,data[par]) ) {
@@ -138 +138 @@
     }
 
-    int bubble_down(int hole, PairType p, int length) {
+    int bubble_down(int hole, Pair p, int length) {
       int child = second_child(hole);
       while(child < length) {
@@ -160 +160 @@
     }
 
-    void move(const PairType &p, int i) {
+    void move(const Pair &p, int i) {
       data[i] = p;
       iim.set(p.first, i);
@@ -170 +170 @@
     /// Adds \c p.first to the heap with priority \c p.second.
     /// \param p The pair to insert.
-    void push(const PairType &p) {
+    void push(const Pair &p) {
       int n = data.size();
       data.resize(n+1);
@@ -181 +181 @@
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
+    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 
     /// \brief Returns the item with minimum priority relative to \c Compare.
@@ -188 +188 @@
     /// Compare.  
     /// \pre The heap must be nonempty.  
-    ItemType top() const {
+    Item top() const {
       return data[0].first;
     }
@@ -219 +219 @@
     /// \param i The item to erase.
     /// \pre The item should be in the heap.
-    void erase(const ItemType &i) {
+    void erase(const Item &i) {
       int h = iim[i];
       int n = data.size()-1;
@@ -237 +237 @@
     /// \pre \c i must be in the heap.
     /// \param i The item.
-    Prio operator[](const ItemType &i) const {
+    Prio operator[](const Item &i) const {
       int idx = iim[i];
       return data[idx].second;
@@ -249 +249 @@
     /// \param i The item.
     /// \param p The priority.
-    void set(const ItemType &i, const Prio &p) {
+    void set(const Item &i, const Prio &p) {
       int idx = iim[i];
       if( idx < 0 ) {
@@ -255 +255 @@
       }
       else if( comp(p, data[idx].second) ) {
-        bubble_up(idx, PairType(i,p));
+        bubble_up(idx, Pair(i,p));
       }
       else {
-        bubble_down(idx, PairType(i,p), data.size());
+        bubble_down(idx, Pair(i,p), data.size());
       }
     }
@@ -269 +269 @@
     /// \param i The item.
     /// \param p The priority.
-    void decrease(const ItemType &i, const Prio &p) {
+    void decrease(const Item &i, const Prio &p) {
       int idx = iim[i];
-      bubble_up(idx, PairType(i,p));
+      bubble_up(idx, Pair(i,p));
     }
     
@@ -281 +281 @@
     /// \param i The item.
     /// \param p The priority.
-    void increase(const ItemType &i, const Prio &p) {
+    void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
-      bubble_down(idx, PairType(i,p), data.size());
+      bubble_down(idx, Pair(i,p), data.size());
     }
 
@@ -294 +294 @@
     /// get back to the heap again.
     /// \param i The item.
-    state_enum state(const ItemType &i) const {
+    State state(const Item &i) const {
       int s = iim[i];
       if( s>=0 )
         s=0;
-      return state_enum(s);
+      return State(s);
     }
 
@@ -308 +308 @@
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const ItemType& i, state_enum st) {
+    void state(const Item& i, State st) {
       switch (st) {
       case POST_HEAP: