use std::borrow::Borrow;
use std::sync::Arc;
use crate::core::search::doc_id_set_iterator::NO_MORE_DOCS;
use crate::core::util::SliceCopyOps;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::hnsw::neighbor_array::NeighborArray;
pub trait HnswGraph {
const HAS_BORROWED_NEIGHBORS: bool = false;
fn seek(&mut self, level: usize, target: usize) -> Result<()>;
fn size(&self) -> usize;
fn max_node_id(&self) -> Option<usize> {
Some(self.size() - 1)
}
fn next_neighbor(&mut self) -> Result<usize>;
fn borrow_neighbors(&mut self) -> Result<(&NeighborArray<true>, &mut usize)> {
Err(LuceneError::unsupported_operation(
"exclusive neighbor borrowing is unavailable",
))
}
fn num_levels(&self) -> Result<usize>;
fn entry_node(&self) -> Result<Option<usize>>;
type NodeIterator: NodesIterator;
fn get_nodes_on_level(&mut self, level: usize) -> Result<Self::NodeIterator>;
fn with_neighbors<T, F>(&self, _level: usize, _node: usize, _action: F) -> Result<T>
where
F: FnOnce(&NeighborArray<true>) -> Result<T>,
{
Err(LuceneError::unsupported_operation(""))
}
}
impl<T> HnswGraph for Box<T>
where
T: HnswGraph + ?Sized,
{
const HAS_BORROWED_NEIGHBORS: bool = T::HAS_BORROWED_NEIGHBORS;
fn seek(&mut self, level: usize, target: usize) -> Result<()> {
(**self).seek(level, target)
}
fn size(&self) -> usize {
(**self).size()
}
fn max_node_id(&self) -> Option<usize> {
(**self).max_node_id()
}
fn next_neighbor(&mut self) -> Result<usize> {
(**self).next_neighbor()
}
#[inline]
fn borrow_neighbors(&mut self) -> Result<(&NeighborArray<true>, &mut usize)> {
(**self).borrow_neighbors()
}
fn num_levels(&self) -> Result<usize> {
(**self).num_levels()
}
fn entry_node(&self) -> Result<Option<usize>> {
(**self).entry_node()
}
type NodeIterator = T::NodeIterator;
fn get_nodes_on_level(&mut self, level: usize) -> Result<Self::NodeIterator> {
(**self).get_nodes_on_level(level)
}
fn with_neighbors<R, F>(&self, level: usize, node: usize, action: F) -> Result<R>
where
F: FnOnce(&NeighborArray<true>) -> Result<R>,
{
(**self).with_neighbors(level, node, action)
}
}
impl<T> HnswGraph for &mut T
where
T: HnswGraph + ?Sized,
{
const HAS_BORROWED_NEIGHBORS: bool = T::HAS_BORROWED_NEIGHBORS;
fn seek(&mut self, level: usize, target: usize) -> Result<()> {
(**self).seek(level, target)
}
fn size(&self) -> usize {
(**self).size()
}
fn max_node_id(&self) -> Option<usize> {
(**self).max_node_id()
}
#[inline]
fn next_neighbor(&mut self) -> Result<usize> {
(**self).next_neighbor()
}
#[inline]
fn borrow_neighbors(&mut self) -> Result<(&NeighborArray<true>, &mut usize)> {
(**self).borrow_neighbors()
}
fn num_levels(&self) -> Result<usize> {
(**self).num_levels()
}
fn entry_node(&self) -> Result<Option<usize>> {
(**self).entry_node()
}
type NodeIterator = T::NodeIterator;
fn get_nodes_on_level(&mut self, level: usize) -> Result<Self::NodeIterator> {
(**self).get_nodes_on_level(level)
}
fn with_neighbors<R, F>(&self, level: usize, node: usize, action: F) -> Result<R>
where
F: FnOnce(&NeighborArray<true>) -> Result<R>,
{
(**self).with_neighbors(level, node, action)
}
}
pub struct EmptyHnswGraph;
impl HnswGraph for EmptyHnswGraph {
fn seek(&mut self, _level: usize, _target: usize) -> Result<()> {
Ok(())
}
fn size(&self) -> usize {
0
}
fn next_neighbor(&mut self) -> Result<usize> {
Ok(NO_MORE_DOCS as usize)
}
fn num_levels(&self) -> Result<usize> {
Ok(0)
}
fn entry_node(&self) -> Result<Option<usize>> {
Ok(Some(0))
}
type NodeIterator = ArrayNodesIterator;
fn get_nodes_on_level(&mut self, _level: usize) -> Result<Self::NodeIterator> {
Ok(ArrayNodesIterator::empty())
}
}
pub trait NodesIterator: Iterator<Item = usize> {
fn size(&self) -> usize;
fn consume(&mut self, dest: &mut [usize]) -> Result<usize>;
fn has_next(&self) -> bool;
}
macro_rules! define_nodes_iterator_enum {
(
$enum_name:ident,
[$($V:ident),+ $(,)?]
) => {
pub enum $enum_name<$($V),+> {
$($V($V)),+
}
impl<$($V),+> Iterator for $enum_name<$($V),+>
where
$($V: Iterator<Item = usize>,)+
{
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
match self {
$(Self::$V(iter) => iter.next(),)+
}
}
}
impl<$($V),+> NodesIterator for $enum_name<$($V),+>
where
$($V: NodesIterator,)+
{
fn size(&self) -> usize {
match self {
$(Self::$V(iter) => iter.size(),)+
}
}
fn consume(&mut self, dest: &mut [usize]) -> Result<usize> {
match self {
$(Self::$V(iter) => iter.consume(dest),)+
}
}
fn has_next(&self) -> bool {
match self {
$(Self::$V(iter) => iter.has_next(),)+
}
}
}
};
}
define_nodes_iterator_enum!(NodesIteratorEnum2, [A, B]);
pub fn get_sorted_nodes<I>(nodes: &mut I) -> Vec<usize>
where
I: NodesIterator,
{
let mut sorted = Vec::with_capacity(nodes.size());
for v in nodes.by_ref() {
sorted.push(v);
}
sorted.sort_unstable();
sorted
}
pub struct ArrayNodesIterator<N = Arc<Vec<usize>>> {
nodes: Option<N>,
cur: usize,
size: usize,
}
impl<N: Borrow<Vec<usize>>> ArrayNodesIterator<N> {
pub fn from_nodes(nodes: Option<N>, size: usize) -> Self {
debug_assert!(
nodes
.as_ref()
.is_some_and(|nodes| size <= <N as Borrow<Vec<usize>>>::borrow(nodes).len())
);
Self {
nodes,
cur: 0,
size,
}
}
pub fn from_size(size: usize) -> Self {
Self {
nodes: None,
cur: 0,
size,
}
}
pub fn empty() -> Self {
Self::from_size(0)
}
}
impl<N: Borrow<Vec<usize>>> Iterator for ArrayNodesIterator<N> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
if !self.has_next() {
None
} else {
let value = match &self.nodes {
Some(vec) => <N as Borrow<Vec<usize>>>::borrow(vec)[self.cur],
None => self.cur,
};
self.cur += 1;
Some(value)
}
}
}
impl<N: Borrow<Vec<usize>>> NodesIterator for ArrayNodesIterator<N> {
fn size(&self) -> usize {
self.size
}
fn consume(&mut self, dest: &mut [usize]) -> Result<usize> {
if !self.has_next() {
return Err(LuceneError::no_such_element(""));
}
let num_to_copy = std::cmp::min(dest.len(), self.size - self.cur);
match &self.nodes {
Some(vec) => {
let vec: &Vec<usize> = vec.borrow();
dest.copy_from(&vec[self.cur..self.cur + num_to_copy], 0);
self.cur += num_to_copy;
Ok(num_to_copy)
},
None => {
for (i, slot) in dest.iter_mut().enumerate().take(num_to_copy) {
*slot = self.cur + i;
}
Ok(num_to_copy)
},
}
}
fn has_next(&self) -> bool {
self.cur < self.size
}
}
pub struct CollectionNodesIterator {
nodes: Arc<Option<Vec<usize>>>,
index: usize,
size: usize,
}
impl CollectionNodesIterator {
pub fn new(nodes: Arc<Option<Vec<usize>>>) -> Self {
let size = nodes.as_ref().as_ref().map_or(0, |v| v.len());
Self {
nodes,
index: 0,
size,
}
}
}
impl Iterator for CollectionNodesIterator {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
if self.size == 0 {
return None;
}
let vec = self.nodes.as_ref().as_ref()?;
if self.index < vec.len() {
let val = vec[self.index];
self.index += 1;
Some(val)
} else {
None
}
}
}
impl NodesIterator for CollectionNodesIterator {
fn size(&self) -> usize {
self.size
}
fn consume(&mut self, dest: &mut [usize]) -> Result<usize> {
if !self.has_next() {
return Err(LuceneError::no_such_element(""));
}
let mut dest_index = 0;
while self.has_next() && dest_index < dest.len() {
dest[dest_index] = self
.next()
.ok_or_else(|| LuceneError::no_such_element(""))?;
dest_index += 1;
}
Ok(dest_index)
}
fn has_next(&self) -> bool {
self.index < self.size
}
}