use crate::inner_prelude::*;
#[cfg(test)]
mod tests;
pub mod owned;
pub mod collectable;
pub mod analyze;
pub mod par;
pub(crate) use self::notsorted::NotSorted;
mod notsorted {
use super::*;
pub struct NotSorted<'a, A: Axis, T: Aabb>(pub(crate) DinoTree<'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> {
DinoTreeBuilder::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> {
DinoTreeBuilder::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> {
DinoTreeBuilder::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> {
DinoTreeBuilder::with_axis(axis, bots).build_not_sorted_seq()
}
}
impl<'a, A: Axis, T: Aabb + HasInner + Send + Sync> NotSorted<'a, A, T> {
pub fn find_intersections_mut_par(
&mut self,
func: impl Fn(&mut T::Inner, &mut T::Inner) + Send + Sync + Copy,
) {
colfind::NotSortedQueryBuilder::new(self)
.query_par(move |mut a, mut b| func(a.inner_mut(), b.inner_mut()));
}
}
impl<'a, A: Axis, T: Aabb> NotSorted<'a, A, T> {
#[inline(always)]
pub fn axis(&self) -> A {
self.0.axis()
}
#[inline(always)]
pub fn get_height(&self) -> usize {
self.0.get_height()
}
#[inline(always)]
pub fn vistr(&self) -> Vistr<NodeMut<'a, T>> {
self.0.inner.vistr()
}
#[inline(always)]
pub fn vistr_mut(&mut self) -> VistrMut<NodeMut<'a, T>> {
VistrMut {
inner: self.0.inner.vistr_mut(),
}
}
}
impl<'a, A: Axis, T: Aabb + HasInner> NotSorted<'a, A, T> {
pub fn find_intersections_mut(
&mut self,
mut func: impl FnMut(&mut T::Inner, &mut T::Inner),
) {
colfind::NotSortedQueryBuilder::new(self)
.query_seq(move |mut a, mut b| func(a.inner_mut(), b.inner_mut()));
}
}
}
use crate::query::*;
pub struct DinoTree<'a, A: Axis, T: Aabb> {
axis: A,
inner: compt::dfs_order::CompleteTreeContainer<NodeMut<'a, T>, compt::dfs_order::PreOrder>,
bots: PMutPtr<[T]>,
}
pub type DefaultA = YAXIS;
pub const fn default_axis() -> YAXIS {
YAXIS
}
impl<'a, T: Aabb> DinoTree<'a, DefaultA, T> {
pub fn new(bots: &'a mut [T]) -> DinoTree<'a, DefaultA, T> {
DinoTreeBuilder::new(bots).build_seq()
}
}
impl<'a, T: Aabb + Send + Sync> DinoTree<'a, DefaultA, T> {
pub fn new_par(bots: &'a mut [T]) -> DinoTree<'a, DefaultA, T> {
DinoTreeBuilder::new(bots).build_par()
}
}
impl<'a, A: Axis, T: Aabb> DinoTree<'a, A, T> {
pub fn with_axis(axis: A, bots: &'a mut [T]) -> DinoTree<'a, A, T> {
DinoTreeBuilder::with_axis(axis, bots).build_seq()
}
}
impl<'a, A: Axis, T: Aabb + Send + Sync> DinoTree<'a, A, T> {
pub fn with_axis_par(axis: A, bots: &'a mut [T]) -> DinoTree<'a, A, T> {
DinoTreeBuilder::with_axis(axis, bots).build_par()
}
}
impl<'a, A: Axis, T: Aabb + HasInner + Send + Sync> DinoTree<'a, A, T> {}
impl<'a, A: Axis, T: Aabb + HasInner + Send + Sync> DinoTree<'a, A, T> {
pub fn find_intersections_mut_par(
&mut self,
func: impl Fn(&mut T::Inner, &mut T::Inner) + Send + Sync + Copy,
) {
query::colfind::QueryBuilder::new(self)
.query_par(move |mut a, mut b| func(a.inner_mut(), b.inner_mut()));
}
pub fn find_intersections_par_ext<B: Send + Sync>(
&mut self,
split: impl Fn(&mut B) -> B + Send + Sync + Copy,
fold: impl Fn(&mut B, B) + Send + Sync + Copy,
collision: impl Fn(&mut B, &mut T::Inner, &mut T::Inner) + Send + Sync + Copy,
acc: B,
) -> B {
struct Foo<T, A, B, C, D> {
_p: PhantomData<T>,
acc: A,
split: B,
fold: C,
collision: D,
}
impl<T: Aabb + HasInner, A, B, C, D: Fn(&mut A, &mut T::Inner, &mut T::Inner)> ColMulti
for Foo<T, A, B, C, D>
{
type T = T;
fn collide(&mut self, mut a: PMut<Self::T>, mut b: PMut<Self::T>) {
(self.collision)(&mut self.acc, a.inner_mut(), b.inner_mut())
}
}
impl<T, A, B: Fn(&mut A) -> A + Copy, C: Fn(&mut A, A) + Copy, D: Copy> Splitter
for Foo<T, A, B, C, D>
{
fn div(&mut self) -> Self {
let acc = (self.split)(&mut self.acc);
Foo {
_p: PhantomData,
acc,
split: self.split,
fold: self.fold,
collision: self.collision,
}
}
fn add(&mut self, b: Self) {
(self.fold)(&mut self.acc, b.acc)
}
fn node_start(&mut self) {}
fn node_end(&mut self) {}
}
let foo = Foo {
_p: PhantomData,
acc,
split,
fold,
collision,
};
let foo = query::colfind::QueryBuilder::new(self).query_splitter_par(foo);
foo.acc
}
}
impl<A: Axis, T: Aabb + HasInner + Send + Sync> DinoTree<'_, A, T> {
#[cfg(feature = "nbody")]
pub fn nbody_mut<X: query::nbody::NodeMassTrait<Num = T::Num, Item = T> + Send + Sync>(
&mut self,
ncontext: &X,
rect: Rect<T::Num>,
) where
X::No: Send,
{
query::nbody::nbody(self, ncontext, rect)
}
}
impl<'a, A: Axis, T: Aabb + HasInner + Send + Sync> DinoTree<'a, A, T> {
#[cfg(feature = "nbody")]
pub fn nbody_mut_par<X: query::nbody::NodeMassTrait<Num = T::Num, Item = T> + Sync + Send>(
&mut self,
ncontext: &X,
rect: Rect<T::Num>,
) where
X::No: Send,
{
query::nbody::nbody_par(self, ncontext, rect)
}
}
impl<'a, A: Axis, T: Aabb + HasInner> DinoTree<'a, A, T> {
#[must_use]
pub fn raycast_mut<Acc>(
&mut self,
ray: axgeom::Ray<T::Num>,
start: &mut Acc,
broad: impl FnMut(&mut Acc, &Ray<T::Num>, &Rect<T::Num>) -> CastResult<T::Num>,
fine: impl FnMut(&mut Acc, &Ray<T::Num>, &T) -> CastResult<T::Num>,
border: Rect<T::Num>,
) -> raycast::RayCastResult<T::Inner, T::Num> {
let mut rtrait = raycast::RayCastClosure {
a: start,
broad,
fine,
_p: PhantomData,
};
raycast::raycast_mut(self, border, ray, &mut rtrait)
}
#[must_use]
pub fn k_nearest_mut<Acc>(
&mut self,
point: Vec2<T::Num>,
num: usize,
start: &mut Acc,
broad: impl FnMut(&mut Acc, Vec2<T::Num>, &Rect<T::Num>) -> T::Num,
fine: impl FnMut(&mut Acc, Vec2<T::Num>, &T) -> T::Num,
border: Rect<T::Num>,
) -> Vec<k_nearest::KnearestResult<T::Inner, T::Num>> {
let mut foo = k_nearest::KnearestClosure {
acc: start,
broad,
fine,
_p: PhantomData,
};
k_nearest::k_nearest_mut(self, point, num, &mut foo, border)
}
pub fn intersect_with_mut<X: Aabb<Num = T::Num> + HasInner>(
&mut self,
other: &mut [X],
func: impl Fn(&mut T::Inner, &mut X::Inner),
) {
intersect_with::intersect_with_mut(self, other, move |a, b| {
(func)(a.into_inner(), b.into_inner())
})
}
pub fn for_all_not_in_rect_mut(
&mut self,
rect: &Rect<T::Num>,
mut func: impl FnMut(&mut T::Inner),
) {
rect::for_all_not_in_rect_mut(self, rect, move |a| (func)(a.into_inner()));
}
pub fn for_all_intersect_rect_mut(
&mut self,
rect: &Rect<T::Num>,
mut func: impl FnMut(&mut T::Inner),
) {
rect::for_all_intersect_rect_mut(self, rect, move |a| (func)(a.into_inner()));
}
pub fn for_all_in_rect_mut(
&mut self,
rect: &Rect<T::Num>,
mut func: impl FnMut(&mut T::Inner),
) {
rect::for_all_in_rect_mut(self, rect, move |a| (func)(a.into_inner()));
}
pub fn find_intersections_mut(&mut self, mut func: impl FnMut(&mut T::Inner, &mut T::Inner)) {
colfind::QueryBuilder::new(self)
.query_seq(move |a, b| func(a.into_inner(), b.into_inner()));
}
pub fn find_intersections_pmut(&mut self, mut func: impl FnMut(PMut<T>, PMut<T>)) {
colfind::QueryBuilder::new(self).query_seq(move |a, b| func(a, b));
}
}
impl<'a, A: Axis, T: Aabb> DinoTree<'a, A, T> {
#[must_use]
#[inline(always)]
pub fn get_bots(&self) -> &[T] {
&unsafe { self.bots.as_mut() }
}
#[must_use]
#[inline(always)]
pub fn get_bots_mut(&mut self) -> PMut<[T]> {
unsafe { self.bots.as_mut() }
}
#[must_use]
#[inline(always)]
pub fn axis(&self) -> A {
self.axis
}
#[must_use]
pub fn vistr_mut(&mut self) -> VistrMut<NodeMut<'a, T>> {
VistrMut {
inner: self.inner.vistr_mut(),
}
}
#[must_use]
pub fn vistr(&self) -> Vistr<NodeMut<'a, T>> {
self.inner.vistr()
}
#[must_use]
#[inline(always)]
pub fn get_height(&self) -> usize {
self.inner.get_height()
}
#[must_use]
#[inline(always)]
pub fn num_nodes(&self) -> usize {
self.inner.get_nodes().len()
}
}
impl<'a, A: Axis, T: Aabb> DinoTree<'a, A, T> {
pub fn draw(&self, drawer: &mut impl graphics::DividerDrawer<N = T::Num>, rect: &Rect<T::Num>) {
graphics::draw(self, drawer, rect)
}
#[must_use]
pub fn multi_rect<'b>(&'b mut self) -> rect::MultiRectMut<'b, 'a, A, T> {
rect::MultiRectMut::new(self)
}
pub fn for_all_intersect_rect<'b>(&'b self, rect: &Rect<T::Num>, func: impl FnMut(&'b T)) {
rect::for_all_intersect_rect(self, rect, func);
}
pub fn for_all_in_rect<'b>(&'b self, rect: &Rect<T::Num>, func: impl FnMut(&'b T)) {
rect::for_all_in_rect(self, rect, func);
}
}
use self::builder::DinoTreeBuilder;
mod builder {
use super::*;
pub struct DinoTreeBuilder<'a, A: Axis, T> {
axis: A,
bots: &'a mut [T],
rebal_strat: BinStrat,
height: usize,
height_switch_seq: usize,
}
impl<'a, A: Axis, T: Aabb + Send + Sync> DinoTreeBuilder<'a, A, T> {
pub fn build_not_sorted_par(&mut self) -> NotSorted<'a, A, T> {
let b = PMut::new(self.bots).as_ptr();
let mut bots: &mut [T] = &mut [];
core::mem::swap(&mut bots, &mut self.bots);
let dlevel = par::compute_level_switch_sequential(self.height_switch_seq, self.height);
let inner = create_tree_par(
self.axis,
dlevel,
bots,
NoSorter,
&mut SplitterEmpty,
self.height,
self.rebal_strat,
);
NotSorted(DinoTree {
axis: self.axis,
inner,
bots: b,
})
}
pub fn build_par(&mut self) -> DinoTree<'a, A, T> {
let b = PMut::new(self.bots).as_ptr();
let mut bots: &mut [T] = &mut [];
core::mem::swap(&mut bots, &mut self.bots);
let dlevel = par::compute_level_switch_sequential(self.height_switch_seq, self.height);
let inner = create_tree_par(
self.axis,
dlevel,
bots,
DefaultSorter,
&mut SplitterEmpty,
self.height,
self.rebal_strat,
);
DinoTree {
axis: self.axis,
inner,
bots: b,
}
}
}
impl<'a, T: Aabb> DinoTreeBuilder<'a, DefaultA, T> {
pub fn new(bots: &'a mut [T]) -> DinoTreeBuilder<'a, DefaultA, T> {
Self::with_axis(default_axis(), bots)
}
}
impl<'a, A: Axis, T: Aabb> DinoTreeBuilder<'a, A, T> {
pub fn with_axis(axis: A, bots: &'a mut [T]) -> DinoTreeBuilder<'a, A, T> {
let rebal_strat = BinStrat::NotChecked;
let height = compute_tree_height_heuristic(bots.len(), DEFAULT_NUMBER_ELEM_PER_NODE);
let height_switch_seq = par::SWITCH_SEQUENTIAL_DEFAULT;
DinoTreeBuilder {
axis,
bots,
rebal_strat,
height,
height_switch_seq,
}
}
pub fn build_not_sorted_seq(&mut self) -> NotSorted<'a, A, T> {
let b = PMut::new(self.bots).as_ptr();
let mut bots: &mut [T] = &mut [];
core::mem::swap(&mut bots, &mut self.bots);
let inner = create_tree_seq(
self.axis,
bots,
NoSorter,
&mut SplitterEmpty,
self.height,
self.rebal_strat,
);
NotSorted(DinoTree {
axis: self.axis,
inner,
bots: b,
})
}
pub fn build_seq(&mut self) -> DinoTree<'a, A, T> {
let b = PMut::new(self.bots).as_ptr();
let mut bots: &mut [T] = &mut [];
core::mem::swap(&mut bots, &mut self.bots);
let inner = create_tree_seq(
self.axis,
bots,
DefaultSorter,
&mut SplitterEmpty,
self.height,
self.rebal_strat,
);
DinoTree {
axis: self.axis,
inner,
bots: b,
}
}
#[inline(always)]
pub fn with_bin_strat(&mut self, strat: BinStrat) -> &mut Self {
self.rebal_strat = strat;
self
}
#[inline(always)]
pub fn with_height(&mut self, height: usize) -> &mut Self {
self.height = height;
self
}
#[inline(always)]
pub fn with_height_switch_seq(&mut self, height: usize) -> &mut Self {
self.height_switch_seq = height;
self
}
pub fn build_with_splitter_seq<S: Splitter>(
&mut self,
splitter: &mut S,
) -> DinoTree<'a, A, T> {
let b = PMut::new(self.bots).as_ptr();
let mut bots: &mut [T] = &mut [];
core::mem::swap(&mut bots, &mut self.bots);
let inner = create_tree_seq(
self.axis,
bots,
DefaultSorter,
splitter,
self.height,
self.rebal_strat,
);
DinoTree {
axis: self.axis,
inner,
bots: b,
}
}
}
}
pub(crate) use self::node::*;
pub mod node {
use super::*;
pub type Vistr<'a, N> = compt::dfs_order::Vistr<'a, N, compt::dfs_order::PreOrder>;
mod vistr_mut {
use crate::inner_prelude::*;
#[repr(transparent)]
pub struct VistrMut<'a, N> {
pub(crate) inner: compt::dfs_order::VistrMut<'a, N, compt::dfs_order::PreOrder>,
}
impl<'a, N> VistrMut<'a, N> {
#[inline(always)]
pub fn create_wrap_mut(&mut self) -> VistrMut<N> {
VistrMut {
inner: self.inner.create_wrap_mut(),
}
}
#[inline(always)]
pub fn as_slice_mut(&mut self) -> PMut<[N]> {
PMut::new(self.inner.as_slice_mut())
}
}
impl<'a, N> core::ops::Deref for VistrMut<'a, N> {
type Target = Vistr<'a, N>;
#[inline(always)]
fn deref(&self) -> &Vistr<'a, N> {
unsafe { &*(self as *const VistrMut<_> as *const Vistr<_>) }
}
}
unsafe impl<'a, N> compt::FixedDepthVisitor for VistrMut<'a, N> {}
impl<'a, N> Visitor for VistrMut<'a, N> {
type Item = PMut<'a, N>;
#[inline(always)]
fn next(self) -> (Self::Item, Option<[Self; 2]>) {
let (nn, rest) = self.inner.next();
let k = match rest {
Some([left, right]) => {
Some([VistrMut { inner: left }, VistrMut { inner: right }])
}
None => None,
};
(PMut::new(nn), k)
}
#[inline(always)]
fn level_remaining_hint(&self) -> (usize, Option<usize>) {
self.inner.level_remaining_hint()
}
#[inline(always)]
fn dfs_preorder(self, mut func: impl FnMut(Self::Item)) {
self.inner.dfs_preorder(move |a| func(PMut::new(a)));
}
}
}
pub use vistr_mut::VistrMut;
pub trait Node {
type T: Aabb<Num = Self::Num>;
type Num: Num;
fn get(&self) -> NodeRef<Self::T>;
fn get_mut(&mut self) -> NodeRefMut<Self::T>;
}
impl<'a, T: Aabb> Node for NodeMut<'a, T> {
type T = T;
type Num = T::Num;
fn get(&self) -> NodeRef<Self::T> {
NodeRef {
bots: self.range.as_ref(),
cont: &self.cont,
div: &self.div,
}
}
fn get_mut(&mut self) -> NodeRefMut<Self::T> {
NodeRefMut {
bots: self.range.as_mut(),
cont: &self.cont,
div: &self.div,
}
}
}
pub struct NodeMut<'a, T: Aabb> {
pub(crate) range: PMut<'a, [T]>,
pub(crate) cont: Option<axgeom::Range<T::Num>>,
pub(crate) div: Option<T::Num>,
}
impl<'a, T: Aabb> NodeMut<'a, T> {
pub fn get(&self) -> NodeRef<T> {
NodeRef {
bots: self.range.as_ref(),
cont: &self.cont,
div: &self.div,
}
}
pub fn get_mut(&mut self) -> NodeRefMut<T> {
NodeRefMut {
bots: self.range.as_mut(),
cont: &self.cont,
div: &self.div,
}
}
}
pub struct NodeRefMut<'a, T: Aabb> {
pub bots: PMut<'a, [T]>,
pub cont: &'a Option<axgeom::Range<T::Num>>,
pub div: &'a Option<T::Num>,
}
pub struct NodeRef<'a, T: Aabb> {
pub bots: &'a [T],
pub cont: &'a Option<axgeom::Range<T::Num>>,
pub div: &'a Option<T::Num>,
}
}
fn create_tree_seq<'a, A: Axis, T: Aabb, K: Splitter>(
div_axis: A,
rest: &'a mut [T],
sorter: impl Sorter,
splitter: &mut K,
height: usize,
binstrat: BinStrat,
) -> compt::dfs_order::CompleteTreeContainer<NodeMut<'a, T>, compt::dfs_order::PreOrder> {
let num_bots = rest.len();
let mut nodes = Vec::with_capacity(tree::nodes_left(0, height));
let r = Recurser {
height,
binstrat,
sorter,
_p: PhantomData,
};
r.recurse_preorder_seq(div_axis, rest, &mut nodes, splitter, 0);
let tree = compt::dfs_order::CompleteTreeContainer::from_preorder(nodes).unwrap();
let k = tree
.get_nodes()
.iter()
.fold(0, move |acc, a| acc + a.range.len());
debug_assert_eq!(k, num_bots);
tree
}
fn create_tree_par<
'a,
A: Axis,
JJ: par::Joiner,
T: Aabb + Send + Sync,
K: Splitter + Send + Sync,
>(
div_axis: A,
dlevel: JJ,
rest: &'a mut [T],
sorter: impl Sorter,
splitter: &mut K,
height: usize,
binstrat: BinStrat,
) -> compt::dfs_order::CompleteTreeContainer<NodeMut<'a, T>, compt::dfs_order::PreOrder> {
let num_bots = rest.len();
let mut nodes = Vec::with_capacity(tree::nodes_left(0, height));
let r = Recurser {
height,
binstrat,
sorter,
_p: PhantomData,
};
r.recurse_preorder(div_axis, dlevel, rest, &mut nodes, splitter, 0);
let tree = compt::dfs_order::CompleteTreeContainer::from_preorder(nodes).unwrap();
let k = tree
.get_nodes()
.iter()
.fold(0, move |acc, a| acc + a.range.len());
debug_assert_eq!(k, num_bots);
tree
}
struct Recurser<'a, T: Aabb, K: Splitter, S: Sorter> {
height: usize,
binstrat: BinStrat,
sorter: S,
_p: PhantomData<(K, &'a T)>,
}
impl<'a, T: Aabb, K: Splitter, S: Sorter> Recurser<'a, T, K, S> {
fn create_leaf<A: Axis>(&self, axis: A, rest: &'a mut [T]) -> NodeMut<'a, T> {
self.sorter.sort(axis.next(), rest);
let cont = create_cont(axis, rest);
NodeMut {
range: PMut::new(rest),
cont,
div: None,
}
}
fn create_non_leaf<A: Axis>(
&self,
axis: A,
rest: &'a mut [T],
) -> (NodeMut<'a, T>, &'a mut [T], &'a mut [T]) {
match construct_non_leaf(self.binstrat, self.sorter, axis, rest) {
ConstructResult::NonEmpty {
cont,
div,
mid,
left,
right,
} => (
NodeMut {
range: PMut::new(mid),
cont,
div: Some(div),
},
left,
right,
),
ConstructResult::Empty(empty) => {
let node = NodeMut {
range: PMut::new(empty),
cont: None,
div: None,
};
(node, &mut [], &mut [])
}
}
}
fn recurse_preorder_seq<A: Axis>(
&self,
axis: A,
rest: &'a mut [T],
nodes: &mut Vec<NodeMut<'a, T>>,
splitter: &mut K,
depth: usize,
) {
splitter.node_start();
if depth < self.height - 1 {
let (node, left, right) = self.create_non_leaf(axis, rest);
nodes.push(node);
let mut splitter2 = splitter.div();
self.recurse_preorder_seq(axis.next(), left, nodes, splitter, depth + 1);
self.recurse_preorder_seq(axis.next(), right, nodes, &mut splitter2, depth + 1);
splitter.add(splitter2);
} else {
let node = self.create_leaf(axis, rest);
nodes.push(node);
splitter.node_end();
}
}
}
impl<'a, T: Aabb + Send + Sync, K: Splitter + Send + Sync, S: Sorter> Recurser<'a, T, K, S> {
fn recurse_preorder<A: Axis, JJ: par::Joiner>(
&self,
axis: A,
dlevel: JJ,
rest: &'a mut [T],
nodes: &mut Vec<NodeMut<'a, T>>,
splitter: &mut K,
depth: usize,
) {
splitter.node_start();
if depth < self.height - 1 {
let (node, left, right) = self.create_non_leaf(axis, rest);
nodes.push(node);
let mut splitter2 = splitter.div();
let splitter = match dlevel.next() {
par::ParResult::Parallel([dleft, dright]) => {
let splitter2 = &mut splitter2;
let ((splitter, nodes), mut nodes2) = rayon::join(
move || {
self.recurse_preorder(
axis.next(),
dleft,
left,
nodes,
splitter,
depth + 1,
);
(splitter, nodes)
},
move || {
let mut nodes2: Vec<_> =
Vec::with_capacity(nodes_left(depth, self.height));
self.recurse_preorder(
axis.next(),
dright,
right,
&mut nodes2,
splitter2,
depth + 1,
);
nodes2
},
);
nodes.append(&mut nodes2);
splitter
}
par::ParResult::Sequential(_) => {
self.recurse_preorder_seq(axis.next(), left, nodes, splitter, depth + 1);
self.recurse_preorder_seq(axis.next(), right, nodes, &mut splitter2, depth + 1);
splitter
}
};
splitter.add(splitter2);
} else {
let node = self.create_leaf(axis, rest);
nodes.push(node);
splitter.node_end();
}
}
}
#[bench]
#[cfg(all(feature = "unstable", test))]
fn bench_cont(b: &mut test::Bencher) {
let grow = 2.0;
let s = dists::spiral::Spiral::new([400.0, 400.0], 17.0, grow);
fn aabb_create_isize(pos: [isize; 2], radius: isize) -> axgeom::Rect<isize> {
axgeom::Rect::new(
pos[0] - radius,
pos[0] + radius,
pos[1] - radius,
pos[1] + radius,
)
}
let bots: Vec<_> = s
.as_isize()
.take(100_000)
.map(move |pos| BBox::new(aabb_create_isize(pos, 5), ()))
.collect();
b.iter(|| {
let k = create_cont(axgeom::XAXISS, &bots);
let _ = test::black_box(k);
});
}
#[bench]
#[cfg(all(feature = "unstable", test))]
fn bench_cont2(b: &mut test::Bencher) {
fn create_cont2<A: Axis, T: Aabb>(axis: A, middle: &[T]) -> axgeom::Range<T::Num> {
let left = middle
.iter()
.map(|a| a.get().get_range(axis).left)
.min()
.unwrap();
let right = middle
.iter()
.map(|a| a.get().get_range(axis).right)
.max()
.unwrap();
axgeom::Range { left, right }
}
let grow = 2.0;
let s = dists::spiral::Spiral::new([400.0, 400.0], 17.0, grow);
fn aabb_create_isize(pos: [isize; 2], radius: isize) -> axgeom::Rect<isize> {
axgeom::Rect::new(
pos[0] - radius,
pos[0] + radius,
pos[1] - radius,
pos[1] + radius,
)
}
let bots: Vec<_> = s
.as_isize()
.take(100_000)
.map(|pos| BBox::new(aabb_create_isize(pos, 5), ()))
.collect();
b.iter(|| {
let k = create_cont2(axgeom::XAXISS, &bots);
let _ = test::black_box(k);
});
}
fn create_cont<A: Axis, T: Aabb>(axis: A, middle: &[T]) -> Option<axgeom::Range<T::Num>> {
match middle.split_first() {
Some((first, rest)) => {
let mut min = first.get().get_range(axis).start;
let mut max = first.get().get_range(axis).end;
for a in rest.iter() {
let start = &a.get().get_range(axis).start;
let end = &a.get().get_range(axis).end;
if *start < min {
min = *start;
}
if *end > max {
max = *end;
}
}
Some(axgeom::Range {
start: min,
end: max,
})
}
None => None,
}
}
enum ConstructResult<'a, T: Aabb> {
NonEmpty {
div: T::Num,
cont: Option<axgeom::Range<T::Num>>,
mid: &'a mut [T],
right: &'a mut [T],
left: &'a mut [T],
},
Empty(&'a mut [T]),
}
fn construct_non_leaf<T: Aabb>(
bin_strat: BinStrat,
sorter: impl Sorter,
div_axis: impl Axis,
bots: &mut [T],
) -> ConstructResult<T> {
let med = if bots.is_empty() {
return ConstructResult::Empty(bots);
} else {
let closure =
move |a: &T, b: &T| -> core::cmp::Ordering { oned::compare_bots(div_axis, a, b) };
let k = {
let mm = bots.len() / 2;
pdqselect::select_by(bots, mm, closure);
&bots[mm]
};
k.get().get_range(div_axis).start
};
let binned = match bin_strat {
BinStrat::Checked => oned::bin_middle_left_right(div_axis, &med, bots),
BinStrat::NotChecked => unsafe {
oned::bin_middle_left_right_unchecked(div_axis, &med, bots)
},
};
sorter.sort(div_axis.next(), binned.middle);
let cont = create_cont(div_axis, binned.middle);
ConstructResult::NonEmpty {
mid: binned.middle,
cont,
div: med,
left: binned.left,
right: binned.right,
}
}