1193323Sed//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the PriorityQueue class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14249423Sdim#ifndef LLVM_ADT_PRIORITYQUEUE_H 15249423Sdim#define LLVM_ADT_PRIORITYQUEUE_H 16193323Sed 17199481Srdivacky#include <algorithm> 18193323Sed#include <queue> 19193323Sed 20193323Sednamespace llvm { 21193323Sed 22193323Sed/// PriorityQueue - This class behaves like std::priority_queue and 23193323Sed/// provides a few additional convenience functions. 24193323Sed/// 25193323Sedtemplate<class T, 26193323Sed class Sequence = std::vector<T>, 27193323Sed class Compare = std::less<typename Sequence::value_type> > 28193323Sedclass PriorityQueue : public std::priority_queue<T, Sequence, Compare> { 29193323Sedpublic: 30193323Sed explicit PriorityQueue(const Compare &compare = Compare(), 31193323Sed const Sequence &sequence = Sequence()) 32193323Sed : std::priority_queue<T, Sequence, Compare>(compare, sequence) 33193323Sed {} 34193323Sed 35193323Sed template<class Iterator> 36193323Sed PriorityQueue(Iterator begin, Iterator end, 37193323Sed const Compare &compare = Compare(), 38193323Sed const Sequence &sequence = Sequence()) 39193323Sed : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) 40193323Sed {} 41193323Sed 42193323Sed /// erase_one - Erase one element from the queue, regardless of its 43193323Sed /// position. This operation performs a linear search to find an element 44193323Sed /// equal to t, but then uses all logarithmic-time algorithms to do 45193323Sed /// the erase operation. 46193323Sed /// 47193323Sed void erase_one(const T &t) { 48193323Sed // Linear-search to find the element. 49193323Sed typename Sequence::size_type i = 50193323Sed std::find(this->c.begin(), this->c.end(), t) - this->c.begin(); 51193323Sed 52193323Sed // Logarithmic-time heap bubble-up. 53193323Sed while (i != 0) { 54193323Sed typename Sequence::size_type parent = (i - 1) / 2; 55193323Sed this->c[i] = this->c[parent]; 56193323Sed i = parent; 57193323Sed } 58193323Sed 59193323Sed // The element we want to remove is now at the root, so we can use 60193323Sed // priority_queue's plain pop to remove it. 61193323Sed this->pop(); 62193323Sed } 63193323Sed 64193323Sed /// reheapify - If an element in the queue has changed in a way that 65193323Sed /// affects its standing in the comparison function, the queue's 66193323Sed /// internal state becomes invalid. Calling reheapify() resets the 67193323Sed /// queue's state, making it valid again. This operation has time 68193323Sed /// complexity proportional to the number of elements in the queue, 69193323Sed /// so don't plan to use it a lot. 70193323Sed /// 71193323Sed void reheapify() { 72193323Sed std::make_heap(this->c.begin(), this->c.end(), this->comp); 73193323Sed } 74193323Sed 75193323Sed /// clear - Erase all elements from the queue. 76193323Sed /// 77193323Sed void clear() { 78193323Sed this->c.clear(); 79193323Sed } 80193323Sed}; 81193323Sed 82193323Sed} // End llvm namespace 83193323Sed 84193323Sed#endif 85