kiddo 6.0.1

A high-performance, flexible, ergonomic k-d tree library. Ideal for geo- and astro- nearest-neighbour and k-nearest-neighbor queries
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

use crate::{Axis, Content, LeafStrategy, StemStrategy};

/// Query-facing interface for resolving stem indices to leaf indices during traversal.
pub trait StemLeafResolution {
    /// Returns true if this resolution strategy uses arithmetic (fast path).
    fn uses_arithmetic(&self) -> bool;

    /// Resolves a terminal stem index to a leaf index.
    fn resolve_terminal_stem_idx(&self, stem_idx: usize, arithmetic_leaf_idx: usize) -> usize;

    /// Returns true if `stem_idx` has an explicit terminal mapping in mapped mode.
    fn is_terminal_stem_idx(&self, stem_idx: usize) -> bool;
}

/// Read-only query access over owned and archived kd-tree storage.
pub trait KdTreeAccessor<A, T, SS, LS, const K: usize, const B: usize>
where
    A: Axis<Coord = A>,
    T: Content,
    SS: StemStrategy,
    LS: LeafStrategy<A, T, SS, K, B>,
{
    /// Stem/branch pivot values in the stem strategy's native layout.
    fn stems(&self) -> &[A];

    /// Leaf storage.
    fn leaves(&self) -> &LS;

    /// Stem-to-leaf resolution strategy.
    fn stem_leaf_resolution(&self) -> &impl StemLeafResolution;

    /// Total number of items.
    fn size(&self) -> usize;

    /// Deepest stem level that can contain an actual pivot.
    fn max_stem_level(&self) -> i32;

    /// Maximum leaf length used for scratch sizing.
    fn max_leaf_len(&self) -> usize;

    /// Number of leaves.
    #[inline]
    fn leaf_count(&self) -> usize {
        self.leaves().leaf_count()
    }
}