kiddo 5.3.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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#[doc(hidden)]
#[macro_export]
macro_rules! generate_immutable_approx_nearest_one {
    ($comments:tt) => {
            #[doc = concat!$comments]
            #[inline]
            pub fn approx_nearest_one<D>(&self, query: &[A; K]) -> NearestNeighbour<A, T>
            where
                A: $crate::float_leaf_slice::leaf_slice::LeafSliceFloat<T> + $crate::float_leaf_slice::leaf_slice::LeafSliceFloatChunk<T, K>,
                D: DistanceMetric<A, K>,
                usize: Cast<T>,
            {
                #[cfg(feature = "modified_van_emde_boas")]
                use $crate::modified_van_emde_boas::modified_van_emde_boas_get_child_idx_v2;

                #[cfg(feature = "modified_van_emde_boas")]
                let mut curr_idx: usize = 0;
                #[cfg(not(feature = "modified_van_emde_boas"))]
                let mut curr_idx: usize = 1;

                let mut dim: usize = 0;
                let mut best_item = T::zero();
                let mut best_dist = A::max_value();
                let mut level: i32 = 0;
                let mut leaf_idx: usize = 0;

                while level <= Into::<i32>::into(self.max_stem_level) {
                    let val = *unsafe { self.stems.get_unchecked(curr_idx) };
                    let is_right_child = *unsafe { query.get_unchecked(dim) } >= val;

                    #[cfg(feature = "modified_van_emde_boas")]
                    let next_idx = modified_van_emde_boas_get_child_idx_v2(curr_idx as u32, is_right_child, level as u32) as usize;
                    #[cfg(not(feature = "modified_van_emde_boas"))]
                    let next_idx = (curr_idx << 1) + usize::from(is_right_child);

                    curr_idx = next_idx;

                    let is_right_child = usize::from(is_right_child);
                    leaf_idx = (leaf_idx << 1) + is_right_child;

                    level += 1;
                    dim = (dim + 1) % K;
                }

                #[cfg(feature = "rkyv_08")]
                #[allow(clippy::missing_transmute_annotations)]
                let leaf_slice = {
                    let leaf_extent = unsafe { self.leaf_extents.get_unchecked(leaf_idx) };
                    let start = Into::<u32>::into(leaf_extent.0);
                    let end = Into::<u32>::into(leaf_extent.1);

                    $crate::float_leaf_slice::leaf_slice::LeafSlice::new(
                        array_init::array_init(|i| {
                            let archived_slice = &self.leaf_points[i][start as usize..end as usize];
                            unsafe { std::mem::transmute(archived_slice) }
                        }),
                        {
                            let archived_slice = &self.leaf_items[start as usize..end as usize];
                            unsafe { std::mem::transmute(archived_slice) }
                        }
                    )
                };

                #[cfg(not(feature = "rkyv_08"))]
                let leaf_slice = {
                    let (start, end) = unsafe { *self.leaf_extents.get_unchecked(leaf_idx) };

                    $crate::float_leaf_slice::leaf_slice::LeafSlice::new(
                        array_init::array_init(|i|
                            &self.leaf_points[i][start as usize..end as usize]
                        ),
                        &self.leaf_items[start as usize..end as usize],
                    )
                };

                leaf_slice.nearest_one::<D>(
                    query,
                    &mut best_dist,
                    &mut best_item
                );

                NearestNeighbour {
                    distance: best_dist,
                    item: best_item,
                }
            }
    };
}