1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include <vector>
#include <functional>
#include <algorithm>
#include "left_right_heap.h"
namespace vespalib {
/**
* A priority queue that orders its elements according to the less
* operator by default. The front element may be modified in place. If
* the front element is modified, the adjust function must be called
* afterward to restore priority order. The priority ordering can be
* specified with a second template parameter. The any and pop_any
* functions can be used to access and remove the element that is
* cheapest to remove. Note that if you change the any element, you
* must pop it afterward. Alternative heap implementations can be
* specified with a third template parameter. Only left heaps are
* supported. Please refer to the left-right heap benchmarks to figure
* out what implementation fits your case best.
**/
template <typename T, typename C = std::less<T>, typename H = LeftHeap>
class PriorityQueue
{
private:
C _cmp;
std::vector<T> _data;
public:
PriorityQueue() : _cmp(), _data() { H::require_left_heap(); }
PriorityQueue(C cmp) : _cmp(cmp), _data() { H::require_left_heap(); }
bool empty() const { return _data.empty(); }
size_t size() const { return _data.size(); }
void push(const T &item) {
_data.push_back(item);
H::template push<T, C>(&_data[0], &_data[size()], _cmp);
}
void push(T &&item) {
_data.push_back(std::move(item));
H::template push<T, C>(&_data[0], &_data[size()], _cmp);
}
T &front() {
return H::template front<T>(&_data[0], &_data[size()]);
}
void adjust() {
H::template adjust<T,C>(&_data[0], &_data[size()], _cmp);
}
void pop_front() {
H::template pop<T, C>(&_data[0], &_data[size()], _cmp);
_data.pop_back();
}
T &any() { return _data.back(); }
void pop_any() { _data.pop_back(); }
void reserve(size_t sz) { _data.reserve(sz); }
};
} // namespace vespalib
|
