kiddo 5.0.3

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

#[doc(hidden)]
#[macro_export]
macro_rules! generate_immutable_approx_nearest_one {
    ($comments:tt) => {
        doc_comment! {
            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: usize = 0;
                let mut leaf_idx: usize = 0;

                while level as isize <= self.max_stem_level as isize {
                    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;
                }

                let (start, end) = unsafe { *self.leaf_extents.get_unchecked(leaf_idx) };

                let leaf_slice = $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,
                }
            }
        }
    };
}