Crate dinotree

Overview

Provides the dinotree data structure and ways to traverse it. All divide and conquer style query algorithms that you can do on this tree would be done using the Vistr and VistrMut visitors. No actual query algorithms are provided in this crate. Only the data structure and a way to construct it are provided in this crate.

The tree is comprised of copies of objects (rather than references) sorted to improve cache coherency. There is an alternative NoCopyDinoTree That does not allocate more space, but instead rearranges the bots in a user provided slice for better cache coherency. However from empirical benchmarking, the version that builds up a new Vec instead of rearranging is faster.

2d Tree Divider Representation:


   o   ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┃         ┆         o
 ┈┈┈┈┈┈┆     o      o     ┃     o   ┆   o                 o
 ───────o─────────────────┃         o┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
               ┆       o  o   o     ┆
       o       ┆    o     ┃┈┈┈┈┈o┈┈┈┆       o
               ┆   o      ┃         o             o
               ┆┈┈┈┈┈┈┈┈┈┈┃         ┆                   o
     o         o    o     ┃───────o────────────────────────
               ┆          ┃                ┆   o
 ┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆      o   o   o            ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
    o          ┆          ┃┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆         o
         o     ┆   o      ┃        o       ┆   o
               ┆          ┃                ┆

Axis alternates every level.
Divider placement is placed at the median at each level.
objects that intersect a divider belong to that node.
Every divider keeps track of how thick a line would have to be
to cover all the bots it owns.
All the objects in a node are sorted along that node's axis.
 

Unsafety

The HasAabb trait is marked as unsafe. See its description. Unsafety used to have slices of bots in the tree, but also a slice of all the bots so that we can efficiently return a slice of all the bots. Unsafety is used to reuse code between sequential and parallel build algorithms.

Modules

advanced	Provies some debugging and misc functions.
par	Contains code to write generic code that can be run in parallel, or sequentially. Not intended to be used directly by the user. Used by algorithms that operate on the tree.

Structs

BBox	A wrapper type around a type T and bounding box where the bounding box is hidden. This is what is inserted into the tree. This way the user cannot modify the bounding box since it is hidden, with only read access.
BBoxMut	A wrapper type where you are allowed to modify the aabb.
DinoTree	The datastructure this crate revolves around.
DinoTreeBuilder	Builder for a DinoTree
DinoTreeNoCopy	A version where the bots are not copied. This means that the slice borrowed from the user must remain borrowed for the entire lifetime of the tree.
DinoTreeNoCopyBuilder	Builder for a DinoTree
DinoTreeRef	Referance to a dinotree container.
DinoTreeRefMut	Mutable referance to a dinotree container.
Node	A node in a dinotree.
NodeRef	Reference to a node in the dinotree.
NodeRefMut	Mutable reference to a node in the dinotree.
NotSorted	A version of a dinotree where the bots that belong to a node are not sorted along an axis. So this is really a regular kd-tree.
Vistr	Tree Iterator that returns a reference to each node. It also returns the non-leaf specific data when it applies.
VistrMut	Tree Iterator that returns a reference to each node. It also returns the non-leaf specific data when it applies.

Traits

HasAabb	Marker trait to signify that this object has an axis aligned bounding box. If two HasAabb objects have aabb's that do not intersect, then it must be safe to have a mutable reference to each simultaneously.
NumTrait	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.