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