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

@@ -20,53 +20,83 @@
 		#define LEMON_BUCKET_HEAP_H
 		///\ingroup auxdat
 		///\file
 		///\brief Bucket Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		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.
 		  ///
 		  /// This class implements the \e bucket \e heap data structure. A \e heap
 		  /// is a data structure for storing items with specified values called \e
 		  /// priorities in such a way that finding the item with minimum priority is
 		  /// efficient. The bucket heap is very simple implementation, it can store
 		  /// only integer priorities and it stores for each priority in the
 		  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
 		  /// the priorities are small. It is not intended to use as dijkstra heap.
 		  ///
 		  /// \param _ItemIntMap A read and writable Item int map, used internally
 		  /// 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:
 		    /// \e
 		    typedef typename _ItemIntMap::Key Item;
 		    /// \e
 		    typedef int Prio;
 		    /// \e
 		    typedef std::pair<Item, Prio> Pair;
 		    /// \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",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// 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 {
 		      IN_HEAP = 0,
 		      PRE_HEAP = -1,
 		      POST_HEAP = -2
@@ -152,58 +182,58 @@
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// Adds \c i to the heap with priority \c p.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    void push(const Item &i, const Prio &p) {
 		      int idx = data.size();
 		      index[i] = idx;
 		      data.push_back(BucketItem(i, p));
 		      lace(idx);
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
+		    }
 		    /// \brief Returns the item with minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    Item top() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return data[first[minimal]].item;
+		    }
 		    /// \brief Returns the minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    Prio prio() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return minimal;
+		    }
 		    /// \brief Deletes the item with minimum priority.
 		    ///
 		    /// This method deletes the item with minimum priority from the heap.
 		    /// \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;
 		      unlace(idx);
 		      relocate_last(idx);
+		    }
 		    /// \brief Deletes \c i from the heap.
 		    ///
 		    /// This method deletes item \c i from the heap, if \c i was
 		    /// already stored in the heap.
 		    /// \param i The item to erase.
@@ -226,44 +256,44 @@
+		    }
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    ///
 		    /// This method calls \ref push(\c i, \c p) if \c i is not stored
 		    /// in the heap and sets the priority of \c i to \c p otherwise.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    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);
+		      }
+		    }
 		    /// \brief Decreases the priority of \c i to \c p.
 		    ///
 		    /// This method decreases the priority of item \c i to \c p.
 		    /// \pre \c i must be stored in the heap with priority at least \c
 		    /// p relative to \c Compare.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = index[i];
 		      unlace(idx);
 		      data[idx].value = p;
-		      if (p < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
 		      lace(idx);
+		    }
 		    /// \brief Increases the priority of \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.
 		    /// \param i The item.
 		    /// \param p The priority.
@@ -319,238 +349,57 @@
 		      int value;
 		      int prev, next;
 		    };
 		    ItemIntMap& index;
 		    std::vector<int> first;
 		    std::vector<BucketItem> data;
 		    mutable int minimal;
 		  }; // 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.
 		  ///
 		  /// This class implements a simplified \e bucket \e heap data
 		  /// structure.  It does not provide some functionality but it faster
 		  /// 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
 		  /// to handle the cross references.
 		  /// \param minimize If the given parameter is true then the heap gives back
 		  /// the lowest priority.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename _ItemIntMap, bool minimize = true >
 		  class SimpleBucketHeap {
 		  public:
 		    typedef typename _ItemIntMap::Key Item;
 		    typedef int Prio;
 		    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",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// 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 {
 		      IN_HEAP = 0,
 		      PRE_HEAP = -1,
 		      POST_HEAP = -2
@@ -605,59 +454,59 @@
 		      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 < minimal) {
+		      if (Direction::less(p, minimal)) {
 		        minimal = p;
+		      }
 		      ++num;
+		    }
 		    /// \brief Returns the item with minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    Item top() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return data[first[minimal]].item;
+		    }
 		    /// \brief Returns the minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    Prio prio() const {
 		      while (first[minimal] == -1) {
-		        ++minimal;
+		        Direction::increase(minimal);
+		      }
 		      return minimal;
+		    }
 		    /// \brief Deletes the item with minimum priority.
 		    ///
 		    /// This method deletes the item with minimum priority from the heap.
 		    /// \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;
 		      first[minimal] = data[idx].next;
 		      data[idx].next = free;
 		      free = idx;
 		      --num;
+		    }
 		    /// \brief Returns the priority of \c i.
 		    ///
 		    /// This function returns the priority of item \c i.
@@ -702,130 +551,15 @@
 		      Item item;
 		      int next;
 		    };
 		    ItemIntMap& index;
 		    std::vector<int> first;
 		    std::vector<BucketItem> data;
 		    int free, num;
 		    mutable int minimal;
 		  }; // 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

0 comments (0 inline)

RhodeCode

Login to your account