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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

//! Contains query modules for each query algorithm.

use crate::build::default_axis;
use crate::build::Splitter;
use crate::build::SplitterEmpty;
use crate::node::*;
use crate::parallel;
use crate::pmut::*;
use crate::util::*;
use alloc::vec::Vec;
use axgeom::*;
use compt::*;
use core::marker::PhantomData;

pub mod colfind;

pub mod draw;

pub mod knearest;

pub mod raycast;

pub mod nbody;

pub mod rect;

mod tools;

///panics if a broken broccoli tree invariant is detected.
///For debugging purposes only.
pub fn assert_tree_invariants<T: Aabb>(tree: &crate::Tree<T>)
where
    T::Num: core::fmt::Debug,
{
    fn inner<A: Axis, T: Aabb>(axis: A, iter: compt::LevelIter<Vistr<Node<T>>>)
    where
        T::Num: core::fmt::Debug,
    {
        fn a_bot_has_value<N: Num>(it: impl Iterator<Item = N>, val: N) -> bool {
            for b in it {
                if b == val {
                    return true;
                }
            }
            false
        }

        let ((_depth, nn), rest) = iter.next();
        let axis_next = axis.next();

        let f = |a: &&T, b: &&T| -> Option<core::cmp::Ordering> {
            let j = a
                .get()
                .get_range(axis_next)
                .start
                .partial_cmp(&b.get().get_range(axis_next).start)
                .unwrap();
            Some(j)
        };

        {
            use is_sorted::IsSorted;
            assert!(IsSorted::is_sorted_by(&mut nn.range.iter(), f));
        }

        if let Some([start, end]) = rest {
            match nn.div {
                Some(div) => {
                    if nn.range.is_empty() {
                        assert_eq!(nn.cont.start, nn.cont.end);
                        let v: T::Num = Default::default();
                        assert_eq!(nn.cont.start, v);
                    } else {
                        let cont = nn.cont;
                        for bot in nn.range.iter() {
                            assert!(bot.get().get_range(axis).contains(div));
                        }

                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.get().get_range(axis).start),
                            div
                        ));

                        for bot in nn.range.iter() {
                            assert!(cont.contains_range(bot.get().get_range(axis)));
                        }

                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.get().get_range(axis).start),
                            cont.start
                        ));
                        assert!(a_bot_has_value(
                            nn.range.iter().map(|b| b.get().get_range(axis).end),
                            cont.end
                        ));
                    }

                    inner(axis_next, start);
                    inner(axis_next, end);
                }
                None => {
                    for (_depth, n) in start.dfs_preorder_iter().chain(end.dfs_preorder_iter()) {
                        assert!(n.range.is_empty());
                        //assert!(n.cont.is_none());
                        assert_eq!(n.cont.start, nn.cont.end);
                        let v: T::Num = Default::default();
                        assert_eq!(n.cont.start, v);

                        assert!(n.div.is_none());
                    }
                }
            }
        }
    }

    inner(default_axis(), tree.vistr().with_depth(compt::Depth(0)))
}