LEMON/LEMON-official Changeset - r729:bb8c4cd57900

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r729:bb8c4cd57900

« 728:532697

730:9f529a »

r729:bb8c4cd57900

Thu, 11 Jun 2009 22:16:11

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Simplified implementation of bucket heaps (#50)

0 1 0

default

1 file changed with 51 insertions and 317 deletions:

lemon/bucket_heap.h

317

↑ Collapse diff ↑

lemon/bucket_heap.h

Show inline comments

@@ -31,2 +31,26 @@
 		  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
@@ -47,3 +71,3 @@
 		  /// the lowest priority.
-		  template <typename _ItemIntMap, bool minimize = true >
 		  template <typename _ItemIntMap, bool minimize = true>
 		  class BucketHeap {
@@ -60,2 +84,8 @@
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
 		  public:
 		    /// \brief Type to represent the items states.
@@ -163,3 +193,3 @@
 		      lace(idx);
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
@@ -174,3 +204,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -185,3 +215,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -196,3 +226,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -237,7 +267,7 @@
 		      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);
+		      }
@@ -256,3 +286,3 @@
 		      data[idx].value = p;
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
@@ -330,189 +360,2 @@
 		  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
@@ -526,3 +369,3 @@
 		  /// 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.
@@ -544,2 +387,8 @@
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
 		  public:
 		    /// \brief Type to represent the items states.
@@ -616,3 +465,3 @@
 		      first[p] = idx;
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
@@ -628,3 +477,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -639,3 +488,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -650,3 +499,3 @@
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
@@ -713,117 +562,2 @@
 		  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;
 		  };
+		}

0 comments (0 inline)

RhodeCode

Login to your account