kiddo 5.3.1

//! Floating point k-d tree, for use when the co-ordinates of the points being stored in the tree
//! are floats. f64 or f32 are supported currently, or [`f16`](https://docs.rs/half/latest/half/struct.f16.html) if used with the
//! [`half`](https://docs.rs/half/latest/half) crate.
//!
//! NB if you don't need to be able to add or remove items from the tree after construction /
//! deserialization, you may get better performance from [`immutable::float::kdtree::ImmutableKdTree`](`crate::immutable::float::kdtree::ImmutableKdTree`)
//!
//! ## Normal Usage
//! Most of the structs listed in these docs are only relevant when using `rkyv` for zero-copy
//! serialisation. **The main Struct in here, [`KdTree`], is usually what you're looking for.**
//!
//! ## Rkyv Usage
//! This release of Kiddo supports usage of both Rkyv 0.7 and Rkyv 0.8 simultaneously.
//! Rkyv 0.7.x support is gated behind the `rkyv` crate feature, as has historically been the case since
//! Kiddo introduced Rkyv support.
//! Rkyv 0.8 support is gated behind the newer `rkyv_08` crate feature.
//!
//! ### Deprecation Notice
//! Rkyv can be a tricky beast to work with. Implementing support for both 0.7.x and 0.8.x branches of Rkyv
//! simultaneously was especially painful. As such, **support for Rkyv 0.7.x will be dropped in Kiddo v6**
//! and only 0.8.x will be supported. This will be the only version that supports both.
//! The `rkyv_08` feature will remain and still be called `rkyv_08` to protect against breaking changes should
//! a future version of rkyv be released.
//! With the removal of rkyv 0.7 support, the rkyv 0.8 structs will revert to the default names that are currently
//! being used for the rkyv 0.7 structs.
//!
//! ### Struct Naming
//! Since both rkyv 0.7 and 0.8 by default will attempt to name the structs derived by the `Archive` macro
//! as `ArchivedKdTree` etc., it was necessary to choose a different name for the Rkyv 0.8.x derived types
//! to avoid them clashing with the existing Rkyv 0.7 ones.
//! So, the `ArchivedKdTree` struct is the rkyv 0.7.x Archived version of `KdTree`. The `ArchivedR8KdTree`
//! is the rkyv 0.8.x Archived version of `KdTree`.
//!
//! ### Using both Rkyv and `f16` / `half` support at the same time
//! Additionally, if you are using `rkyv` 0.8 via the `rkyv_08` feature and want
//! to use `f16`, bear in mind that versions of the `half` up to 2.4.1 support `rkyv` 0.7 only,
//! and versions of the `half` crate from 2.5.0 onwards support `rkyv` 0.8 only.
//!
use az::{Az, Cast};
use divrem::DivCeil;
use num_traits::float::FloatCore;
use std::cmp::PartialEq;
use std::fmt::Debug;

#[allow(unused_imports)]
// RustRover keeps adding the below, but Clippy complains it is unnecessary
use crate::rkyv_utils::transform;
use crate::{
    iter::{IterableTreeData, TreeIter},
    traits::{Content, Index},
};

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Axis trait represents the traits that must be implemented
/// by the type that is used as the first generic parameter, `A`,
/// on the float [`KdTree`]. This will be [`f64`] or [`f32`],
/// or [`f16`](https://docs.rs/half/latest/half/struct.f16.html) if used with
/// the [`half`](https://docs.rs/half/latest/half) crate
pub trait Axis: FloatCore + Default + Debug + Copy + Sync + Send + std::ops::AddAssign {
    /// returns absolute diff between two values of a type implementing this trait
    fn saturating_dist(self, other: Self) -> Self;

    /// Used in query methods to update the rd value. A saturating add for Fixed and an add for Float
    #[deprecated(since = "5.3.0", note = "Use D::accumulate instead")] // TODO: change version number if adding this change - or better so: fully get rid off rd_update
    fn rd_update(rd: Self, delta: Self) -> Self;
}

impl<T: FloatCore + Default + Debug + Copy + Sync + Send + std::ops::AddAssign> Axis for T {
    fn saturating_dist(self, other: Self) -> Self {
        (self - other).abs()
    }

    #[inline]
    fn rd_update(rd: Self, delta: Self) -> Self {
        // DEPRECATED: Use D::accumulate instead
        rd + delta
    }
}

// TODO: make LeafNode and StemNode `pub(crate)` so that they,
//       and their Archived types, don't show up in docs.
//       This is tricky due to encountering this problem:
//       https://github.com/rkyv/rkyv/issues/275

/// Floating point k-d tree
///
/// For use when the co-ordinates of the points being stored in the tree
/// on the float [`KdTree`]. This will be [`f64`] or [`f32`],
/// or [`f16`](https://docs.rs/half/latest/half/struct.f16.html) if used with the
/// [`half`](https://docs.rs/half/latest/half) crate.
///
/// A convenient type alias exists for KdTree with some sensible defaults set: [`kiddo::KdTree`](`crate::KdTree`).
///
/// NB if you don't need to be able to add or remove items from the tree after construction /
/// deserialization, you may get better performance from [`immutable::float::kdtree::ImmutableKdTree`](`crate::immutable::float::kdtree::ImmutableKdTree`)
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    feature = "rkyv",
    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
)]
#[cfg_attr(
    feature = "rkyv_08",
    derive(rkyv_08::Archive, rkyv_08::Serialize, rkyv_08::Deserialize)
)]
#[cfg_attr(feature = "rkyv_08", rkyv(crate=rkyv_08, archived=ArchivedR8KdTree, resolver=KdTreeR8Resolver))]
#[derive(Clone, Debug, PartialEq)]
pub struct KdTree<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize, IDX> {
    pub(crate) leaves: Vec<LeafNode<A, T, K, B, IDX>>,
    pub(crate) stems: Vec<StemNode<A, K, IDX>>,
    pub(crate) root_index: IDX,
    pub(crate) size: T,
}

#[doc(hidden)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    feature = "rkyv",
    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
)]
#[cfg_attr(
    feature = "rkyv_08",
    derive(rkyv_08::Archive, rkyv_08::Serialize, rkyv_08::Deserialize)
)]
#[cfg_attr(feature = "rkyv_08", rkyv(crate=rkyv_08, archived=ArchivedR8StemNode, resolver=StemNodeR8Resolver))]
#[cfg_attr(feature = "rkyv_08", rkyv(attr(doc(hidden))))]
#[derive(Clone, Debug, PartialEq)]
pub struct StemNode<A: Copy + Default, const K: usize, IDX> {
    pub(crate) left: IDX,
    pub(crate) right: IDX,
    pub(crate) split_val: A,
}

#[doc(hidden)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    feature = "rkyv",
    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
)]
#[cfg_attr(
    feature = "rkyv_08",
    derive(rkyv_08::Archive, rkyv_08::Serialize, rkyv_08::Deserialize)
)]
#[cfg_attr(feature = "rkyv_08", rkyv(crate=rkyv_08, archived=ArchivedR8LeafNode, resolver=LeafNodeR8Resolver))]
#[cfg_attr(feature = "rkyv_08", rkyv(attr(doc(hidden))))]
#[derive(Clone, Debug, PartialEq)]
pub struct LeafNode<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize, IDX> {
    #[cfg_attr(
        feature = "serde",
        serde(with = "crate::custom_serde::array_of_arrays")
    )]
    #[cfg_attr(
        feature = "serde",
        serde(bound(serialize = "A: Serialize", deserialize = "A: Deserialize<'de>"))
    )]
    // TODO: Refactor content_points to be [[A; B]; K] to see if this helps vectorisation
    pub content_points: [[A; K]; B],

    #[cfg_attr(feature = "serde", serde(with = "crate::custom_serde::array"))]
    #[cfg_attr(
        feature = "serde",
        serde(bound(
            serialize = "A: Serialize, T: Serialize",
            deserialize = "A: Deserialize<'de>, T: Deserialize<'de> + Copy + Default"
        ))
    )]
    pub content_items: [T; B],

    pub size: IDX,
}

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX> LeafNode<A, T, K, B, IDX>
where
    IDX: Index<T = IDX>,
{
    // Enforce bucket size of at least 2. B=1 can trigger UB in split fn
    // https://github.com/sdd/kiddo/issues/295
    const _VALID_B: () = {
        assert!(B > 1, "Bucket size must be at least 2");
    };

    pub(crate) fn new() -> Self {
        #[allow(clippy::let_unit_value)]
        let _ = Self::_VALID_B;

        Self {
            content_points: [[A::zero(); K]; B],
            content_items: [T::zero(); B],
            size: IDX::zero(),
        }
    }
}

impl<A, T, const K: usize, const B: usize, IDX> Default for KdTree<A, T, K, B, IDX>
where
    A: Axis,
    T: Content,
    IDX: Index<T = IDX>,
    usize: Cast<IDX>,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>
where
    A: Axis,
    T: Content,
    IDX: Index<T = IDX>,
    usize: Cast<IDX>,
{
    /// Creates a new float KdTree.
    ///
    /// Capacity is set by default to 10x the bucket size (32 in this case).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use kiddo::KdTree;
    ///
    /// let mut tree: KdTree<f64, 3> = KdTree::new();
    ///
    /// tree.add(&[1.0, 2.0, 5.0], 100);
    ///
    /// assert_eq!(tree.size(), 1);
    /// ```
    #[inline]
    pub fn new() -> Self {
        KdTree::with_capacity(B * 10)
    }

    /// Creates a new float KdTree and reserve capacity for a specific number of items.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use kiddo::KdTree;
    ///
    /// let mut tree: KdTree<f64, 3> = KdTree::with_capacity(1_000_000);
    ///
    /// tree.add(&[1.0, 2.0, 5.0], 100);
    ///
    /// assert_eq!(tree.size(), 1);
    /// ```
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        assert!(capacity <= <IDX as Index>::capacity_with_bucket_size(B));
        let mut tree = Self {
            size: T::zero(),
            stems: Vec::with_capacity(capacity.max(1).ilog2() as usize),
            leaves: Vec::with_capacity(DivCeil::div_ceil(capacity, B.az::<usize>())),
            root_index: <IDX as Index>::leaf_offset(),
        };

        tree.leaves.push(LeafNode::new());

        tree
    }

    /// Iterate over all `(index, point)` tuples in arbitrary order.
    ///
    /// ```
    /// use kiddo::KdTree;
    ///
    /// let mut tree: KdTree<f64, 3> = KdTree::new();
    /// tree.add(&[1.0f64, 2.0f64, 3.0f64], 10);
    /// tree.add(&[11.0f64, 12.0f64, 13.0f64], 20);
    /// tree.add(&[21.0f64, 22.0f64, 23.0f64], 30);
    ///
    /// let mut pairs: Vec<_> = tree.iter().collect();
    /// assert_eq!(pairs.pop().unwrap(), (10, [1.0f64, 2.0f64, 3.0f64]));
    /// assert_eq!(pairs.pop().unwrap(), (20, [11.0f64, 12.0f64, 13.0f64]));
    /// assert_eq!(pairs.pop().unwrap(), (30, [21.0f64, 22.0f64, 23.0f64]));
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = (T, [A; K])> + '_ {
        TreeIter::new(self, B)
    }
}

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>>
    IterableTreeData<A, T, K> for KdTree<A, T, K, B, IDX>
{
    fn get_leaf_data(&self, idx: usize, out: &mut Vec<(T, [A; K])>) -> Option<usize> {
        let leaf = self.leaves.get(idx)?;
        let max = leaf.size.cast();
        out.extend(
            leaf.content_items
                .iter()
                .cloned()
                .zip(leaf.content_points.iter().cloned())
                .take(max),
        );
        Some(max)
    }
}

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> From<&Vec<[A; K]>>
    for KdTree<A, T, K, B, IDX>
where
    usize: Cast<IDX>,
    usize: Cast<T>,
{
    fn from(vec: &Vec<[A; K]>) -> Self {
        let mut tree: KdTree<A, T, K, B, IDX> = KdTree::with_capacity(vec.len());

        vec.iter().enumerate().for_each(|(idx, pos)| {
            tree.add(pos, idx.az::<T>());
        });

        tree
    }
}

macro_rules! generate_common_methods {
    ($kdtree:ident) => {
        /// Returns the current number of elements stored in the tree
        ///
        /// # Examples
        ///
        /// ```rust
        /// use kiddo::KdTree;
        ///
        /// let mut tree: KdTree<f64, 3> = KdTree::new();
        ///
        /// tree.add(&[1.0, 2.0, 5.0], 100);
        /// tree.add(&[1.1, 2.1, 5.1], 101);
        ///
        /// assert_eq!(tree.size(), 2);
        /// ```
        #[inline]
        pub fn size(&self) -> T {
            self.size
        }
    };
}

impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>
where
    A: Axis,
    T: Content,
    IDX: Index<T = IDX>,
    usize: Cast<IDX>,
{
    generate_common_methods!(KdTree);
}

#[cfg(feature = "rkyv")]
impl<
        A: Axis + rkyv::Archive<Archived = A>,
        T: Content + rkyv::Archive<Archived = T>,
        const K: usize,
        const B: usize,
        IDX: Index<T = IDX> + rkyv::Archive<Archived = IDX>,
    > ArchivedKdTree<A, T, K, B, IDX>
where
    usize: Cast<IDX>,
{
    generate_common_methods!(ArchivedKdTree);
}

#[cfg(feature = "rkyv_08")]
impl<
        A: Axis + rkyv_08::Archive,
        T: Content + rkyv_08::Archive,
        const K: usize,
        const B: usize,
        IDX: Index<T = IDX> + rkyv_08::Archive,
    > ArchivedR8KdTree<A, T, K, B, IDX>
where
    usize: Cast<IDX>,
{
    /// Returns the current number of elements stored in the tree
    ///
    /// # Examples
    ///
    /// ```rust
    /// use kiddo::KdTree;
    ///
    /// let mut tree: KdTree<f64, 3> = KdTree::new();
    ///
    /// tree.add(&[1.0, 2.0, 5.0], 100);
    /// tree.add(&[1.1, 2.1, 5.1], 101);
    ///
    /// assert_eq!(tree.size(), 2);
    /// ```
    #[inline]
    pub fn size(&self) -> T {
        *transform(&self.size)
    }
}

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    use crate::float::kdtree::KdTree;
    type AX = f64;

    #[test]
    fn it_can_be_constructed_with_new() {
        let tree: KdTree<AX, u32, 4, 32, u32> = KdTree::new();

        assert_eq!(tree.size(), 0);
    }

    #[test]
    fn it_can_be_constructed_with_a_defined_capacity() {
        let tree: KdTree<AX, u32, 4, 32, u32> = KdTree::with_capacity(10);

        assert_eq!(tree.size(), 0);
    }

    #[test]
    fn it_can_be_constructed_with_a_capacity_of_zero() {
        let tree: KdTree<AX, u32, 4, 32, u32> = KdTree::with_capacity(0);

        assert_eq!(tree.size(), 0);
    }

    #[cfg(feature = "serde")]
    #[test]
    fn can_serde() {
        let mut tree: KdTree<f32, u32, 4, 32, u32> = KdTree::new();

        let content_to_add: [([f32; 4], u32); 16] = [
            ([9f32, 0f32, 9f32, 0f32], 9),
            ([4f32, 500f32, 4f32, 500f32], 4),
            ([12f32, -300f32, 12f32, -300f32], 12),
            ([7f32, 200f32, 7f32, 200f32], 7),
            ([13f32, -400f32, 13f32, -400f32], 13),
            ([6f32, 300f32, 6f32, 300f32], 6),
            ([2f32, 700f32, 2f32, 700f32], 2),
            ([14f32, -500f32, 14f32, -500f32], 14),
            ([3f32, 600f32, 3f32, 600f32], 3),
            ([10f32, -100f32, 10f32, -100f32], 10),
            ([16f32, -700f32, 16f32, -700f32], 16),
            ([1f32, 800f32, 1f32, 800f32], 1),
            ([15f32, -600f32, 15f32, -600f32], 15),
            ([5f32, 400f32, 5f32, 400f32], 5),
            ([8f32, 100f32, 8f32, 100f32], 8),
            ([11f32, -200f32, 11f32, -200f32], 11),
        ];

        for (point, item) in content_to_add {
            tree.add(&point, item);
        }
        assert_eq!(tree.size(), 16);

        let serialized = serde_json::to_string(&tree).unwrap();
        println!("JSON: {:?}", &serialized);

        let deserialized: KdTree<f32, u32, 4, 32, u32> = serde_json::from_str(&serialized).unwrap();
        assert_eq!(tree, deserialized);
    }

    #[test]
    fn can_iterate() {
        let mut t: KdTree<f64, i32, 3, 32, u16> = KdTree::new();
        let expected: HashMap<_, _> = vec![
            (10, [1.0, 2.0, 3.0]),
            (12, [10.0, 2.0, 3.0]),
            (15, [1.0, 20.0, 3.0]),
        ]
        .into_iter()
        .collect();

        for (k, v) in expected.iter() {
            t.add(v, *k);
        }
        let actual: HashMap<_, _> = t.iter().collect();
        assert_eq!(actual, expected);
    }
}