Struct Tree

pub struct Tree<V, S, T, const CHILDREN: usize> { /* private fields */ }

A generic “grid tree” which can be either a quadtree or an octree depending on the type parameters.

Implementations

impl<V, S, T, const CHILDREN: usize> Tree<V, S, T, CHILDREN>

where V: VectorKey, NodeKey<V>: Hash, S: BranchShape<V>,

pub const CHILDREN: ChildIndex

The maximum number of children a branch node can have. 4 for a quadtree and 8 for an octree.

pub unsafe fn new_generic(height: Level) -> Self

This constructor is only necessary if you need to use a custom shape S or vector V. Otherwise use the constructor for OctreeI32 or QuadtreeI32.

Safety

You must guarantee that S correctly linearizes V vectors so that they don’t go out of array bounds in a block. Refer to QuadtreeShapeI32 and OctreeShapeI32 for examples.

pub fn height(&self) -> Level

The number of Levels in this tree.

pub fn root_level(&self) -> Level

The Level where root nodes live.

pub fn ancestor_root_key(&self, descendant_key: NodeKey<V>) -> NodeKey<V>

Returns the unique root at self.root_level() that is an ancestor of descendant_key.

pub fn iter_root_keys(&self) -> impl Iterator<Item = &NodeKey<V>>

Iterate over all root keys.

pub fn iter_roots(&self) -> impl Iterator<Item = (&NodeKey<V>, &RootNode)>

Iterate over all root nodes.

pub fn contains_node(&self, ptr: NodePtr) -> bool

Returns true iff this tree contains a node for ptr.

pub fn contains_root(&self, key: NodeKey<V>) -> bool

Returns true iff this tree contains a root node at coords.

pub fn get_value(&self, ptr: NodePtr) -> Option<&T>

pub fn get_value_mut(&mut self, ptr: NodePtr) -> Option<&mut T>

pub unsafe fn get_value_unchecked(&self, ptr: NodePtr) -> &T

Safety

The node for ptr must exist.

pub unsafe fn get_value_unchecked_mut(&mut self, ptr: NodePtr) -> &mut T

Safety

The node for ptr must exist.

pub fn insert_root( &mut self, key: NodeKey<V>, parent_ptr: Option<AllocPtr>, new_value: T, ) -> (RootNode, Option<T>)

Inserts value at the root node at key. Returns the old value.

pub fn get_or_create_root( &mut self, key: NodeKey<V>, filler: impl FnMut() -> T, ) -> RootNode

Gets the root pointer or calls filler to insert a value first.

pub fn insert_child( &mut self, parent_ptr: NodePtr, child_index: ChildIndex, child_value: T, ) -> (NodePtr, Option<T>)

Inserts a child node of parent_ptr storing child_value. Returns the old child value if one exists.

pub fn insert_child_at_offset( &mut self, parent_ptr: NodePtr, child_offset: V, child_value: T, ) -> (NodePtr, Option<T>)

Same as insert_child but child_offset is linearized into a ChildIndex based on the BranchShape.

This means any given coordinate in child_offset can only be 0 or 1!

pub fn fill_tree_from_root( &mut self, root_key: NodeKey<V>, min_level: Level, filler: impl FnMut(NodeKey<V>, &mut NodeEntry<'_, T, CHILDREN>) -> VisitCommand, )

Equivalent to calling fill_root and then fill_descendants of that root.

pub fn fill_root( &mut self, key: NodeKey<V>, filler: impl FnOnce(&mut NodeEntry<'_, T, CHILDREN>) -> VisitCommand, ) -> (Option<RootNode>, VisitCommand)

May return the RootNode for convenience.

pub fn child_entry( &mut self, parent_ptr: NodePtr, child_index: ChildIndex, ) -> NodeEntry<'_, T, CHILDREN>

Panics

• If parent_ptr is at level 0 and hence cannot have children.
• If no node exists for parent_ptr.

pub fn fill_descendants( &mut self, ancestor_ptr: NodePtr, ancestor_coordinates: V, min_level: Level, filler: impl FnMut(NodeKey<V>, &mut NodeEntry<'_, T, CHILDREN>) -> VisitCommand, )

Inserts data in descendant “slots” of ancestor_ptr using filler().

Any node N is skipped if filler returns VisitCommand::SkipDescendants for any ancestor of N.

pub fn fill_path_to_node_from_root( &mut self, target_key: NodeKey<V>, filler: impl FnMut(NodeKey<V>, &mut NodeEntry<'_, T, CHILDREN>) -> VisitCommand, )

Call filler on all nodes from the root ancestor to target_key.

pub fn fill_path_to_node( &mut self, ancestor_coordinates: V, ancestor_ptr: NodePtr, target_key: NodeKey<V>, filler: impl FnMut(NodeKey<V>, &mut NodeEntry<'_, T, CHILDREN>) -> VisitCommand, )

Call filler on all nodes from the ancestor to target_key.

pub fn find_root(&self, key: NodeKey<V>) -> Option<RootNode>

Looks up the root pointer for key in the top-level hash map.

pub fn find_node(&self, key: NodeKey<V>) -> Option<ChildRelation<V>>

Starting from the ancestor root, searches for the corresponding descendant node at key.

A ChildRelation is returned because it contains some extra useful info that is conveniently accessible during the search.

pub fn find_descendant( &self, ancestor_ptr: NodePtr, ancestor_coordinates: V, descendant_key: NodeKey<V>, ) -> Option<ChildRelation<V>>

Starting from the node at ancestor_ptr, searches for the corresponding descendant node at descendant_key.

pub fn visit_children( &self, parent_ptr: NodePtr, visitor: impl FnMut(NodePtr, ChildIndex), )

Visits pointers for all non-empty children of the node at parent_ptr.

If parent_ptr does not exist or does not have any children, nothing happens.

pub fn visit_children_with_coordinates( &self, parent_ptr: NodePtr, parent_coordinates: V, visitor: impl FnMut(NodePtr, V), )

Visits pointers and coordinates for all non-empty children of the node at parent_ptr with coordinates parent_coords.

If parent_ptr does not exist or does not have any children, nothing happens.

pub fn visit_tree_depth_first( &self, ancestor_ptr: NodePtr, ancestor_coordinates: V, min_level: Level, visitor: impl FnMut(NodePtr, V) -> VisitCommand, )

Visit ancestor_ptr and all descendants in depth-first order.

If visitor returns false, descendants of that node will not be visited.

pub fn visit_tree_breadth_first( &self, ancestor_ptr: NodePtr, ancestor_coordinates: V, min_level: Level, visitor: impl FnMut(NodePtr, V) -> VisitCommand, )

Visit ancestor_ptr and all descendants in breadth-first order.

If visitor returns false, descendants of that node will not be visited.

pub fn child_pointers( &self, parent_ptr: NodePtr, ) -> Option<ChildPointers<'_, CHILDREN>>

Returns an array of pointers to the children of parent_ptr.

Returns None if parent_ptr is at level 0.

pub fn drop_tree(&mut self, relation: &ChildRelation<V>)

Drops the child node of relation and all descendants.

pub fn remove_tree( &mut self, relation: &ChildRelation<V>, coordinates: V, consumer: impl FnMut(NodeKey<V>, T), )

Moves the child node of relation (with coordinates) and all descendants into consumer.

impl<T> Tree<IVec2, ConstPow2Shape2i32<1, 1>, T, 4>

pub fn new(height: Level) -> Self

impl<T> Tree<UVec2, ConstPow2Shape2u32<1, 1>, T, 4>

pub fn new(height: Level) -> Self

impl<T> Tree<IVec3, ConstPow2Shape3i32<1, 1, 1>, T, 8>

pub fn new(height: Level) -> Self

impl<T> Tree<UVec3, ConstPow2Shape3u32<1, 1, 1>, T, 8>

pub fn new(height: Level) -> Self

Trait Implementations

impl<V: Clone, S: Clone, T: Clone, const CHILDREN: usize> Clone for Tree<V, S, T, CHILDREN>

fn clone(&self) -> Tree<V, S, T, CHILDREN>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V: Debug, S: Debug, T: Debug, const CHILDREN: usize> Debug for Tree<V, S, T, CHILDREN>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.