1e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// 2e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 3e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// The LLVM Compiler Infrastructure 4e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 5e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// This file is distributed under the University of Illinois Open Source 6e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// License. See LICENSE.TXT for details. 7e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 8e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 9e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 10e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// This file defines the PriorityQueue class. 11e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao// 12e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao//===----------------------------------------------------------------------===// 13e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 14e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#ifndef LLVM_ADT_PRIORITY_QUEUE_H 15e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#define LLVM_ADT_PRIORITY_QUEUE_H 16e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 17e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <algorithm> 18e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#include <queue> 19e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 20e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaonamespace llvm { 21e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 22e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// PriorityQueue - This class behaves like std::priority_queue and 23e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// provides a few additional convenience functions. 24e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao/// 25e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaotemplate<class T, 26e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao class Sequence = std::vector<T>, 27e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao class Compare = std::less<typename Sequence::value_type> > 28e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaoclass PriorityQueue : public std::priority_queue<T, Sequence, Compare> { 29e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liaopublic: 30e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao explicit PriorityQueue(const Compare &compare = Compare(), 31e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const Sequence &sequence = Sequence()) 32e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao : std::priority_queue<T, Sequence, Compare>(compare, sequence) 33e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao {} 34e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 35e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao template<class Iterator> 36e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao PriorityQueue(Iterator begin, Iterator end, 37e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const Compare &compare = Compare(), 38e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao const Sequence &sequence = Sequence()) 39e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) 40e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao {} 41e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 42e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// erase_one - Erase one element from the queue, regardless of its 43e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// position. This operation performs a linear search to find an element 44e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// equal to t, but then uses all logarithmic-time algorithms to do 45e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// the erase operation. 46e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 47e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao void erase_one(const T &t) { 48e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Linear-search to find the element. 49e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typename Sequence::size_type i = 50e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao std::find(this->c.begin(), this->c.end(), t) - this->c.begin(); 51e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 52e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // Logarithmic-time heap bubble-up. 53e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao while (i != 0) { 54e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao typename Sequence::size_type parent = (i - 1) / 2; 55e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao this->c[i] = this->c[parent]; 56e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao i = parent; 57e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 58e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 59e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // The element we want to remove is now at the root, so we can use 60e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao // priority_queue's plain pop to remove it. 61e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao this->pop(); 62e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 63e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 64e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// reheapify - If an element in the queue has changed in a way that 65e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// affects its standing in the comparison function, the queue's 66e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// internal state becomes invalid. Calling reheapify() resets the 67e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// queue's state, making it valid again. This operation has time 68e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// complexity proportional to the number of elements in the queue, 69e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// so don't plan to use it a lot. 70e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 71e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao void reheapify() { 72e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao std::make_heap(this->c.begin(), this->c.end(), this->comp); 73e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 74e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 75e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// clear - Erase all elements from the queue. 76e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao /// 77e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao void clear() { 78e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao this->c.clear(); 79e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao } 80e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao}; 81e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 82e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao} // End llvm namespace 83e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao 84e264f62ca09a8f65c87a46d562a4d0f9ec5d457Shih-wei Liao#endif 85