Struct charcoal::Octree [−][src]
An octree.
See the module-level documentation for more.
Implementations
impl<B, L, K, S> Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
pub fn new(root: L) -> Self
[src]
octree
only.Creates an octree with the specified value for the root node.
Example
// The only way to create a tree... let tree = Octree::<_>::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
[src]
octree
only.Creates an octree 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 = Octree::<_>::with_capacity(9, "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", "Spam", "Eggs", "Monty", "Python", ]); // 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>
[src]
octree
only.Returns a reference to the root node of the tree.
Example
// A tree always has a root node: let tree = Octree::<_>::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>
[src]
octree
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 = Octree::<_>::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
[src]
octree
only.Returns the number of nodes in the tree.
pub fn capacity(&self) -> usize
[src]
octree
only.Returns the additional number of nodes which the tree can store without the need to reallocate.
pub fn reserve(&mut self, additional: usize)
[src]
octree
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)
[src]
octree
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> Octree<B, L, usize, SparseStorage<Node<B, L, usize>, S>> where
S: ListStorage<Element = SparseStorageSlot<Node<B, L, usize>>>,
[src]
S: ListStorage<Element = SparseStorageSlot<Node<B, L, usize>>>,
pub fn defragment(&mut self)
[src]
octree
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::octree::SparseVecOctree; // Create a tree which explicitly uses sparse storage: let mut tree = SparseVecOctree::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, 5, 6, 7, 8, ]).unwrap(); // You can replace this with proper error handling tree .root_mut() .nth_child_mut(0) .unwrap() // This too .make_branch([ 9, 10, 11, 12, 13, 14, 15, 16, ]) .unwrap(); // And this tree .root_mut() .nth_child_mut(0) .unwrap() // Same as above .try_remove_children() .unwrap(); // Same here // We ended up creating 8 holes: assert_eq!(tree.num_holes(), 8); // Let's patch them: tree.defragment(); // Now there are none: assert_eq!(tree.num_holes(), 0);
pub fn num_holes(&self) -> usize
[src]
octree
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
[src]
octree
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 Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B: Copy, L: Copy, K: Copy, S: Copy> Copy for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B: Debug, L: Debug, K: Debug, S: Debug> Debug for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B, L, K, S> Default for Octree<B, L, K, S> where
L: Default,
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
L: Default,
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B: Eq, L: Eq, K: Eq, S: Eq> Eq for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B: Hash, L: Hash, K: Hash, S: Hash> Hash for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.fn hash<__H: Hasher>(&self, state: &mut __H)
[src]
pub fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<B: PartialEq, L: PartialEq, K: PartialEq, S: PartialEq> PartialEq<Octree<B, L, K, S>> for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.fn eq(&self, other: &Octree<B, L, K, S>) -> bool
[src]
fn ne(&self, other: &Octree<B, L, K, S>) -> bool
[src]
impl<B, L, K, S> StructuralEq for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B, L, K, S> StructuralPartialEq for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.impl<B, L, K, S> Traversable for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
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. Read more
fn advance_cursor<V>(
&self,
cursor: Self::Cursor,
direction: VisitorDirection<Self::Cursor, V>
) -> CursorResult<Self::Cursor>
[src]
&self,
cursor: Self::Cursor,
direction: VisitorDirection<Self::Cursor, V>
) -> CursorResult<Self::Cursor>
fn cursor_to_root(&self) -> Self::Cursor
[src]
fn value_of(
&self,
cursor: &Self::Cursor
) -> NodeValue<&Self::Branch, &Self::Leaf>
[src]
&self,
cursor: &Self::Cursor
) -> NodeValue<&Self::Branch, &Self::Leaf>
fn parent_of(&self, cursor: &Self::Cursor) -> Option<Self::Cursor>
[src]
fn num_children_of(&self, cursor: &Self::Cursor) -> usize
[src]
fn nth_child_of(
&self,
cursor: &Self::Cursor,
child_num: usize
) -> Option<Self::Cursor>
[src]
&self,
cursor: &Self::Cursor,
child_num: usize
) -> Option<Self::Cursor>
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>,
[src]
&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>,
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>,
[src]
V: Visitor,
&'a Self: Borrow<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
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>,
[src]
&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>,
impl<B, L, K, S> TraversableMut for Octree<B, L, K, S> where
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
[src]
S: Storage<Element = Node<B, L, K>, Key = K>,
K: Clone + Debug + Eq,
octree
only.const CAN_REMOVE_INDIVIDUAL_CHILDREN: bool
[src]
const CAN_PACK_CHILDREN: bool
[src]
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>
[src]
&mut self,
cursor: &Self::Cursor
) -> NodeValue<&mut Self::Branch, &mut Self::Leaf>
fn try_remove_leaf<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<Self::Leaf, TryRemoveLeafError>
[src]
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<Self::Leaf, TryRemoveLeafError>
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>
[src]
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL,
_collector: C
) -> Result<Self::Branch, TryRemoveBranchError>
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>
[src]
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL,
collector: C
) -> Result<(), TryRemoveChildrenError>
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>
[src]
&mut self,
_cursor: &Self::Cursor,
_branch_to_leaf: BtL
) -> Result<(Self::Branch, Self::PackedChildren), TryRemoveBranchError>
fn try_remove_children<BtL: FnOnce(Self::Branch) -> Self::Leaf>(
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL
) -> Result<Self::PackedChildren, TryRemoveChildrenError>
[src]
&mut self,
cursor: &Self::Cursor,
branch_to_leaf: BtL
) -> Result<Self::PackedChildren, TryRemoveChildrenError>
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>,
[src]
&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>,
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>,
[src]
&'a mut Self: BorrowMut<V::Target>,
Self::Cursor: From<<V::Target as Traversable>::Cursor> + Into<<V::Target as Traversable>::Cursor>,
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>,
[src]
&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>,
Auto Trait Implementations
impl<B, L, K, S> RefUnwindSafe for Octree<B, L, K, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
impl<B, L, K, S> Send for Octree<B, L, K, S> where
K: Send,
S: Send,
K: Send,
S: Send,
impl<B, L, K, S> Sync for Octree<B, L, K, S> where
K: Sync,
S: Sync,
K: Sync,
S: Sync,
impl<B, L, K, S> Unpin for Octree<B, L, K, S> where
K: Unpin,
S: Unpin,
K: Unpin,
S: Unpin,
impl<B, L, K, S> UnwindSafe for Octree<B, L, K, S> where
K: UnwindSafe,
S: UnwindSafe,
K: UnwindSafe,
S: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Slottable for T where
T: Copy,
[src]
T: Copy,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,