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

use super::*;
use tree::TreeBuilder;

///A version of Tree where the elements are not sorted along each axis, like a KD Tree.
/// For comparison, a normal kd-tree is provided by [`NotSorted`]. In this tree, the elements are not sorted
/// along an axis at each level. Construction of [`NotSorted`] is faster than [`Tree`] since it does not have to
/// sort bots that belong to each node along an axis. But most query algorithms can usually take advantage of this
/// extra property to be faster.
pub struct NotSorted<'a, A: Axis, T: Aabb>(pub(crate) Tree<'a, A, T>);

impl<'a, T: Aabb + Send + Sync> NotSorted<'a, DefaultA, T> {
    pub fn new_par(bots: &'a mut [T]) -> NotSorted<'a, DefaultA, T> {
        TreeBuilder::new(bots).build_not_sorted_par()
    }
}
impl<'a, T: Aabb> NotSorted<'a, DefaultA, T> {
    pub fn new(bots: &'a mut [T]) -> NotSorted<'a, DefaultA, T> {
        TreeBuilder::new(bots).build_not_sorted_seq()
    }
}

impl<'a, A: Axis, T: Aabb + Send + Sync> NotSorted<'a, A, T> {
    pub fn with_axis_par(axis: A, bots: &'a mut [T]) -> NotSorted<'a, A, T> {
        TreeBuilder::with_axis(axis, bots).build_not_sorted_par()
    }
}
impl<'a, A: Axis, T: Aabb> NotSorted<'a, A, T> {
    pub fn with_axis(axis: A, bots: &'a mut [T]) -> NotSorted<'a, A, T> {
        TreeBuilder::with_axis(axis, bots).build_not_sorted_seq()
    }
}

impl<'a, A: Axis, T: Aabb + HasInner> NotSortedQueries<'a> for NotSorted<'a, A, T> {
    type A = A;
    type T = T;
    type Num = T::Num;
    type Inner = T::Inner;

    #[inline(always)]
    fn axis(&self) -> Self::A {
        self.0.axis()
    }

    #[inline(always)]
    fn vistr_mut(&mut self) -> VistrMut<NodeMut<'a, T>> {
        self.0.vistr_mut()
    }

    #[inline(always)]
    fn vistr(&self) -> Vistr<NodeMut<'a, T>> {
        self.0.vistr()
    }
}

impl<'a, A: Axis, T: Aabb> NotSorted<'a, A, T> {
    #[inline(always)]
    pub fn get_height(&self) -> usize {
        self.0.get_height()
    }
}