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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::error::lucene_error::{LuceneError, Result};
/// A min heap that stores `i64` values.
/// This is a primitive priority queue that maintains a partial ordering of
/// elements such that the smallest element can always be found in constant
/// time.
///
/// `push()` and `pop()` require O(log(n)) time complexity.
/// This heap supports both unbounded growth (via `push()`) and bounded-size
/// insertion (via `insert_with_overflow()`).
///
/// The heap is 1-based internally: index 0 is unused.
pub struct LongHeap {
max_size: usize,
heap: Vec<i64>,
size: usize,
}
impl LongHeap {
/// Create an empty priority queue of the configured initial size.
///
/// # Arguments
///
/// * `max_size` - The maximum size of the heap. Must be > 0 and <
/// ArrayUtil::MAX_ARRAY_LENGTH.
///
/// # Errors
///
/// Returns `Err` if `max_size` is invalid to prevent confusing
/// out-of-memory errors.
pub fn new(max_size: usize) -> Result<Self> {
if !(1..ArrayUtil::MAX_ARRAY_LENGTH).contains(&max_size) {
return Err(LuceneError::illegal_argument(format!(
"max_size must be > 0 and < {}; got: {max_size}",
ArrayUtil::MAX_ARRAY_LENGTH
)));
}
// We add +1 because index 0 is unused.
let heap_size = max_size + 1;
let heap = vec![0i64; heap_size];
Ok(Self {
max_size,
heap,
size: 0,
})
}
/// Adds a value in O(log(n)) time. Grows unbounded as needed to accommodate
/// new values. Returns the new top element.
pub fn push(&mut self, element: i64) -> Result<i64> {
self.size += 1;
if self.size == self.heap.len() {
let new_capacity = (self.size * 3).div_ceil(2);
debug_assert!(new_capacity <= i32::MAX as usize);
ArrayUtil::grow_with(&mut self.heap, new_capacity, || 0)?;
}
self.heap[self.size] = element;
self.up_heap(self.size)?;
Ok(self.heap[1])
}
/// Adds a value in O(log(n)) time. If the number of values would exceed
/// `max_size`, the least value is discarded.
///
/// Returns whether the value was added.
pub fn insert_with_overflow(&mut self, value: i64) -> Result<bool> {
if self.size >= self.max_size {
if value < self.heap[1] {
return Ok(false);
}
self.update_top(value);
return Ok(true);
}
self.push(value)?;
Ok(true)
}
/// Returns the least element of the heap in constant time.
/// The caller must ensure the heap is not empty.
pub fn top(&self) -> i64 {
self.heap[1]
}
/// Removes and returns the least element of the heap in O(log(n)) time.
///
/// # Errors
///
/// Returns error if the heap is empty.
pub fn pop(&mut self) -> Result<i64> {
if self.size > 0 {
let result = self.heap[1];
self.heap[1] = self.heap[self.size];
self.size -= 1;
self.down_heap(1);
Ok(result)
} else {
Err(LuceneError::illegal_state("The heap is empty"))
}
}
/// Replaces the top of the heap with `new_top`.
/// This is faster than calling `pop()` followed by `push()`.
/// Does not add an element if the heap is empty.
pub fn update_top(&mut self, value: i64) -> i64 {
self.heap[1] = value;
self.down_heap(1);
self.heap[1]
}
/// Returns the number of elements currently stored in the heap.
pub fn size(&self) -> usize {
self.size
}
/// Removes all entries from the heap.
pub fn clear(&mut self) {
self.size = 0;
}
fn up_heap(&mut self, i: usize) -> Result<()> {
let (mut slot, mut parents) = self
.heap
.get_mut(..=i)
.and_then(|heap| heap.split_last_mut())
.ok_or_else(|| LuceneError::illegal_state("Heap slot is out of bounds"))?;
let value = *slot; // save bottom value
while parents.len() > 1 {
let parent_index = parents.len() >> 1;
let (head, tail) = parents.split_at_mut(parent_index);
let parent = &mut tail[0];
if value >= *parent {
break;
}
*slot = *parent; // shift parent down
slot = parent;
parents = head;
}
*slot = value;
Ok(())
}
fn down_heap(&mut self, mut i: usize) {
let value = self.heap[i];
let mut j = i << 1;
let mut k = j + 1;
j += usize::from(k <= self.size && self.heap[k] < self.heap[j]);
while j <= self.size && self.heap[j] < value {
self.heap[i] = self.heap[j];
i = j;
j = i << 1;
k = j + 1;
j += usize::from(k <= self.size && self.heap[k] < self.heap[j]);
}
self.heap[i] = value;
}
/// Pushes all elements from another heap into this heap.
pub fn push_all(&mut self, other: &LongHeap) -> Result<()> {
for i in 1..=other.size {
self.push(other.heap[i])?;
}
Ok(())
}
/// Returns the element at the ith location in the heap array.
/// Valid indices are in [1, size].
pub fn get(&self, i: usize) -> i64 {
self.heap[i]
}
/// Returns the internal heap array.
#[cfg(test)]
pub fn get_heap_array(&self) -> &[i64] {
&self.heap
}
}