LLVM 20.0.0git
PriorityQueue.h
Go to the documentation of this file.
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/// \file
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
20namespace llvm {
21
22/// PriorityQueue - This class behaves like std::priority_queue and
23/// provides a few additional convenience functions.
24///
25template<class T,
26 class Sequence = std::vector<T>,
27 class Compare = std::less<typename Sequence::value_type> >
28class PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
29public:
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
#define T
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:28
PriorityQueue(Iterator begin, Iterator end, const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:36
void clear()
clear - Erase all elements from the queue.
Definition: PriorityQueue.h:76
void reheapify()
reheapify - If an element in the queue has changed in a way that affects its standing in the comparis...
Definition: PriorityQueue.h:70
PriorityQueue(const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:30
void erase_one(const T &t)
erase_one - Erase one element from the queue, regardless of its position.
Definition: PriorityQueue.h:47
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858