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 49 insertions and 315 deletions:

lemon/bucket_heap.h

315

↑ Collapse diff ↑

lemon/bucket_heap.h

Show inline comments

@@ -30,4 +30,28 @@
 		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
 		  ///
@@ -59,4 +83,10 @@
 		    typedef _ItemIntMap ItemIntMap;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
 		  public:
 		    /// \brief Type to represent the items states.
 		    ///
@@ -162,5 +192,5 @@
 		      data.push_back(BucketItem(i, p));
 		      lace(idx);
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
@@ -173,5 +203,5 @@
 		    Item top() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return data[first[minimal]].item;
@@ -184,5 +214,5 @@
 		    Prio prio() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return minimal;
@@ -195,5 +225,5 @@
 		    void pop() {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      int idx = first[minimal];
@@ -237,8 +267,8 @@
 		      if (idx < 0) {
 		        push(i,p);
-		      } else if (p > data[idx].value) {
+		      } else if (Direction::less(p, data[idx].value)) {
 		        decrease(i, p);
 		      } else {
 		        increase(i, p);
 		      } else {
 		        decrease(i, p);
+		      }
+		    }
@@ -255,5 +285,5 @@
 		      unlace(idx);
 		      data[idx].value = p;
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
@@ -329,191 +359,4 @@
 		  }; // 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
 		  ///
@@ -525,5 +368,5 @@
 		  /// 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.
 		  ///
@@ -543,4 +386,10 @@
 		    typedef _ItemIntMap ItemIntMap;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<minimize> Direction;
 		  public:
 		    /// \brief Type to represent the items states.
 		    ///
@@ -615,5 +464,5 @@
 		      data[idx].next = first[p];
 		      first[p] = idx;
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
@@ -627,5 +476,5 @@
 		    Item top() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return data[first[minimal]].item;
@@ -638,5 +487,5 @@
 		    Prio prio() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return minimal;
@@ -649,5 +498,5 @@
 		    void pop() {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      int idx = first[minimal];
@@ -712,119 +561,4 @@
 		  }; // 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;
 		  };
+		}

0 comments (0 inline)

RhodeCode

Login to your account