Struct grid_tree::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 FnMut(&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(
    &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 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_i32, 1_i32>, T, 4_usize>

pub fn new(height: Level) -> Self

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

pub fn new(height: Level) -> Self

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

pub fn new(height: Level) -> Self

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

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.