blob: b7fc9cfab0584c193aa392aa678db343572e9a64 (
plain) (
blame)
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
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include "posting_priority_queue.h"
namespace search {
template <class Reader>
void
PostingPriorityQueue<Reader>::adjust()
{
if (!_vec.front().get()->isValid()) {
_vec.erase(_vec.begin()); // Iterator no longer valid
return;
}
if (_vec.size() == 1) { // Only one iterator left
return;
}
// Peform binary search to find first element higher than changed value
auto gt = std::upper_bound(_vec.begin() + 1, _vec.end(), _vec.front());
auto to = _vec.begin();
auto from = to;
++from;
Ref changed = *to; // Remember changed value
while (from != gt) { // Shift elements to make space for changed value
*to = *from;
++from;
++to;
}
*to = changed; // Save changed value at right location
}
template <class Reader>
void
PostingPriorityQueue<Reader>::setup(uint32_t heap_limit)
{
_heap_limit = heap_limit;
for (auto ref : _vec) {
assert(ref.get()->isValid());
}
if (_vec.size() >= heap_limit) {
std::sort(_vec.begin(), _vec.end());
}
}
}
|
