# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 2009-06-11 22:16:11
# Node ID bb8c4cd57900e4b3052fd3f5b20263cf4da343de
# Parent  532697c9fa536a2cd3ccc715b47f1e6a678510a6

Simplified implementation of bucket heaps (#50)

diff --git a/lemon/bucket_heap.h b/lemon/bucket_heap.h
--- a/lemon/bucket_heap.h
+++ b/lemon/bucket_heap.h
@@ -29,6 +29,30 @@
 
 namespace lemon {
 
+  namespace _bucket_heap_bits {
+
+    template <bool minimize>
+    struct DirectionTraits {
+      static bool less(int left, int right) {
+        return left < right;
+      }
+      static void increase(int& value) {
+        ++value;
+      }
+    };
+
+    template <>
+    struct DirectionTraits<false> {
+      static bool less(int left, int right) {
+        return left > right;
+      }
+      static void increase(int& value) {
+        --value;
+      }
+    };
+
+  }
+
   /// \ingroup auxdat
   ///
   /// \brief A Bucket Heap implementation.
@@ -45,7 +69,7 @@
   /// to handle the cross references.
   /// \param minimize If the given parameter is true then the heap gives back
   /// the lowest priority.
-  template <typename _ItemIntMap, bool minimize = true >
+  template <typename _ItemIntMap, bool minimize = true>
   class BucketHeap {
 
   public:
@@ -58,6 +82,12 @@
     /// \e
     typedef _ItemIntMap ItemIntMap;
 
+  private:
+
+    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
+
+  public:
+
     /// \brief Type to represent the items states.
     ///
     /// Each Item element have a state associated to it. It may be "in heap",
@@ -161,7 +191,7 @@
       index[i] = idx;
       data.push_back(BucketItem(i, p));
       lace(idx);
-      if (p < minimal) {
+      if (Direction::less(p, minimal)) {
         minimal = p;
       }
     }
@@ -172,7 +202,7 @@
     /// \pre The heap must be nonempty.
     Item top() const {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       return data[first[minimal]].item;
     }
@@ -183,7 +213,7 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       return minimal;
     }
@@ -194,7 +224,7 @@
     /// \pre The heap must be non-empty.
     void pop() {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       int idx = first[minimal];
       index[data[idx].item] = -2;
@@ -235,11 +265,11 @@
     void set(const Item &i, const Prio &p) {
       int idx = index[i];
       if (idx < 0) {
-        push(i,p);
-      } else if (p > data[idx].value) {
+        push(i, p);
+      } else if (Direction::less(p, data[idx].value)) {
+        decrease(i, p);
+      } else {
         increase(i, p);
-      } else {
-        decrease(i, p);
       }
     }
 
@@ -254,7 +284,7 @@
       int idx = index[i];
       unlace(idx);
       data[idx].value = p;
-      if (p < minimal) {
+      if (Direction::less(p, minimal)) {
         minimal = p;
       }
       lace(idx);
@@ -328,193 +358,6 @@
 
   }; // class BucketHeap
 
-
-  template <typename _ItemIntMap>
-  class BucketHeap<_ItemIntMap, false> {
-
-  public:
-    typedef typename _ItemIntMap::Key Item;
-    typedef int Prio;
-    typedef std::pair<Item, Prio> Pair;
-    typedef _ItemIntMap ItemIntMap;
-
-    enum State {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-
-  public:
-
-    explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
-
-    int size() const { return data.size(); }
-    bool empty() const { return data.empty(); }
-
-    void clear() {
-      data.clear(); first.clear(); maximal = -1;
-    }
-
-  private:
-
-    void relocate_last(int idx) {
-      if (idx + 1 != int(data.size())) {
-        data[idx] = data.back();
-        if (data[idx].prev != -1) {
-          data[data[idx].prev].next = idx;
-        } else {
-          first[data[idx].value] = idx;
-        }
-        if (data[idx].next != -1) {
-          data[data[idx].next].prev = idx;
-        }
-        index[data[idx].item] = idx;
-      }
-      data.pop_back();
-    }
-
-    void unlace(int idx) {
-      if (data[idx].prev != -1) {
-        data[data[idx].prev].next = data[idx].next;
-      } else {
-        first[data[idx].value] = data[idx].next;
-      }
-      if (data[idx].next != -1) {
-        data[data[idx].next].prev = data[idx].prev;
-      }
-    }
-
-    void lace(int idx) {
-      if (int(first.size()) <= data[idx].value) {
-        first.resize(data[idx].value + 1, -1);
-      }
-      data[idx].next = first[data[idx].value];
-      if (data[idx].next != -1) {
-        data[data[idx].next].prev = idx;
-      }
-      first[data[idx].value] = idx;
-      data[idx].prev = -1;
-    }
-
-  public:
-
-    void push(const Pair& p) {
-      push(p.first, p.second);
-    }
-
-    void push(const Item &i, const Prio &p) {
-      int idx = data.size();
-      index[i] = idx;
-      data.push_back(BucketItem(i, p));
-      lace(idx);
-      if (data[idx].value > maximal) {
-        maximal = data[idx].value;
-      }
-    }
-
-    Item top() const {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      return data[first[maximal]].item;
-    }
-
-    Prio prio() const {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      return maximal;
-    }
-
-    void pop() {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      int idx = first[maximal];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    void erase(const Item &i) {
-      int idx = index[i];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    Prio operator[](const Item &i) const {
-      int idx = index[i];
-      return data[idx].value;
-    }
-
-    void set(const Item &i, const Prio &p) {
-      int idx = index[i];
-      if (idx < 0) {
-        push(i,p);
-      } else if (p > data[idx].value) {
-        decrease(i, p);
-      } else {
-        increase(i, p);
-      }
-    }
-
-    void decrease(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      if (p > maximal) {
-        maximal = p;
-      }
-      lace(idx);
-    }
-
-    void increase(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      lace(idx);
-    }
-
-    State state(const Item &i) const {
-      int idx = index[i];
-      if (idx >= 0) idx = 0;
-      return State(idx);
-    }
-
-    void state(const Item& i, State st) {
-      switch (st) {
-      case POST_HEAP:
-      case PRE_HEAP:
-        if (state(i) == IN_HEAP) {
-          erase(i);
-        }
-        index[i] = st;
-        break;
-      case IN_HEAP:
-        break;
-      }
-    }
-
-  private:
-
-    struct BucketItem {
-      BucketItem(const Item& _item, int _value)
-        : item(_item), value(_value) {}
-
-      Item item;
-      int value;
-
-      int prev, next;
-    };
-
-    ItemIntMap& index;
-    std::vector<int> first;
-    std::vector<BucketItem> data;
-    mutable int maximal;
-
-  }; // class BucketHeap
-
   /// \ingroup auxdat
   ///
   /// \brief A Simplified Bucket Heap implementation.
@@ -524,7 +367,7 @@
   /// and simplier data structure than the BucketHeap. The main
   /// difference is that the BucketHeap stores for every key a double
   /// linked list while this class stores just simple lists. In the
-  /// other way it does not supports erasing each elements just the
+  /// other way it does not support erasing each elements just the
   /// minimal and it does not supports key increasing, decreasing.
   ///
   /// \param _ItemIntMap A read and writable Item int map, used internally
@@ -542,6 +385,12 @@
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
 
+  private:
+
+    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
+
+  public:
+
     /// \brief Type to represent the items states.
     ///
     /// Each Item element have a state associated to it. It may be "in heap",
@@ -614,7 +463,7 @@
       if (p >= int(first.size())) first.resize(p + 1, -1);
       data[idx].next = first[p];
       first[p] = idx;
-      if (p < minimal) {
+      if (Direction::less(p, minimal)) {
         minimal = p;
       }
       ++num;
@@ -626,7 +475,7 @@
     /// \pre The heap must be nonempty.
     Item top() const {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       return data[first[minimal]].item;
     }
@@ -637,7 +486,7 @@
     /// \pre The heap must be nonempty.
     Prio prio() const {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       return minimal;
     }
@@ -648,7 +497,7 @@
     /// \pre The heap must be non-empty.
     void pop() {
       while (first[minimal] == -1) {
-        ++minimal;
+        Direction::increase(minimal);
       }
       int idx = first[minimal];
       index[data[idx].item] = -2;
@@ -711,121 +560,6 @@
 
   }; // class SimpleBucketHeap
 
-  template <typename _ItemIntMap>
-  class SimpleBucketHeap<_ItemIntMap, false> {
-
-  public:
-    typedef typename _ItemIntMap::Key Item;
-    typedef int Prio;
-    typedef std::pair<Item, Prio> Pair;
-    typedef _ItemIntMap ItemIntMap;
-
-    enum State {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-
-  public:
-
-    explicit SimpleBucketHeap(ItemIntMap &_index)
-      : index(_index), free(-1), num(0), maximal(0) {}
-
-    int size() const { return num; }
-
-    bool empty() const { return num == 0; }
-
-    void clear() {
-      data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
-    }
-
-    void push(const Pair& p) {
-      push(p.first, p.second);
-    }
-
-    void push(const Item &i, const Prio &p) {
-      int idx;
-      if (free == -1) {
-        idx = data.size();
-        data.push_back(BucketItem(i));
-      } else {
-        idx = free;
-        free = data[idx].next;
-        data[idx].item = i;
-      }
-      index[i] = idx;
-      if (p >= int(first.size())) first.resize(p + 1, -1);
-      data[idx].next = first[p];
-      first[p] = idx;
-      if (p > maximal) {
-        maximal = p;
-      }
-      ++num;
-    }
-
-    Item top() const {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      return data[first[maximal]].item;
-    }
-
-    Prio prio() const {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      return maximal;
-    }
-
-    void pop() {
-      while (first[maximal] == -1) {
-        --maximal;
-      }
-      int idx = first[maximal];
-      index[data[idx].item] = -2;
-      first[maximal] = data[idx].next;
-      data[idx].next = free;
-      free = idx;
-      --num;
-    }
-
-    Prio operator[](const Item &i) const {
-      for (int k = 0; k < first.size(); ++k) {
-        int idx = first[k];
-        while (idx != -1) {
-          if (data[idx].item == i) {
-            return k;
-          }
-          idx = data[idx].next;
-        }
-      }
-      return -1;
-    }
-
-    State state(const Item &i) const {
-      int idx = index[i];
-      if (idx >= 0) idx = 0;
-      return State(idx);
-    }
-
-  private:
-
-    struct BucketItem {
-      BucketItem(const Item& _item) : item(_item) {}
-
-      Item item;
-
-      int next;
-    };
-
-    ItemIntMap& index;
-    std::vector<int> first;
-    std::vector<BucketItem> data;
-    int free, num;
-    mutable int maximal;
-
-  };
-
 }
 
 #endif