13627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// 23627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// 33627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// The LLVM Compiler Infrastructure 43627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// 53627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// This file is distributed under the University of Illinois Open Source 63627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// License. See LICENSE.TXT for details. 73627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// 83627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman//===----------------------------------------------------------------------===// 93627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// 103627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// This file defines the PriorityQueue class. 113627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman// 123627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman//===----------------------------------------------------------------------===// 133627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ADT_PRIORITYQUEUE_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ADT_PRIORITYQUEUE_H 163627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 170c8ae782cb966068f8317f8225633e2f4720ccb7Douglas Gregor#include <algorithm> 183627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman#include <queue> 193627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 203627e34486db088661bc7fb6c0dde6a18a543217Dan Gohmannamespace llvm { 213627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 223627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman/// PriorityQueue - This class behaves like std::priority_queue and 233627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman/// provides a few additional convenience functions. 243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// 253627e34486db088661bc7fb6c0dde6a18a543217Dan Gohmantemplate<class T, 263627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman class Sequence = std::vector<T>, 273627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman class Compare = std::less<typename Sequence::value_type> > 283627e34486db088661bc7fb6c0dde6a18a543217Dan Gohmanclass PriorityQueue : public std::priority_queue<T, Sequence, Compare> { 293627e34486db088661bc7fb6c0dde6a18a543217Dan Gohmanpublic: 303627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman explicit PriorityQueue(const Compare &compare = Compare(), 313627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman const Sequence &sequence = Sequence()) 323627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman : std::priority_queue<T, Sequence, Compare>(compare, sequence) 333627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman {} 343627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 353627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman template<class Iterator> 363627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman PriorityQueue(Iterator begin, Iterator end, 373627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman const Compare &compare = Compare(), 383627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman const Sequence &sequence = Sequence()) 393627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) 403627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman {} 413627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 423627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// erase_one - Erase one element from the queue, regardless of its 433627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// position. This operation performs a linear search to find an element 443627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// equal to t, but then uses all logarithmic-time algorithms to do 453627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// the erase operation. 463627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// 473627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman void erase_one(const T &t) { 483627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman // Linear-search to find the element. 493627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman typename Sequence::size_type i = 503627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman std::find(this->c.begin(), this->c.end(), t) - this->c.begin(); 513627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 523627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman // Logarithmic-time heap bubble-up. 533627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman while (i != 0) { 543627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman typename Sequence::size_type parent = (i - 1) / 2; 552904538fc30fbdc2788802ca7389482d5e20a717Dan Gohman this->c[i] = this->c[parent]; 563627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman i = parent; 573627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman } 583627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 593627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman // The element we want to remove is now at the root, so we can use 603627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman // priority_queue's plain pop to remove it. 613627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman this->pop(); 623627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman } 633627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 643627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// reheapify - If an element in the queue has changed in a way that 653627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// affects its standing in the comparison function, the queue's 663627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// internal state becomes invalid. Calling reheapify() resets the 673627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// queue's state, making it valid again. This operation has time 683627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// complexity proportional to the number of elements in the queue, 693627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// so don't plan to use it a lot. 703627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman /// 713627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman void reheapify() { 723627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman std::make_heap(this->c.begin(), this->c.end(), this->comp); 733627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman } 74caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman 75caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman /// clear - Erase all elements from the queue. 76caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman /// 77caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman void clear() { 78caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman this->c.clear(); 79caf746aa5a836bc3401049235c6d7d41c5921502Dan Gohman } 803627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman}; 813627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 823627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman} // End llvm namespace 833627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman 843627e34486db088661bc7fb6c0dde6a18a543217Dan Gohman#endif 85