Struct charcoal::Quadtree

pub struct Quadtree<B, L = B, K = usize, S = DefaultStorage<Node<B, L, K>>> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq,  { /* fields omitted */ }

A quadtree.

See the module-level documentation for more.

Implementations

impl<B, L, K, S> Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

pub fn new(root: L) -> Self

This is supported on crate feature quadtree only.

Creates a quadtree with the specified value for the root node.

Example

// The only way to create a tree...
let tree = Quadtree::<_>::new(87);
// ...is to simply create the root leaf node and storage. 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.

// No other nodes have been created yet:
assert!(tree.root().is_leaf());

pub fn with_capacity(capacity: usize, root: L) -> Self

This is supported on crate feature quadtree only.

Creates a quadtree with the specified capacity for the storage.

Panics

The storage may panic if it has fixed capacity and the specified value does not match it.

Example

// Let's create a tree, but with some preallocated space for more nodes:
let mut tree = Quadtree::<_>::with_capacity(5, "Variable Names");
// 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.

// Capacity does not affect the actual nodes:
assert!(tree.root().is_leaf());

// Not until we create them ourselves:
tree.root_mut().make_branch([
    "Foo", "Bar", "Baz", "Quux",
]);

// If the default storage is backed by a dynamic memory allocation,
// at most one has happened to this point.

pub fn root(&self) -> NodeRef<'_, B, L, K, S>

This is supported on crate feature quadtree only.

Returns a reference to the root node of the tree.

Example

// A tree always has a root node:
let tree = Quadtree::<_>::new("Root");

assert_eq!(
    // The into_inner() call extracts data from a NodeValue, which is used to generalize
    // tres to both work with same and different types for payloads of leaf and branch
    // nodes.
    *tree.root().value().into_inner(),
    "Root",
);

pub fn root_mut(&mut self) -> NodeRefMut<'_, B, L, K, S>

This is supported on crate feature quadtree only.

Returns a mutable reference to the root node of the tree, allowing modifications to the entire tree.

Example

// A tree always has a root node:
let mut tree = Quadtree::<_>::new("Root");

let mut root_mut = tree.root_mut();
// The into_inner() call extracts data from a NodeValue, which is used to generalize trees
// to both work with same and different types for payloads of leaf and branch nodes.
*(root_mut.value_mut().into_inner()) = "The Source of the Beer";

pub fn num_nodes(&self) -> usize

This is supported on crate feature quadtree only.

Returns the number of nodes in the tree.

pub fn capacity(&self) -> usize

This is supported on crate feature quadtree only.

Returns the additional number of nodes which the tree can store without the need to reallocate.

pub fn reserve(&mut self, additional: usize)

This is supported on crate feature quadtree only.

Reserves capacity for at least additional more elements to be inserted in the given storage. The storage may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

pub fn shrink_to_fit(&mut self)

This is supported on crate feature quadtree only.

Shrinks the capacity of the storage as much as possible.

It will drop down as close as possible to the current length, though dynamically allocated storages may not always reallocate exactly as much as it is needed to store all elements and none more.

impl<B, L, S> Quadtree<B, L, usize, SparseStorage<Node<B, L, usize>, S>> where
    S: ListStorage<Element = SparseStorageSlot<Node<B, L, usize>>>, 

pub fn defragment(&mut self)

This is supported on crate feature quadtree only.

Removes all holes from the sparse storage.

Under the hood, this uses defragment_and_fix. It’s not possible to defragment without fixing the indicies, as that might cause undefined behavior.

Example

use charcoal::quadtree::SparseVecQuadtree;

// Create a tree which explicitly uses sparse storage:
let mut tree = SparseVecQuadtree::new(0);
// This is already the default, but for the sake of this example we'll stay explicit.

// Add some elements for the holes to appear:
tree.root_mut().make_branch([
    1, 2, 3, 4,
]).unwrap(); // You can replace this with proper error handling
tree
    .root_mut()
    .nth_child_mut(0)
    .unwrap() // This too
    .make_branch([5, 6, 7, 8])
    .unwrap(); // And this

tree
    .root_mut()
    .nth_child_mut(0)
    .unwrap() // Same as above
    .try_remove_children()
    .unwrap(); // Same here

// We ended up creating 4 holes:
assert_eq!(tree.num_holes(), 4);
// Let's patch them:
tree.defragment();
// Now there are none:
assert_eq!(tree.num_holes(), 0);

pub fn num_holes(&self) -> usize

This is supported on crate feature quadtree only.

Returns the number of holes in the storage. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.

Example

See the example in defragment.

pub fn is_dense(&self) -> bool

This is supported on crate feature quadtree only.

Returns true if there are no holes in the storage, false otherwise. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.

Example

See the example in defragment.

Trait Implementations

impl<B: Clone, L: Clone, K: Clone, S: Clone> Clone for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

fn clone(&self) -> Quadtree<B, L, K, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<B: Copy, L: Copy, K: Copy, S: Copy> Copy for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

impl<B: Debug, L: Debug, K: Debug, S: Debug> Debug for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

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

Formats the value using the given formatter.

impl<B, L, K, S> Default for Quadtree<B, L, K, S> where
    L: Default,
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

fn default() -> Self

Returns the “default value” for a type.

impl<B: Eq, L: Eq, K: Eq, S: Eq> Eq for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

impl<B: Hash, L: Hash, K: Hash, S: Hash> Hash for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<B: PartialEq, L: PartialEq, K: PartialEq, S: PartialEq> PartialEq<Quadtree<B, L, K, S>> for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

fn eq(&self, other: &Quadtree<B, L, K, S>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Quadtree<B, L, K, S>) -> bool

This method tests for !=.

impl<B, L, K, S> StructuralEq for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

impl<B, L, K, S> StructuralPartialEq for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

impl<B, L, K, S> Traversable for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

type Leaf = L

The payload of the node if it’s a leaf node.

type Branch = B

The payload of the node if it’s a branch node.

type Cursor = K

The type for the cursor which will be used for keeping track of the traversed nodes.

fn advance_cursor<V>(
    &self,
    cursor: Self::Cursor,
    direction: VisitorDirection<Self::Cursor, V>
) -> CursorResult<Self::Cursor>

Advances the specified cursor according to the specified directions from the visitor.

fn cursor_to_root(&self) -> Self::Cursor

Returns the cursor pointing to the root node.

fn value_of(
    &self,
    cursor: &Self::Cursor
) -> NodeValue<&Self::Branch, &Self::Leaf>

Returns a by-reference NodeValue of the node at the specified cursor.

fn parent_of(&self, cursor: &Self::Cursor) -> Option<Self::Cursor>

Returns a cursor to the parent of the node at the specified cursor, or None if that node is the root node.

fn num_children_of(&self, cursor: &Self::Cursor) -> usize

Returns the number of children of the node at the specified cursor.

fn nth_child_of(
    &self,
    cursor: &Self::Cursor,
    child_num: usize
) -> Option<Self::Cursor>

Returns a cursor to the *n*th child of the node at the specified cursor, or None if the child at that index does not exist.

fn step<V>(
    &self,
    visitor: V,
    cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
    V: Visitor,
    &'a Self: Borrow<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Performs one step of the visitor from the specified cursor, returning either the cursor for the next step or the final result of the visitor if it ended.

fn traverse<V>(&self, visitor: V) -> V::Output where
    V: Visitor,
    &'a Self: Borrow<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Traverses the traversable from the root node until the end, returning the final result of the visitor.

fn traverse_from<V>(
    &self,
    starting_cursor: Self::Cursor,
    visitor: V
) -> V::Output where
    V: Visitor,
    &'a Self: Borrow<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Traverses the traversable from the specified starting point until the end, returning the final result of the visitor.

impl<B, L, K, S> TraversableMut for Quadtree<B, L, K, S> where
    S: Storage<Element = Node<B, L, K>, Key = K>,
    K: Clone + Debug + Eq, 

This is supported on crate feature quadtree only.

const CAN_REMOVE_INDIVIDUAL_CHILDREN: bool

Whether the traversable allows removing individual children. This is true for trees which have a variable number of children for branches and false which don’t.

const CAN_PACK_CHILDREN: bool

Whether the try_remove_branch and try_remove_children methods are implemented. If false, PackedChildren must be an iterator type which never yields elements, like Empty.

type PackedChildren = PackedChildren<L>

A container for the leaf children of a branch node.

fn value_mut_of(
    &mut self,
    cursor: &Self::Cursor
) -> NodeValue<&mut Self::Branch, &mut Self::Leaf>

Returns a mutable by-reference NodeValue of the node at the specified cursor, allowing modifications.

fn try_remove_leaf<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
    &mut self,
    _cursor: &Self::Cursor,
    _branch_to_leaf: BtL
) -> Result<Self::Leaf, TryRemoveLeafError>

Attempts to remove a leaf node without using recursion. If its parent only had one child, it’s replaced with a leaf node, the value for which is provided by the specified closure (the previous value is passed into the closure).

fn try_remove_branch_into<BtL: FnOnce(Self::Branch) -> Self::Leaf, C: FnMut(Self::Leaf)>(
    &mut self,
    _cursor: &Self::Cursor,
    _branch_to_leaf: BtL,
    _collector: C
) -> Result<Self::Branch, TryRemoveBranchError>

Attempts to remove a branch node without using recursion. If its parent only had one child, it’s replaced with a leaf node, the value for which is provided by the specified closure (the previous value is passed into the closure). The removed children are put in the specified collector closure in order.

fn try_remove_children_into<BtL: FnOnce(Self::Branch) -> Self::Leaf, C: FnMut(Self::Leaf)>(
    &mut self,
    cursor: &Self::Cursor,
    branch_to_leaf: BtL,
    collector: C
) -> Result<(), TryRemoveChildrenError>

Attempts to remove a branch node’s children without using recursion, replacing it with a leaf node, the value for which is provided by the specified closure. The removed children are put in the specified collector closure in order.

fn try_remove_branch<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
    &mut self,
    _cursor: &Self::Cursor,
    _branch_to_leaf: BtL
) -> Result<(Self::Branch, Self::PackedChildren), TryRemoveBranchError>

Attempts to remove a branch node without using recursion. If its parent only had one child, it’s replaced with a leaf node, the value for which is provided by the specified closure (the previous value is passed into the closure).

fn try_remove_children<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
    &mut self,
    cursor: &Self::Cursor,
    branch_to_leaf: BtL
) -> Result<Self::PackedChildren, TryRemoveChildrenError>

Attempts to remove a branch node’s children without using recursion, replacing it with a leaf node, the value for which is provided by the specified closure.

fn step_mut<V: VisitorMut>(
    &mut self,
    visitor: V,
    cursor: CursorResult<Self::Cursor>
) -> Step<Self::Cursor, V::Output> where
    &'a mut Self: BorrowMut<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Performs one step of the mutating visitor from the specified cursor, returning either the cursor for the next step or the final result of the visitor if it ended.

fn traverse_mut<V: VisitorMut>(&mut self, visitor: V) -> V::Output where
    &'a mut Self: BorrowMut<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Mutably traverses the traversable from the root node until the end, returning the final result of the visitor.

fn traverse_mut_from<V: VisitorMut>(
    &mut self,
    starting_cursor: Self::Cursor,
    visitor: V
) -> V::Output where
    &'a mut Self: BorrowMut<V::Target>,
    Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>, 

Mutably traverses the traversable from the specified starting point until the end, returning the final result of the visitor.