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>
{
pub fn assert_find_intersections_mut(&mut self){
let mut res_dino=Vec::new();
self.find_intersections_mut(|a,b|{
let a=a as *const _ as usize;
let b=b as *const _ as usize;
let k=if a<b{(a,b)}else{(b,a)};
res_dino.push(k);
});
let mut res_naive=Vec::new();
NaiveAlgs::new(self.get_bots_mut()).find_intersections_mut(|a,b|{
let a=a as *const _ as usize;
let b=b as *const _ as usize;
let k=if a<b{(a,b)}else{(b,a)};
res_naive.push(k);
});
res_naive.sort();
res_dino.sort();
assert_eq!(res_naive.len(),res_dino.len());
assert!(res_naive.iter().eq(res_dino.iter()));
}
pub fn assert_k_nearest_mut<Acc>(
&mut self,
point: Vec2<T::Num>,
num: usize,
acc:&mut Acc,
mut broad:impl FnMut(&mut Acc,Vec2<T::Num>,&Rect<T::Num>)->T::Num,
mut fine:impl FnMut(&mut Acc,Vec2<T::Num>,&T)->T::Num,
rect: Rect<T::Num>,
)
{
let bots=self.get_bots_mut();
let mut res_naive = NaiveAlgs::new(bots).k_nearest_mut(point, num, acc,&mut broad,&mut fine)
.drain(..)
.map(|a| (a.bot as *const _ as usize,a.mag))
.collect::<Vec<_>>();
let mut r=self.k_nearest_mut(point,num,acc,broad,fine,rect);
let mut res_dino:Vec<_>=r.drain(..).map(|a|(a.bot as *const _ as usize,a.mag)).collect();
res_naive.sort();
res_dino.sort();
assert_eq!(res_naive.len(),res_dino.len());
assert!(res_naive.iter().eq(res_dino.iter()));
}
pub fn assert_raycast_mut<Acc>(
&mut self,
ray: axgeom::Ray<T::Num>,
start: &mut Acc,
mut broad:impl FnMut(&mut Acc,&Ray<T::Num>,&Rect<T::Num>)->CastResult<T::Num>,
mut fine:impl FnMut(&mut Acc,&Ray<T::Num>,&T)->CastResult<T::Num>,
border:Rect<T::Num>
) where <T as Aabb>::Num: core::fmt::Debug
{
let bots=self.get_bots_mut();
let mut res_naive = Vec::new();
match NaiveAlgs::new(bots).raycast_mut(ray, start,&mut broad,&mut fine,border){
RayCastResult::Hit((bots,mag))=>{
for a in bots.iter(){
let j=(*a) as *const _ as usize;
res_naive.push((j,mag))
}
},
RayCastResult::NoHit=>{
}
}
let mut res_dino = Vec::new();
match self.raycast_mut(ray, start,broad,fine,border){
RayCastResult::Hit((bots,mag))=>{
for a in bots.iter(){
let j=(*a) as *const _ as usize;
res_dino.push((j,mag))
}
},
RayCastResult::NoHit=>{
}
}
res_naive.sort();
res_dino.sort();
assert_eq!(res_naive.len(),res_dino.len(),"len:{:?}",(res_naive,res_dino));
assert!(res_naive.iter().eq(res_dino.iter()),"nop:{:?}",(res_naive,res_dino));
}
pub fn assert_for_all_in_rect_mut(&mut self, rect: &axgeom::Rect<T::Num>)
{
let mut res_dino=Vec::new();
self.for_all_in_rect_mut(rect,|a|{
res_dino.push(a as *const _ as usize);
});
let mut res_naive=Vec::new();
NaiveAlgs::new(self.get_bots_mut()).for_all_in_rect_mut(rect,|a|{
res_naive.push(a as *const _ as usize);
});
res_dino.sort();
res_naive.sort();
assert_eq!(res_naive.len(),res_dino.len());
assert!(res_naive.iter().eq(res_dino.iter()));
}
pub fn assert_for_all_not_in_rect_mut(&mut self, rect: &axgeom::Rect<T::Num>)
{
let mut res_dino=Vec::new();
self.for_all_not_in_rect_mut(rect,|a|{
res_dino.push(a as *const _ as usize);
});
let mut res_naive=Vec::new();
NaiveAlgs::new(self.get_bots_mut()).for_all_not_in_rect_mut(rect,|a|{
res_naive.push(a as *const _ as usize);
});
res_dino.sort();
res_naive.sort();
assert_eq!(res_naive.len(),res_dino.len());
assert!(res_naive.iter().eq(res_dino.iter()));
}
pub fn assert_for_all_intersect_rect_mut(&mut self, rect: &axgeom::Rect<T::Num>)
{
let mut res_dino=Vec::new();
self.for_all_intersect_rect_mut(rect,|a|{
res_dino.push(a as *const _ as usize);
});
let mut res_naive=Vec::new();
NaiveAlgs::new(self.get_bots_mut()).for_all_intersect_rect_mut(rect,|a|{
res_naive.push(a as *const _ as usize);
});
res_dino.sort();
res_naive.sort();
assert_eq!(res_naive.len(),res_dino.len());
assert!(res_naive.iter().eq(res_dino.iter()));
}
}
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>{
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)
}
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>{
pub fn get_bots(&self)->&[T]{
&unsafe{self.bots.as_mut()}
}
pub fn get_bots_mut(&mut self)->PMut<[T]>{
unsafe{self.bots.as_mut()}
}
pub fn axis(&self) -> A {
self.axis
}
pub fn vistr_mut(&mut self) -> VistrMut<NodeMut<'a,T>> {
VistrMut {
inner: self.inner.vistr_mut(),
}
}
pub fn vistr(&self) -> Vistr<NodeMut<'a,T>> {
self.inner.vistr()
}
pub fn get_height(&self) -> usize {
self.inner.get_height()
}
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,
}
}