priority_queue.h

Go to the documentation of this file.

// Copyright 2016 Google Inc.

#ifndef PAGESPEED_CONTROLLER_PRIORITY_QUEUE_H_
#define PAGESPEED_CONTROLLER_PRIORITY_QUEUE_H_

#include <cstddef>
#include <functional>
#include <utility>
#include <unordered_map>
#include <vector>

#include "base/logging.h"
#include "base/macros.h"
#include "pagespeed/kernel/base/basictypes.h"


namespace net_instaweb {

template <typename T,
          typename HashFn = std::hash<T>,
          typename EqFn = std::equal_to<T>>
class PriorityQueue {
 public:
  PriorityQueue() { }
  ~PriorityQueue() { Clear(); }

  void IncreasePriority(const T& key, int64 amount);

  void Increment(const T& key);

  void Remove(const T& key);

  const std::pair<const T*, int64>& Top() const;

  void Pop();

  bool Empty() const { return queue_.empty(); }
  size_t Size() const { return queue_.size(); }

  void Clear();

 private:
  struct PtrHash {
    size_t operator()(const T* x) const {
      return HashFn()(*x);
    }
  };

  struct PtrEq {
    bool operator()(const T* x, const T* y) const {
      return (x == y || EqFn()(*x, *y));
    }
  };

  void Rebalance(size_t pos); 
  void PushDown(size_t pos);
  void PushUp(size_t pos);

  void SwapElements(size_t a, size_t b);

  void SanityCheckForTesting() const;

  typedef std::unordered_map<const T*, size_t, PtrHash, PtrEq>
      IndexMap;
  IndexMap index_map_;

  typedef std::pair<const T*, int64> QueueEntry;
  std::vector<QueueEntry> queue_;

  friend class PriorityQueueTest;

  
};

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::Clear() {
  index_map_.clear();
  for (const QueueEntry& qe : queue_) {
    delete qe.first;
  }
  queue_.clear();
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::Increment(const T& key) {
  IncreasePriority(key, 1);
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::IncreasePriority(const T& key,
                                                     int64 amount) {
  typename IndexMap::iterator i = index_map_.find(&key);
  if (i == index_map_.end()) {
    size_t queue_pos = queue_.size();
    queue_.emplace_back(new T(key), 0);
    const T* created_key = queue_.back().first;
    std::pair<typename IndexMap::iterator, bool> insert_result =
        index_map_.emplace(created_key, queue_pos);
    CHECK(insert_result.second); 
    i = insert_result.first;
  }
  size_t queue_pos = i->second;
  CHECK(queue_pos < queue_.size());
  queue_[queue_pos].second += amount;
  Rebalance(queue_pos);
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::Remove(const T& key) {
  typename IndexMap::iterator i = index_map_.find(&key);
  if (i == index_map_.end()) {
    return;
  }

  size_t removed_pos = i->second;
  SwapElements(removed_pos, queue_.size() - 1);

  const T* removed_key = queue_.back().first;
  queue_.pop_back();
  index_map_.erase(i);
  delete removed_key;

  if (!Empty() && removed_pos < queue_.size()) {
    Rebalance(removed_pos);
  }
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::Rebalance(size_t pos) {
  CHECK_LT(pos, queue_.size());

  size_t parent_pos = (pos >> 1);

  if (pos != 0 && queue_[parent_pos].second < queue_[pos].second) {
    PushUp(pos);
  } else {
    PushDown(pos);
  }
}

template <typename T, typename Hash, typename Equal>
const std::pair<const T*, int64>& PriorityQueue<T, Hash, Equal>::Top() const {
  CHECK(!Empty());
  return queue_.front();
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::Pop() {
  if (!Empty()) {
    SwapElements(0, queue_.size() - 1);
    const T* removed_key = queue_.back().first;
    queue_.pop_back();
    size_t num_deleted = index_map_.erase(removed_key);
    CHECK_EQ(num_deleted, 1);
    delete removed_key;
    PushDown(0);
  }
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::SwapElements(size_t a_idx, size_t b_idx) {
  if (a_idx != b_idx) {  
    const T* a_key = queue_[a_idx].first;
    const T* b_key = queue_[b_idx].first;
    std::swap(index_map_[a_key], index_map_[b_key]);
    std::swap(queue_[a_idx], queue_[b_idx]);
  }
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::PushDown(size_t pos) {
  while (pos * 2 < queue_.size()) {
    size_t child = pos * 2;
    if (child + 1 < queue_.size() &&
        queue_[child].second < queue_[child + 1].second) {
      ++child;
    }
    if (queue_[pos].second < queue_[child].second) {
      SwapElements(pos, child);
      pos = child;
    } else {
      break;
    }
  }
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::PushUp(size_t pos) {
  while (pos != 0 && pos < queue_.size()) {
    size_t parent = (pos >> 1);
    if (queue_[parent].second < queue_[pos].second) {
      SwapElements(pos, parent);
      pos = parent;
    } else {
      break;
    }
  }
}

template <typename T, typename Hash, typename Equal>
void PriorityQueue<T, Hash, Equal>::SanityCheckForTesting() const {
  CHECK_EQ(queue_.size(), index_map_.size());

  for (size_t queue_pos = 0; queue_pos < queue_.size(); ++queue_pos) {
    const T* key = queue_[queue_pos].first;
    typename IndexMap::const_iterator i = index_map_.find(key);
    CHECK(i != index_map_.end());
    size_t indexed_pos = i->second;
    CHECK_EQ(indexed_pos, queue_pos);

    if (queue_pos > 0) {
      size_t parent_pos = (queue_pos >> 1);
      CHECK_LE(queue_[queue_pos].second, queue_[parent_pos].second);
    }
  }
}

}  

#endif