PriorityQueue.h revision caf746aa5a836bc3401049235c6d7d41c5921502 
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_PRIORITY_QUEUE_H
15#define LLVM_ADT_PRIORITY_QUEUE_H
16
17#include <queue>
18
19namespace llvm {
20
21/// PriorityQueue - This class behaves like std::priority_queue and
22/// provides a few additional convenience functions.
23///
24template<class T,
25         class Sequence = std::vector<T>,
26         class Compare = std::less<typename Sequence::value_type> >
27class PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
28public:
29  explicit PriorityQueue(const Compare &compare = Compare(),
30                         const Sequence &sequence = Sequence())
31    : std::priority_queue<T, Sequence, Compare>(compare, sequence)
32  {}
33
34  template<class Iterator>
35  PriorityQueue(Iterator begin, Iterator end,
36                const Compare &compare = Compare(),
37                const Sequence &sequence = Sequence())
38    : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
39  {}
40
41  /// erase_one - Erase one element from the queue, regardless of its
42  /// position. This operation performs a linear search to find an element
43  /// equal to t, but then uses all logarithmic-time algorithms to do
44  /// the erase operation.
45  ///
46  void erase_one(const T &t) {
47    // Linear-search to find the element.
48    typename Sequence::size_type i =
49      std::find(this->c.begin(), this->c.end(), 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