LLVM: include/llvm/ADT/PriorityQueue.h Source File (original) (raw)
Go to the documentation of this file.
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifndef LLVM_ADT_PRIORITYQUEUE_H
15#define LLVM_ADT_PRIORITYQUEUE_H
16
17#include
18#include
19
20namespace llvm {
21
22
23
24
25template<class T,
26 class Sequence = std::vector,
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
37 const Compare &compare = Compare(),
38 const Sequence &sequence = Sequence())
39 : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
40 {}
41
42
43
44
45
46
48
49 typename Sequence::size_type i = find(this->c, t) - this->c.begin();
50
51
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
59
60 this->pop();
61 }
62
63
64
65
66
67
68
69
71 std::make_heap(this->c.begin(), this->c.end(), this->comp);
72 }
73
74
75
79};
80
81}
82
83#endif
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...
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.