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 = 50 std::find(this->c.begin(), this->c.end(), t) - this->c.begin(); 51 52 // Logarithmic-time heap bubble-up. 53 while (i != 0) { 54 typename Sequence::size_type parent = (i - 1) / 2; 55 this->c[i] = this->c[parent]; 56 i = parent; 57 } 58 59 // The element we want to remove is now at the root, so we can use 60 // priority_queue's plain pop to remove it. 61 this->pop(); 62 } 63 64 /// reheapify - If an element in the queue has changed in a way that 65 /// affects its standing in the comparison function, the queue's 66 /// internal state becomes invalid. Calling reheapify() resets the 67 /// queue's state, making it valid again. This operation has time 68 /// complexity proportional to the number of elements in the queue, 69 /// so don't plan to use it a lot. 70 /// 71 void reheapify() { 72 std::make_heap(this->c.begin(), this->c.end(), this->comp); 73 } 74 75 /// clear - Erase all elements from the queue. 76 /// 77 void clear() { 78 this->c.clear(); 79 } 80 }; 81 82 } // End llvm namespace 83 84 #endif 85
