1//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the PriorityQueue class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_PRIORITYQUEUE_H
14#define LLVM_ADT_PRIORITYQUEUE_H
15
16#include <algorithm>
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 = find(this->c, t) - this->c.begin();
49
50 // Logarithmic-time heap bubble-up.
51 while (i != 0) {
52 typename Sequence::size_type parent = (i - 1) / 2;
53 this->c[i] = this->c[parent];
54 i = parent;
55 }
56
57 // The element we want to remove is now at the root, so we can use
58 // priority_queue's plain pop to remove it.
59 this->pop();
60 }
61
62 /// reheapify - If an element in the queue has changed in a way that
63 /// affects its standing in the comparison function, the queue's
64 /// internal state becomes invalid. Calling reheapify() resets the
65 /// queue's state, making it valid again. This operation has time
66 /// complexity proportional to the number of elements in the queue,
67 /// so don't plan to use it a lot.
68 ///
69 void reheapify() {
70 std::make_heap(this->c.begin(), this->c.end(), this->comp);
71 }
72
73 /// clear - Erase all elements from the queue.
74 ///
75 void clear() {
76 this->c.clear();
77 }
78};
79
80} // End llvm namespace
81
82#endif
83