use crate::core::search::disi_wrapper::DisiWrapper;
use crate::core::search::scorer::Scorer;
use crate::core::util::error::lucene_error::{LuceneError, Result};
#[derive(Default)] pub struct DisiPriorityQueue {
size: usize,
pub(crate) heap: Box<[usize]>,
}
impl DisiPriorityQueue {
pub fn new(max_size: usize) -> Self {
Self {
size: 0,
heap: vec![0; max_size].into_boxed_slice(),
}
}
pub(crate) fn left_node(node: usize) -> usize {
((node + 1) << 1) - 1
}
pub(crate) fn right_node(node: usize) -> usize {
node + 1
}
pub(crate) fn parent_node(node: usize) -> Option<usize> {
if node == 0 {
None
} else {
Some((node - 1) >> 1)
}
}
pub fn size(&self) -> usize {
self.size
}
pub fn top(&self) -> Option<usize> {
if self.size == 0 {
None
} else {
Some(self.heap[0])
}
}
pub fn top2<S>(&self, wrappers: &[DisiWrapper<S>]) -> Option<usize>
where
S: Scorer,
{
match self.size() {
0 | 1 => None,
2 => Some(self.heap[1]),
_ => {
let left = self.heap[1];
let right = self.heap[2];
if wrappers[left].doc <= wrappers[right].doc {
Some(left)
} else {
Some(right)
}
},
}
}
pub fn top_list_root<S>(&self, wrappers: &mut [DisiWrapper<S>]) -> usize
where
S: Scorer,
{
let heap = &self.heap;
let mut list_index = heap[0];
wrappers[list_index].next = None;
if self.size >= 3 {
list_index = self.top_list(list_index, heap, wrappers, self.size, 1);
list_index = self.top_list(list_index, heap, wrappers, self.size, 2);
} else if self.size == 2 {
let child = heap[1];
if wrappers[child].doc == wrappers[list_index].doc {
list_index = self.prepend(child, list_index, wrappers);
}
}
list_index
}
fn prepend<S>(&self, w1_index: usize, w2_index: usize, wrappers: &mut [DisiWrapper<S>]) -> usize
where
S: Scorer,
{
wrappers[w1_index].next = Some(w2_index);
w1_index
}
pub fn top_list<S>(
&self,
mut list: usize,
heap: &[usize],
wrappers: &mut [DisiWrapper<S>],
size: usize,
i: usize,
) -> usize
where
S: Scorer,
{
let w_index = heap[i];
if wrappers[w_index].doc == wrappers[list].doc {
list = self.prepend(w_index, list, wrappers);
let left = Self::left_node(i);
let right = left + 1;
if right < size {
list = self.top_list(list, heap, wrappers, size, left);
list = self.top_list(list, heap, wrappers, size, right);
} else if left < size {
let left_index = heap[left];
if wrappers[left_index].doc == wrappers[list].doc {
list = self.prepend(left_index, list, wrappers);
}
}
}
list
}
pub fn add<S>(&mut self, entry: usize, wrappers: &[DisiWrapper<S>]) -> usize
where
S: Scorer,
{
self.heap[self.size] = entry;
self.up_heap(self.size, wrappers);
self.size += 1;
self.heap[0]
}
pub fn add_all<S>(
&mut self,
entries: &[usize],
offset: usize,
len: usize,
wrappers: &[DisiWrapper<S>],
) -> Result<()>
where
S: Scorer,
{
if len == 0 {
return Ok(());
}
let new_size = self.size.checked_add(len).ok_or_else(|| {
LuceneError::array_index_out_of_bounds(format!(
"Cannot add {} elements to a queue with remaining capacity {}",
len,
self.heap.len().saturating_sub(self.size)
))
})?;
if new_size > self.heap.len() {
return Err(LuceneError::array_index_out_of_bounds(format!(
"Cannot add {} elements to a queue with remaining capacity {}",
len,
self.heap.len().saturating_sub(self.size)
)));
}
let end = offset.checked_add(len).ok_or_else(|| {
LuceneError::array_index_out_of_bounds(format!(
"offset + len overflow: offset={offset}, len={len}"
))
})?;
if end > entries.len() {
return Err(LuceneError::array_index_out_of_bounds(format!(
"index out of bounds: offset={offset}, len={len}, entries.len()={}",
entries.len()
)));
}
for (idx, entry) in entries[offset..end].iter().enumerate() {
self.heap[self.size + idx] = *entry;
}
self.size = new_size;
let first_leaf_index = self.size >> 1;
for root_index in (0..first_leaf_index).rev() {
let mut parent_index = root_index;
let parent = self.heap[parent_index];
let parent_doc = wrappers[parent].doc;
while parent_index < first_leaf_index {
let mut child_index = Self::left_node(parent_index);
let right_child_index = Self::right_node(child_index);
let mut child = self.heap[child_index];
if right_child_index < self.size {
let right_child = self.heap[right_child_index];
if wrappers[right_child].doc < wrappers[child].doc {
child = right_child;
child_index = right_child_index;
}
}
if wrappers[child].doc >= parent_doc {
break;
}
self.heap[parent_index] = child;
parent_index = child_index;
}
self.heap[parent_index] = parent;
}
Ok(())
}
pub fn pop<S>(&mut self, wrappers: &[DisiWrapper<S>]) -> usize
where
S: Scorer,
{
let result = match self.top() {
Some(top) => top,
None => return 0,
};
self.size -= 1;
let i = self.size;
self.heap[0] = self.heap[i];
self.heap[i] = 0;
self.down_heap(i, wrappers);
result
}
pub fn update_top<S>(&mut self, wrappers: &[DisiWrapper<S>]) -> usize
where
S: Scorer,
{
self.down_heap(self.size, wrappers);
self.heap[0]
}
pub(crate) fn update_top_with<S>(
&mut self,
top_replacement: usize,
wrappers: &[DisiWrapper<S>],
) -> usize
where
S: Scorer,
{
self.heap[0] = top_replacement;
self.update_top(wrappers)
}
pub fn clear(&mut self) {
for v in self.heap.iter_mut() {
*v = 0;
}
self.size = 0;
}
pub(crate) fn up_heap<S>(&mut self, mut i: usize, wrappers: &[DisiWrapper<S>])
where
S: Scorer,
{
let node_index = self.heap[i];
let node_doc = wrappers[node_index].doc;
while let Some(j) = Self::parent_node(i) {
if node_doc >= wrappers[self.heap[j]].doc {
break;
}
self.heap[i] = self.heap[j];
i = j;
}
self.heap[i] = node_index;
}
pub fn down_heap<S>(&mut self, size: usize, wrappers: &[DisiWrapper<S>])
where
S: Scorer,
{
if size == 0 {
return;
}
let mut i = 0;
let node = self.heap[0];
let mut j = Self::left_node(i);
if j < size {
let mut k = Self::right_node(j);
if k < size && wrappers[self.heap[k]].doc < wrappers[self.heap[j]].doc {
j = k;
}
if wrappers[self.heap[j]].doc < wrappers[node].doc {
loop {
self.heap[i] = self.heap[j];
i = j;
j = Self::left_node(i);
k = Self::right_node(j);
if k < size && wrappers[self.heap[k]].doc < wrappers[self.heap[j]].doc {
j = k;
}
if j >= size || wrappers[self.heap[j]].doc >= wrappers[node].doc {
break;
}
}
self.heap[i] = node;
}
}
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.heap[..self.size].iter().cloned()
}
}