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

//! This crate is deprecated. Use [broccoli](https://crates.io/crates/broccoli) instead.

#![no_std]

#[macro_use]
extern crate alloc;
extern crate is_sorted;
extern crate pdqselect;

///axgeom crate is re-exported for easy access to the `Rect<T>` type which is what a `BBox` is composed of.
pub extern crate axgeom;

mod inner_prelude {
    pub(crate) use super::*;
    pub(crate) use crate::tree;
    pub(crate) use crate::tree::analyze::*;
    pub use alloc::vec::Vec;
    pub use axgeom::*;
    pub(crate) use compt::Visitor;
    pub use core::iter::*;
    pub use core::marker::PhantomData;

    pub(crate) use crate::bbox::*;
    pub(crate) use crate::pmut::*;
    pub(crate) use crate::tree::par;
    pub(crate) use crate::tree::*;
}

pub mod query;

use axgeom::*;

///Contains generic code used in all dinotree versions
//pub use self::tree::{DinoTree,analyze,collectable,owned,DefaultA,default_axis};
pub use self::tree::*;

#[deprecated(
    note = "use the broccoli crate instead"
)]
mod tree;

///A collection of 1d functions that operate on lists of 2d objects.
mod oned;

pub mod pmut;

///A collection of different bounding box containers.
mod bbox;
pub use crate::bbox::*;

///Generic slice utillity functions.
pub mod util;

///The underlying number type used for the dinotree.
///It is auto implemented by all types that satisfy the type constraints.
///Notice that no arithmatic is possible. The tree is constructed
///using only comparisons and copying.
pub trait Num: Ord + Copy + Send + Sync {}
impl<T> Num for T where T: Ord + Copy + Send + Sync {}

///Trait to signify that this object has an axis aligned bounding box.
///get() must return a aabb with the same value in it while the element
///is in the dinotree. This is hard for the user not to do, this the user
///does not have &mut self, and the aabb is implied to belong to self.
///But it is still possible through the use of static objects or RefCell/ Mutex, etc.
///Using this type of methods the user could make different calls to get()
///return different aabbs.
///This is unsafe since we allow query algorithms to assume the following:
///If two object's aabb's don't intersect, then they can be mutated at the same time.
pub unsafe trait Aabb {
    type Num: Num;
    fn get(&self) -> &Rect<Self::Num>;
}

unsafe impl<N: Num> Aabb for Rect<N> {
    type Num = N;
    fn get(&self) -> &Rect<Self::Num> {
        self
    }
}

///Trait exposes an api where you can return a read-only reference to the axis-aligned bounding box
///and at the same time return a mutable reference to a seperate inner section.
///
///The trait in unsafe since an incorrect implementation could allow the user to get mutable
///references to each element in the tree allowing them to swap them and thus violating
///invariants of the tree. This can be done if the user were to implement with type Inner=Self
///
///We have no easy way to ensure that the Inner type only points to the inner portion of a AABB
///so we mark this trait as unsafe.
pub unsafe trait HasInner: Aabb {
    type Inner;
    #[inline(always)]
    fn inner_mut(&mut self) -> &mut Self::Inner {
        self.get_inner_mut().1
    }
    #[inline(always)]
    fn inner(&self) -> &Self::Inner {
        self.get_inner().1
    }
    fn get_inner(&self) -> (&Rect<Self::Num>, &Self::Inner);
    fn get_inner_mut(&mut self) -> (&Rect<Self::Num>, &mut Self::Inner);
}