StoredPriorityQueue.h

Go to the documentation of this file.

#ifndef StoredPriorityQueue_HEADER
#define StoredPriorityQueue_HEADER

/***************************************************************************
 * Benoit Hudson (C) 2007.
 ***************************************************************************/

#include <boost/type_traits/is_empty.hpp>
#include <functional> // std::less
#include <queue> // std::priority_queue
#include <vector> // std::vector

namespace hudson {
/***************************************************************************
 * \file
 *
 * A priority queue for ordering things, where we store the key separate from
 * the item.  This is pretty common usage, and not entirely trivial to do
 * using stl's priority_queue.
 ***************************************************************************/

namespace details {

  /************************************************************
   * I don't want to pay any storage at all for when
   * compare/compute are empty classes (like std::less).
   * Hence these four template specializations, which all satisfy
   * that they have a public pq_, getCompare(), and getCompute().
   ************************************************************/
  template <class PQ, class Compare, bool compare_empty, class Compute, bool compute_empty>
    struct WrapPQ {
      PQ pq_;
      Compare compare_;
      Compute compute_;

      WrapPQ(const Compare& compare, const Compute& compute)
        : compare_(compare), compute_(compute) { }
      const Compare& getCompare() const { return compare_; }
      const Compute& getCompute() const { return compute_; }
    };

  template <class PQ, class Compare, class Compute>
    struct WrapPQ<PQ, Compare, true, Compute, false> {
      PQ pq_;
      Compute compute_;

      WrapPQ(const Compare&, const Compute& compute)
        : compute_(compute) { }
      Compare getCompare() const { return Compare(); }
      const Compute& getCompute() const { return compute_; }
    };

  template <class PQ, class Compare, class Compute>
    struct WrapPQ<PQ, Compare, false, Compute, true> {
      PQ pq_;
      Compare compare_;

      WrapPQ(const Compare& compare, const Compute&)
        : compare_(compare) { }
      const Compare& getCompare() const { return compare_; }
      Compute getCompute() const { return Compute(); }
    };

  template <class PQ, class Compare, class Compute>
    struct WrapPQ<PQ, Compare, true, Compute, true> {
      PQ pq_;

      WrapPQ(const Compare&, const Compute&) { }
      Compare getCompare() const { return Compare(); }
      Compute getCompute() const { return Compute(); }
    };


} /* end details */

/***************************************************************************
 * A priority queue for ordering things, where we store the key separate from
 * the item.  This is pretty common usage, and not entirely trivial to do
 * using stl's priority_queue.
 *
 * Compare and Compute are function objects.  Compare should compare two Keys;
 * Compute should take an Item and return a Key.
 ***************************************************************************/
template <class Key, class Item, class Compute, class Compare = std::less<Key> >
class StoredPriorityQueue {
  typedef pair<Key, Item> ki_pair;

  struct compare_pair : private Compare { /* inherit rather than contain: saves size */
    compare_pair(): Compare() { }
    compare_pair(const Compare& comp): Compare(comp) { }
    bool operator()(const ki_pair& a, const ki_pair& b) const {
      return Compare::operator()(a.first, b.first);
    }
  };

  details::WrapPQ<
    std::priority_queue<ki_pair, std::vector<ki_pair>, compare_pair>,
    compare_pair, boost::is_empty<compare_pair>::value,
    Compute, boost::is_empty<Compute>::value
    > q_;

  public:
  StoredPriorityQueue(): q_(compare_pair(), Compute()) { }
  StoredPriorityQueue(const Compute& ute): q_(compare_pair(), ute) { }
  StoredPriorityQueue(const Compare& are): q_(compare_pair(are), Compute()) { }
  StoredPriorityQueue(const Compute& ute, const Compare& are): q_(compare_pair(are), ute) { }

  const ki_pair& top_pair() const {
    assert(!empty());
    return q_.pq_.top();
  }

  const Item& top() const { return top_pair().second; }

  void pop() { q_.pq_.pop(); }

  void push(const Key& k, const Item& i) {
    q_.pq_.push(make_pair(k, i));
  }

  void push(const ki_pair& p) {
    q_.pq_.push(p);
  }

  void push(const Item& i) {
    push(getPriority(i), i);
  }

  bool empty() const { return q_.pq_.empty(); }

  bool compare(const Key& a, const Key& b) const {
    return q_.getCompare()(a, b);
  }
  Key getPriority(const Item& i) const {
    return q_.getCompute()(i);
  }
};

} // namespace hudson
#endif

---