Module charcoal::quadtree

This is supported on crate feature quadtree only.

Trees which allow nodes to have either zero children or exactly 4, most often used to partition a 2D space by recursively subdividing it into four quadrants.

The Wikipedia article on quadtrees covers their use cases and specifics in more detail.

Example

use charcoal::quadtree::{Quadtree, NodeRef};

// Create the tree. The only thing we need for that is the data payload for the root node. The
// turbofish there is needed to state that we are using the default storage method instead of
// asking the compiler to infer it, which would be impossible.
let mut tree = Quadtree::<_>::new(451);

// Let's now try to access the structure of the tree and look around.
let root = tree.root();
// We have never added any nodes to the tree, so the root does not have any children, hence:
assert!(root.is_leaf());

// Let's replace our reference to the root with a mutable one, to mutate the tree!
let mut root = tree.root_mut();
// First things first, we want to change our root's data payload:
*(root.value_mut().into_inner()) = 120;
// While we're at it, let's add some child nodes:
let my_numbers = [
    // Random numbers are not what you'd typically see in a quadtree, but for the sake of this
    // example we can use absolutely any kind of data. Bonus points for finding hidden meaning.
    2010, 2014, 1987, 1983,
];
root.make_branch(my_numbers).unwrap();

// Let's return to an immutable reference and look at our tree.
let root = NodeRef::from(root); // Conversion from a mutable to an immutable reference
assert_eq!(root.value().into_inner(), &120);
let children = {
    let children_refs = root.children().unwrap();
    let get_val = |x| {
        // Type inference decided to abandon us here
        let x: NodeRef<'_, _, _, _> = children_refs[x];
        *x.value().into_inner()
    };
    [ get_val(0), get_val(1), get_val(2), get_val(3) ]
};
assert_eq!(children, my_numbers);

Structs

Node	A node of a quadtree.
NodeRef	A reference to a node in a quadtree.
NodeRefMut	A mutable reference to a node in a quadtree.
PackedChildren	Packed leaf children nodes of an quadtree’s branch node.
PackedChildrenIter	An owned iterator over the elements of PackedChildren.
Quadtree	A quadtree.

Type Definitions

SparseVecQuadtree	alloc A quadtree which uses a sparse Vec as backing storage.
VecQuadtree	alloc A quadtree which uses a Vec as backing storage.