use crate::core::util::priority_queue::{Compare, PriorityQueue};
use crate::core::util::ToInt;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::iterator::IteratorExt;
pub struct MergedIterator<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
current: Option<E::Item>,
queue: PriorityQueue<usize, TermMergeQueueCmp<E>>,
top: smallvec::SmallVec<[usize; 4]>,
remove_duplicates: bool,
num_top: usize,
}
impl<E> MergedIterator<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
pub fn new<I>(iterators: I) -> Result<Self>
where
I: IntoIterator<Item = E>,
{
Self::with_remove_duplicates(true, iterators)
}
pub fn with_remove_duplicates<I>(remove_duplicates: bool, iterators: I) -> Result<Self>
where
I: IntoIterator<Item = E>,
{
let iterators = iterators.into_iter().collect::<Vec<_>>();
let len = iterators.len();
let mut sub_iterators = Vec::with_capacity(len);
for (index, mut it) in iterators.into_iter().enumerate() {
if it.has_next()? {
let current = it
.next()?
.ok_or_else(|| LuceneError::illegal_state("has no next"))?;
sub_iterators.push(SubIterator {
iterator: it,
current: Some(current),
index,
});
}
}
let sub_iterator_len = sub_iterators.len();
let cmp = TermMergeQueueCmp {
sub_iterator: sub_iterators,
};
let queue_size = if len < i32::MAX as usize {
sub_iterator_len
} else {
len
};
let mut queue = PriorityQueue::new(queue_size, cmp)?;
for i in 0..sub_iterator_len {
queue.add(i)?;
}
let top_len = if remove_duplicates {
sub_iterator_len
} else {
sub_iterator_len.min(1)
};
Ok(Self {
current: None,
queue,
top: smallvec::smallvec![0; top_len],
remove_duplicates,
num_top: 0,
})
}
fn pull_top(&mut self) -> Result<()> {
debug_assert!(self.num_top == 0);
let first = self
.queue
.pop()?
.ok_or_else(|| LuceneError::illegal_state("queue is empty"))?;
self.top[self.num_top] = first;
self.num_top += 1;
if self.remove_duplicates {
while self.queue.size() > 0 {
let top_idx = *self
.queue
.top()
.ok_or_else(|| LuceneError::number_format("queue is empty"))?;
let first_idx = self.top[0];
if self.queue.compare.sub_iterator[top_idx].current
== self.queue.compare.sub_iterator[first_idx].current
{
let idx = self
.queue
.pop()?
.ok_or_else(|| LuceneError::number_format("queue is empty"))?;
self.top[self.num_top] = idx;
self.num_top += 1;
} else {
break;
}
}
}
let first_idx = self.top[0];
self.current = self.queue.compare.sub_iterator[first_idx].current.take();
Ok(())
}
fn push_top(&mut self) -> Result<()> {
for i in 0..self.num_top {
let idx = self.top[i];
let top = &mut self.queue.compare.sub_iterator[idx];
if top.iterator.has_next()? {
top.current = top.iterator.next()?;
self.queue.add(idx)?;
} else {
top.current = None;
}
}
self.num_top = 0;
Ok(())
}
}
impl<E> IteratorExt for MergedIterator<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
type Item = E::Item;
fn next(&mut self) -> Result<Option<Self::Item>> {
self.push_top()?;
if self.queue.size() > 0 {
self.pull_top()?;
} else {
self.current = None;
}
match self.current.take() {
None => Err(LuceneError::no_such_element("no such element")),
Some(current) => Ok(Some(current)),
}
}
fn has_next(&self) -> Result<bool> {
if self.queue.size() > 0 {
return Ok(true);
}
for i in 0..self.num_top {
let idx = self.top[i];
if self.queue.compare.sub_iterator[idx].iterator.has_next()? {
return Ok(true);
}
}
Ok(false)
}
}
pub struct TermMergeQueueCmp<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
sub_iterator: Vec<SubIterator<E>>,
}
impl<E> Compare<usize> for TermMergeQueueCmp<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
fn less_than(&self, a: &usize, b: &usize) -> Result<bool> {
let cmp = self.sub_iterator[*a]
.current
.cmp(&self.sub_iterator[*b].current)
.to_int();
if cmp != 0 {
Ok(cmp < 0)
} else {
Ok(self.sub_iterator[*a].index < self.sub_iterator[*b].index)
}
}
}
pub struct SubIterator<E>
where
E: IteratorExt,
E::Item: Ord + Clone,
{
iterator: E,
current: Option<E::Item>,
index: usize,
}