use crate::dynamic_index::star_index::{BestNeighbour, NearestNeighbour};
use crate::dynamic_index::star_index_container::SIDX;
use crate::structs_generic::Flt;
use az::Az;
use kiddo_v6::kd_tree::{ArchivedKdTree as KiddoV6ArchivedKdTree, KdTree as KiddoV6KdTree};
use kiddo_v6::leaf_strategies::VecOfArenas as KiddoV6VecOfArenas;
use kiddo_v6::stem_strategies::{
DonnellyCyclicSimdFull as KiddoV6DonnellySimdFull, Eytzinger as KiddoV6Eytzinger,
};
use kiddo_v6::DonnellyUnrolled as KiddoV6Donnelly;
use kiddo_v6::ITEM_LEAF_MODE_SORTED;
use kiddo_v6::{Manhattan as KiddoV6Manhattan, SquaredEuclidean as KiddoV6SquaredEuclidean};
use rkyv_08::{rancor::Error as RkyvError, to_bytes, Archive, Deserialize, Serialize};
use rkyv_08::util::AlignedVec;
use std::any::Any;
use std::fmt::Debug;
use std::marker::PhantomData;
use std::num::NonZero;
#[derive(Debug, Clone, Copy)]
#[non_exhaustive]
pub enum DistanceMetric {
SquaredEuclidean,
Manhattan,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum FloatType {
Float32,
Float64,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum IndexType {
U16,
U32,
U64,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum KiddoV6StemStrategy {
EytzingerPf,
DonnellyScalar,
DonnellySimd,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum KiddoV6LeafStrategy {
VecOfArenas,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum KiddoV6ItemLeafMode {
Unsorted,
ItemSorted,
ItemSortedWithEmbeddedMinShift8,
}
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
#[rkyv(crate=rkyv_08)]
#[non_exhaustive]
pub enum KdTreeDescriptor {
KiddoV6 {
axis: FloatType,
index: IndexType,
bucket_size: u16,
stem_strategy: KiddoV6StemStrategy,
leaf_strategy: KiddoV6LeafStrategy,
item_leaf_mode: KiddoV6ItemLeafMode,
},
}
pub trait KdTree<const D: usize>: Send + Sync {
fn within_radius(
&self,
point: &[f64; D],
radius: f64,
metric: DistanceMetric,
) -> Vec<NearestNeighbour<f64, SIDX>>;
fn best_n_within_radius(
&self,
query: &[f64; D],
radius: f64,
max_qty: NonZero<usize>,
metric: DistanceMetric,
) -> Box<dyn Iterator<Item = BestNeighbour<f64, SIDX>>>;
fn as_any(&self) -> &dyn Any;
}
struct AlignedArchivedKdTree<T, const D: usize> {
bytes: AlignedVec<128>,
archived_type: PhantomData<T>,
}
impl<T, const D: usize> AlignedArchivedKdTree<T, D> {
fn new(raw: &[u8]) -> Self {
let mut bytes = AlignedVec::<128>::with_capacity(raw.len());
bytes.extend_from_slice(raw);
Self {
bytes,
archived_type: PhantomData,
}
}
fn archived(&self) -> &T
where
T: rkyv_08::Portable,
{
unsafe { rkyv_08::access_unchecked::<T>(&self.bytes) }
}
}
impl<T, const D: usize> KdTree<D> for AlignedArchivedKdTree<T, D>
where
T: rkyv_08::Portable + Send + Sync + 'static,
for<'a> &'a T: KdTree<D>,
{
fn within_radius(
&self,
point: &[f64; D],
radius: f64,
metric: DistanceMetric,
) -> Vec<NearestNeighbour<f64, SIDX>> {
KdTree::within_radius(&self.archived(), point, radius, metric)
}
fn best_n_within_radius(
&self,
query: &[f64; D],
radius: f64,
max_qty: NonZero<usize>,
metric: DistanceMetric,
) -> Box<dyn Iterator<Item = BestNeighbour<f64, SIDX>>> {
KdTree::best_n_within_radius(&self.archived(), query, radius, max_qty, metric)
}
fn as_any(&self) -> &dyn Any {
self
}
}
macro_rules! impl_kdtree_methods_v6 {
(f32, $dim:literal, $sq_metric:ty, $man_metric:ty) => {
fn within_radius(
&self,
point: &[f64; $dim],
radius: f64,
metric: DistanceMetric,
) -> Vec<NearestNeighbour<f64, SIDX>> {
let mut converted = [0.0f32; $dim];
for i in 0..$dim {
converted[i] = point[i] as f32;
}
match metric {
DistanceMetric::SquaredEuclidean => self
.query(&converted)
.within::<$sq_metric>(radius as f32)
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance as f64,
item: nn.item.az::<SIDX>(),
})
.collect(),
DistanceMetric::Manhattan => self
.query(&converted)
.within::<$man_metric>(radius as f32)
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance as f64,
item: nn.item.az::<SIDX>(),
})
.collect(),
}
}
fn best_n_within_radius(
&self,
query: &[f64; $dim],
radius: f64,
max_qty: NonZero<usize>,
metric: DistanceMetric,
) -> Box<dyn Iterator<Item = BestNeighbour<f64, SIDX>>> {
let mut converted = [0.0f32; $dim];
for i in 0..$dim {
converted[i] = query[i] as f32;
}
match metric {
DistanceMetric::SquaredEuclidean => Box::new(
self.query(&converted)
.best_n_within::<$sq_metric>(radius as f32, max_qty)
.execute()
.into_sorted_vec()
.into_iter()
.map(|bn| BestNeighbour {
distance: bn.distance as f64,
item: bn.item.az::<SIDX>(),
}),
),
DistanceMetric::Manhattan => Box::new(
self.query(&converted)
.best_n_within::<$man_metric>(radius as f32, max_qty)
.execute()
.into_sorted_vec()
.into_iter()
.map(|bn| BestNeighbour {
distance: bn.distance as f64,
item: bn.item.az::<SIDX>(),
}),
),
}
}
};
(f64, $dim:literal, $sq_metric:ty, $man_metric:ty) => {
fn within_radius(
&self,
point: &[f64; $dim],
radius: f64,
metric: DistanceMetric,
) -> Vec<NearestNeighbour<f64, SIDX>> {
match metric {
DistanceMetric::SquaredEuclidean => self
.query(point)
.within::<$sq_metric>(radius)
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance as f64,
item: nn.item.az::<SIDX>(),
})
.collect(),
DistanceMetric::Manhattan => self
.query(point)
.within::<$man_metric>(radius)
.execute()
.into_iter()
.map(|nn| NearestNeighbour {
distance: nn.distance as f64,
item: nn.item.az::<SIDX>(),
})
.collect(),
}
}
fn best_n_within_radius(
&self,
query: &[f64; $dim],
radius: f64,
max_qty: NonZero<usize>,
metric: DistanceMetric,
) -> Box<dyn Iterator<Item = BestNeighbour<f64, SIDX>>> {
match metric {
DistanceMetric::SquaredEuclidean => Box::new(
self.query(query)
.best_n_within::<$sq_metric>(radius, max_qty)
.execute()
.into_sorted_vec()
.into_iter()
.map(|bn| BestNeighbour {
distance: bn.distance as f64,
item: bn.item.az::<SIDX>(),
}),
),
DistanceMetric::Manhattan => Box::new(
self.query(query)
.best_n_within::<$man_metric>(radius, max_qty)
.execute()
.into_sorted_vec()
.into_iter()
.map(|bn| BestNeighbour {
distance: bn.distance as f64,
item: bn.item.az::<SIDX>(),
}),
),
}
}
};
}
macro_rules! impl_kdtree_v6_owned {
($tree_type:ident, $dim:literal, f32, $sq_metric:ty, $man_metric:ty) => {
impl KdTree<$dim> for $tree_type {
impl_kdtree_methods_v6!(f32, $dim, $sq_metric, $man_metric);
fn as_any(&self) -> &dyn Any {
self
}
}
};
($tree_type:ident, $dim:literal, f64, $sq_metric:ty, $man_metric:ty) => {
impl KdTree<$dim> for $tree_type {
impl_kdtree_methods_v6!(f64, $dim, $sq_metric, $man_metric);
fn as_any(&self) -> &dyn Any {
self
}
}
};
}
macro_rules! impl_kdtree_v6_ref {
($tree_type:ident, $dim:literal, f32, $sq_metric:ty, $man_metric:ty) => {
impl KdTree<$dim> for &$tree_type {
impl_kdtree_methods_v6!(f32, $dim, $sq_metric, $man_metric);
fn as_any(&self) -> &dyn Any {
*self
}
}
};
($tree_type:ident, $dim:literal, f64, $sq_metric:ty, $man_metric:ty) => {
impl KdTree<$dim> for &$tree_type {
impl_kdtree_methods_v6!(f64, $dim, $sq_metric, $man_metric);
fn as_any(&self) -> &dyn Any {
*self
}
}
};
}
type KiddoV6StarTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f32, u32, 3, 32>, 3, 32>;
type KiddoV6ItemSortedStarTreeF32 = KiddoV6KdTree<
f32,
u32,
KiddoV6Eytzinger,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6QuadTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type KiddoV6StarTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32>;
type KiddoV6ItemSortedStarTreeF64 = KiddoV6KdTree<
f64,
u32,
KiddoV6Eytzinger,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6QuadTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type KiddoV6DonnellyPfStarTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6Donnelly<4>, KiddoV6VecOfArenas<f32, u32, 3, 32>, 3, 32>;
type KiddoV6DonnellyPfItemSortedStarTreeF32 = KiddoV6KdTree<
f32,
u32,
KiddoV6Donnelly<4>,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6DonnellyPfQuadTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6Donnelly<4>, KiddoV6VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type KiddoV6DonnellyPfStarTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6Donnelly<3>, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32>;
type KiddoV6DonnellyPfItemSortedStarTreeF64 = KiddoV6KdTree<
f64,
u32,
KiddoV6Donnelly<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6DonnellyPfMinSummaryStarTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6Donnelly<3>, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32, 8>;
type KiddoV6DonnellyPfQuadTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6Donnelly<3>, KiddoV6VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type KiddoV6DonnellyBlockSimdStarTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6DonnellySimdFull<4>, KiddoV6VecOfArenas<f32, u32, 3, 32>, 3, 32>;
type KiddoV6DonnellyBlockSimdItemSortedStarTreeF32 = KiddoV6KdTree<
f32,
u32,
KiddoV6DonnellySimdFull<4>,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6DonnellyBlockSimdQuadTreeF32 =
KiddoV6KdTree<f32, u32, KiddoV6DonnellySimdFull<4>, KiddoV6VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type KiddoV6DonnellyBlockSimdStarTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6DonnellySimdFull<3>, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32>;
type KiddoV6DonnellyBlockSimdItemSortedStarTreeF64 = KiddoV6KdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type KiddoV6DonnellyBlockSimdMinSummaryStarTreeF64 = KiddoV6KdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
8,
>;
type KiddoV6DonnellyBlockSimdQuadTreeF64 =
KiddoV6KdTree<f64, u32, KiddoV6DonnellySimdFull<3>, KiddoV6VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type ArchivedKiddoV6StarTreeF32 =
KiddoV6ArchivedKdTree<f32, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f32, u32, 3, 32>, 3, 32>;
type ArchivedKiddoV6ItemSortedStarTreeF32 = KiddoV6ArchivedKdTree<
f32,
u32,
KiddoV6Eytzinger,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6QuadTreeF32 =
KiddoV6ArchivedKdTree<f32, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type ArchivedKiddoV6StarTreeF64 =
KiddoV6ArchivedKdTree<f64, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32>;
type ArchivedKiddoV6ItemSortedStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6Eytzinger,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6QuadTreeF64 =
KiddoV6ArchivedKdTree<f64, u32, KiddoV6Eytzinger, KiddoV6VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type ArchivedKiddoV6DonnellyPfStarTreeF32 =
KiddoV6ArchivedKdTree<f32, u32, KiddoV6Donnelly<4>, KiddoV6VecOfArenas<f32, u32, 3, 32>, 3, 32>;
type ArchivedKiddoV6DonnellyPfItemSortedStarTreeF32 = KiddoV6ArchivedKdTree<
f32,
u32,
KiddoV6Donnelly<4>,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6DonnellyPfQuadTreeF32 =
KiddoV6ArchivedKdTree<f32, u32, KiddoV6Donnelly<4>, KiddoV6VecOfArenas<f32, u32, 4, 32>, 4, 32>;
type ArchivedKiddoV6DonnellyPfStarTreeF64 =
KiddoV6ArchivedKdTree<f64, u32, KiddoV6Donnelly<3>, KiddoV6VecOfArenas<f64, u32, 3, 32>, 3, 32>;
type ArchivedKiddoV6DonnellyPfItemSortedStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6Donnelly<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6DonnellyPfMinSummaryStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6Donnelly<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
8,
>;
type ArchivedKiddoV6DonnellyPfQuadTreeF64 =
KiddoV6ArchivedKdTree<f64, u32, KiddoV6Donnelly<3>, KiddoV6VecOfArenas<f64, u32, 4, 32>, 4, 32>;
type ArchivedKiddoV6DonnellyBlockSimdStarTreeF32 = KiddoV6ArchivedKdTree<
f32,
u32,
KiddoV6DonnellySimdFull<4>,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
>;
type ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF32 = KiddoV6ArchivedKdTree<
f32,
u32,
KiddoV6DonnellySimdFull<4>,
KiddoV6VecOfArenas<f32, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6DonnellyBlockSimdQuadTreeF32 = KiddoV6ArchivedKdTree<
f32,
u32,
KiddoV6DonnellySimdFull<4>,
KiddoV6VecOfArenas<f32, u32, 4, 32>,
4,
32,
>;
type ArchivedKiddoV6DonnellyBlockSimdStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
>;
type ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
ITEM_LEAF_MODE_SORTED,
>;
type ArchivedKiddoV6DonnellyBlockSimdMinSummaryStarTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 3, 32>,
3,
32,
8,
>;
type ArchivedKiddoV6DonnellyBlockSimdQuadTreeF64 = KiddoV6ArchivedKdTree<
f64,
u32,
KiddoV6DonnellySimdFull<3>,
KiddoV6VecOfArenas<f64, u32, 4, 32>,
4,
32,
>;
impl_kdtree_v6_owned!(
KiddoV6StarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6ItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6QuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6StarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6ItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6QuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfQuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfMinSummaryStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyPfQuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdQuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdMinSummaryStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_owned!(
KiddoV6DonnellyBlockSimdQuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6StarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6ItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6QuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6StarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6ItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6QuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfQuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfMinSummaryStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyPfQuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF32,
3,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdQuadTreeF32,
4,
f32,
KiddoV6SquaredEuclidean<f32>,
KiddoV6Manhattan<f32>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdMinSummaryStarTreeF64,
3,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
impl_kdtree_v6_ref!(
ArchivedKiddoV6DonnellyBlockSimdQuadTreeF64,
4,
f64,
KiddoV6SquaredEuclidean<f64>,
KiddoV6Manhattan<f64>
);
#[allow(unused)]
macro_rules! handle_dimensions {
(
$buffer:expr,
$dimensions:expr,
$axis:expr,
$index:expr,
$bucket_size:expr,
$type_handler:ident,
[$($supported_bucket:literal),*],
$type_mappings:tt
) => {
match $dimensions {
3 => handle_bucket_sizes!(
$buffer,
3,
$axis,
$index,
$bucket_size,
$type_handler,
[$($supported_bucket),*],
$type_mappings
),
4 => handle_bucket_sizes!(
$buffer,
4,
$axis,
$index,
$bucket_size,
$type_handler,
[$($supported_bucket),*],
$type_mappings
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", $dimensions)),
}
};
}
macro_rules! handle_bucket_sizes {
(
$buf:expr,
$dim:literal,
$axis:expr,
$index:expr,
$bucket_size:expr,
$type_handler:ident, // Accept the type handler
[$($bucket:literal),*], // Accept supported bucket sizes
$types:tt // Pass through the type mappings
) => {
match $bucket_size {
$(
$bucket => $type_handler!($buf, $dim, $axis, $index, $bucket, $types),
)*
_ => Err(anyhow::anyhow!("Unsupported bucket size: {}", $bucket_size)),
}
};
}
macro_rules! handle_kiddo_v6_load_with_types {
(
$buf:expr,
$dim:literal,
$axis:expr,
$index:expr,
$bucket:literal,
[$(($float_type:path, $index_type:path) => $archived_tree_type:ty),*]
) => {
match ($axis, $index) {
$(
($float_type, $index_type) => {
let tree: Box<dyn KdTree<$dim>> = Box::new(
AlignedArchivedKdTree::<$archived_tree_type, $dim>::new($buf)
);
Ok(unsafe { std::mem::transmute::<
Box<dyn KdTree<$dim>>,
Box<dyn KdTree<D>>,
>(tree) })
},
)*
_ => Err(anyhow::anyhow!(
"Unsupported Kiddo v6 float or index type: {:?}, {:?}",
$axis,
$index
)),
}
};
}
macro_rules! handle_kiddo_v6_save_with_types {
(
$tree:expr,
$dim:literal,
$axis:expr,
$index:expr,
$bucket:literal,
[$(($float_type:path, $index_type:path) => $tree_type:ty),*]
) => {
match ($axis, $index) {
$(
($float_type, $index_type) => {
let tree = $tree
.as_any()
.downcast_ref::<$tree_type>()
.ok_or_else(|| anyhow::anyhow!("Failed to downcast Kiddo v6 KD-tree"))?;
Ok(to_bytes::<RkyvError>(tree)?.to_vec())
},
)*
_ => Err(anyhow::anyhow!(
"Unsupported Kiddo v6 float or index type: {:?}, {:?}",
$axis,
$index
)),
}
};
}
pub fn load_kd_tree<'a, F: Flt, const D: usize>(
buf: &'a [u8],
kd_tree_descriptor: &KdTreeDescriptor,
) -> anyhow::Result<Box<dyn KdTree<D> + 'a>> {
#[allow(unused)]
match kd_tree_descriptor {
KdTreeDescriptor::KiddoV6 {
axis,
index,
bucket_size,
stem_strategy,
leaf_strategy,
item_leaf_mode,
} => match stem_strategy {
KiddoV6StemStrategy::EytzingerPf => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6StarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6StarTreeF64
]
),
4 => handle_bucket_sizes!(
buf,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6QuadTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6QuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6ItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6ItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are not supported by Eytzinger trees"
)),
},
KiddoV6StemStrategy::DonnellyScalar => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyPfStarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyPfStarTreeF64
]
),
4 => handle_bucket_sizes!(
buf,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyPfQuadTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyPfQuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyPfItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyPfItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyPfMinSummaryStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are supported only for star-tree dimension 3"
)),
},
},
KiddoV6StemStrategy::DonnellySimd => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdStarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdStarTreeF64
]
),
4 => handle_bucket_sizes!(
buf,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdQuadTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdQuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => match D {
3 => handle_bucket_sizes!(
buf,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_load_with_types,
[32],
[
(FloatType::Float64, IndexType::U32) => ArchivedKiddoV6DonnellyBlockSimdMinSummaryStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are supported only for star-tree dimension 3"
)),
},
},
},
_ => Err(anyhow::anyhow!("Unsupported KD-tree type")),
}
}
pub fn save_kd_tree<const D: usize>(
tree: &dyn KdTree<D>,
kd_tree_descriptor: &KdTreeDescriptor,
) -> anyhow::Result<Vec<u8>> {
#[allow(unused)]
match kd_tree_descriptor {
KdTreeDescriptor::KiddoV6 {
axis,
index,
bucket_size,
stem_strategy,
leaf_strategy,
item_leaf_mode,
} => match stem_strategy {
KiddoV6StemStrategy::EytzingerPf => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6StarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6StarTreeF64
]
),
4 => handle_bucket_sizes!(
tree,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6QuadTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6QuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6ItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6ItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are not supported by Eytzinger trees"
)),
},
KiddoV6StemStrategy::DonnellyScalar => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyPfStarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyPfStarTreeF64
]
),
4 => handle_bucket_sizes!(
tree,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyPfQuadTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyPfQuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyPfItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyPfItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyPfMinSummaryStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are supported only for star-tree dimension 3"
)),
},
},
KiddoV6StemStrategy::DonnellySimd => match (leaf_strategy, item_leaf_mode) {
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::Unsorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyBlockSimdStarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyBlockSimdStarTreeF64
]
),
4 => handle_bucket_sizes!(
tree,
4,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyBlockSimdQuadTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyBlockSimdQuadTreeF64
]
),
_ => Err(anyhow::anyhow!("Unsupported dimension: {}", D)),
},
(KiddoV6LeafStrategy::VecOfArenas, KiddoV6ItemLeafMode::ItemSorted) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float32, IndexType::U32) => KiddoV6DonnellyBlockSimdItemSortedStarTreeF32,
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyBlockSimdItemSortedStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Item-sorted Kiddo v6 trees are supported only for star-tree dimension 3"
)),
},
(
KiddoV6LeafStrategy::VecOfArenas,
KiddoV6ItemLeafMode::ItemSortedWithEmbeddedMinShift8,
) => match D {
3 => handle_bucket_sizes!(
tree,
3,
axis,
index,
*bucket_size,
handle_kiddo_v6_save_with_types,
[32],
[
(FloatType::Float64, IndexType::U32) => KiddoV6DonnellyBlockSimdMinSummaryStarTreeF64
]
),
_ => Err(anyhow::anyhow!(
"Embedded minimum-item summaries are supported only for star-tree dimension 3"
)),
},
},
},
_ => Err(anyhow::anyhow!("Unsupported KD-tree type")),
}
}
#[cfg(test)]
mod alignment_tests {
use super::*;
#[test]
fn archived_tree_queries_after_copying_unaligned_bytes() {
let points: Vec<[f64; 4]> = (0..128)
.map(|i| [i as f64 / 128.0, 0.0, 0.0, 0.0])
.collect();
let tree = KiddoV6DonnellyBlockSimdQuadTreeF64::new_from_slice(&points).unwrap();
let archive = to_bytes::<RkyvError>(&tree).unwrap();
let mut storage = vec![0; archive.len() + 8];
let offset = (0..8)
.find(|offset| (storage.as_ptr() as usize + offset) % 8 != 0)
.unwrap();
storage[offset..offset + archive.len()].copy_from_slice(&archive);
let archived = AlignedArchivedKdTree::<ArchivedKiddoV6DonnellyBlockSimdQuadTreeF64, 4>::new(
&storage[offset..offset + archive.len()],
);
let matches = archived.within_radius(&points[37], 0.0001, DistanceMetric::Manhattan);
assert_eq!(matches.len(), 1);
assert_eq!(matches[0].item, 37);
}
}