generational_arena_tree

Trait NodeToken

Source 
pub trait NodeToken<N: Node>:
    Idx
    + Copy
    + PartialEq
    + Debug {

Show 26 methods    // Provided methods
    fn parent(
        &self,
        arena: &Arena<N::Base>,
    ) -> Option<<<N::Base as BaseNode>::Branch as Node>::Token> { ... }
    fn ancestors<'arena>(
        &self,
        arena: &'arena Arena<N::Base>,
    ) -> Ancestors<'arena, N::Base> ⓘ { ... }
    fn root<'arena>(&self, arena: &'arena Arena<N::Base>) -> RootToken<N>
       where for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn data<'arena>(&self, arena: &'arena Arena<N::Base>) -> N::DataRef<'arena>
       where for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn data_mut<'arena>(
        &self,
        arena: &'arena mut Arena<N::Base>,
    ) -> N::DataRefMut<'arena>
       where for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn prev(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
       where N::Base: LinkedNode { ... }
    fn next(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
       where N::Base: LinkedNode { ... }
    fn preceding_siblings<'arena>(
        &self,
        arena: &'arena Arena<N::Base>,
    ) -> PrecedingSiblings<'arena, N> ⓘ
       where N::Base: LinkedNode { ... }
    fn following_siblings<'arena>(
        &self,
        arena: &'arena Arena<N::Base>,
    ) -> FollowingSiblings<'arena, N> ⓘ
       where N::Base: LinkedNode { ... }
    fn first(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
       where N: BranchNode,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn last(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
       where N: BranchNode,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn children<'arena>(
        &self,
        arena: &'arena Arena<N::Base>,
    ) -> N::ChildrenIter<'arena>
       where N: BranchNode,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn descendants<'arena>(
        &self,
        arena: &'arena Arena<N::Base>,
    ) -> Descendants<'arena, N> ⓘ
       where N: BranchNode,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn len(&self, arena: &Arena<N::Base>) -> usize
       where N: BranchNodeDeque,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn is_empty(&self, arena: &Arena<N::Base>) -> bool
       where N: BranchNode,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn get_unchecked(
        &self,
        arena: &Arena<N::Base>,
        index: usize,
    ) -> <N::Base as Node>::Token
       where N: BranchNodeDeque,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn get(
        &self,
        arena: &Arena<N::Base>,
        index: usize,
    ) -> Option<<N::Base as Node>::Token>
       where N: BranchNodeDeque,
             for<'base> &'base N: TryFrom<&'base N::Base>,
             for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug { ... }
    fn detach_front(
        &self,
        arena: &mut Arena<N::Base>,
    ) -> Option<<N::Base as Node>::Token>
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn detach_back(
        &self,
        arena: &mut Arena<N::Base>,
    ) -> Option<<N::Base as Node>::Token>
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn pop_front(
        &self,
        arena: &mut Arena<N::Base>,
    ) -> Option<<N::Base as BaseNode>::Representation>
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn pop_back(
        &self,
        arena: &mut Arena<N::Base>,
    ) -> Option<<N::Base as BaseNode>::Representation>
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn push_front(
        &self,
        arena: &mut Arena<N::Base>,
        new: <N::Base as Node>::Token,
    )
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn push_back(
        &self,
        arena: &mut Arena<N::Base>,
        new: <N::Base as Node>::Token,
    )
       where N: BranchNode<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn detach(
        &self,
        arena: &mut Arena<N::Base>,
        index: usize,
    ) -> <N::Base as Node>::Token
       where N: BranchNodeDeque<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn remove(
        &self,
        arena: &mut Arena<N::Base>,
        index: usize,
    ) -> <N::Base as BaseNode>::Representation
       where N: BranchNodeDeque<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }
    fn insert(
        &self,
        arena: &mut Arena<N::Base>,
        index: usize,
        new: <N::Base as Node>::Token,
    )
       where N: BranchNodeDeque<Token = Self>,
             for<'base> &'base mut N: TryFrom<&'base mut N::Base>,
             for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug { ... }

}

Provided Methods§

Source

fn parent( &self, arena: &Arena<N::Base>, ) -> Option<<<N::Base as BaseNode>::Branch as Node>::Token>

Returns this node’s parent’s token.

If this token refers to a root node, that node will have no parent, so None is returned.

Source

fn ancestors<'arena>( &self, arena: &'arena Arena<N::Base>, ) -> Ancestors<'arena, N::Base> ⓘ

Returns an iterator over the tokens of this node’s ancestors.

This iterator begins with the node’s parent and ends with the root node (i.e. the ancestor with no parent).

Source

fn root<'arena>(&self, arena: &'arena Arena<N::Base>) -> RootToken<N>
where for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns this node’s root node.

The root node is the most distant ancestor; it is the only node in a tree that does not have a parent.

If this node is the root node, RootToken::This is returned. Otherwise, RootToken::Ancestor is returned with the root node’s token.

Internally, this method iterates over the node’s ancestors to find the last one, so it is O(n) best, average, and worst case.

Source

fn data<'arena>(&self, arena: &'arena Arena<N::Base>) -> N::DataRef<'arena>
where for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns a reference to the data associated with this node.

Source

fn data_mut<'arena>( &self, arena: &'arena mut Arena<N::Base>, ) -> N::DataRefMut<'arena>
where for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Returns a mutable reference to the data associated with this node.

Source

fn prev(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
where N::Base: LinkedNode,

Returns the token of this node’s previous sibling.

If this node is the first child of its parent, that means there is no previous sibling and thus None is returned.

Source

fn next(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
where N::Base: LinkedNode,

Returns the token of this node’s next sibling.

If this node is the last child of its parent, that means there is no next sibling and thus None is returned.

Source

fn preceding_siblings<'arena>( &self, arena: &'arena Arena<N::Base>, ) -> PrecedingSiblings<'arena, N> ⓘ
where N::Base: LinkedNode,

Returns an iterator over the tokens of this node’s preceding siblings.

This iterator begins with the previous node and ends with the first child of the parent node.

If this is the first child, the iterator will be empty.

Source

fn following_siblings<'arena>( &self, arena: &'arena Arena<N::Base>, ) -> FollowingSiblings<'arena, N> ⓘ
where N::Base: LinkedNode,

Returns an iterator over the tokens of this node’s following siblings.

This iterator begins with the next node and ends with the last child of the parent node.

If this is the last child, the iterator will be empty.

Source

fn first(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
where N: BranchNode, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns the token of this branch node’s first child.

If this branch node has no children, None is returned.

Source

fn last(&self, arena: &Arena<N::Base>) -> Option<<N::Base as Node>::Token>
where N: BranchNode, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns the token of this branch node’s last child.

If this branch node has no children, None is returned.

Source

fn children<'arena>( &self, arena: &'arena Arena<N::Base>, ) -> N::ChildrenIter<'arena>
where N: BranchNode, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns an iterator over the tokens of this branch node’s children.

Source

fn descendants<'arena>( &self, arena: &'arena Arena<N::Base>, ) -> Descendants<'arena, N> ⓘ
where N: BranchNode, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns an iterator over the tokens of this branch node’s descendants.

This iterator is a breadth-first traversal of the branch node’s descendants: its children are done first, then those children’s children in the same order, and so on and so on.

Source

fn len(&self, arena: &Arena<N::Base>) -> usize
where N: BranchNodeDeque, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Available on crate feature deque only.

Returns the number of children this branch node has.

Source

fn is_empty(&self, arena: &Arena<N::Base>) -> bool
where N: BranchNode, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Returns whether this branch node has no children.

Source

fn get_unchecked( &self, arena: &Arena<N::Base>, index: usize, ) -> <N::Base as Node>::Token
where N: BranchNodeDeque, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Available on crate feature deque only.

Returns the token of the child at the given index.

§Panics

This method will panic if index is out of bounds.

§See also

For a fallible version, see get.

Source

fn get( &self, arena: &Arena<N::Base>, index: usize, ) -> Option<<N::Base as Node>::Token>
where N: BranchNodeDeque, for<'base> &'base N: TryFrom<&'base N::Base>, for<'base> <&'base N as TryFrom<&'base N::Base>>::Error: Debug,

Available on crate feature deque only.

Returns the token of the child at the given index.

If index is out of bounds, None is returned.

§See also

For a version without bounds checks, see get_unchecked.

Source

fn detach_front( &self, arena: &mut Arena<N::Base>, ) -> Option<<N::Base as Node>::Token>
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Detaches this branch node’s first child, returning its token.

If this branch node is empty then there is no child to detach, so None is returned. Otherwise, the child is removed from this branch node’s children, but remains in the arena.

This function is useful if you want to move a node from one parent to another.

§See also

The last child may also be detached using detach_back. If this is a BranchNodeDeque, children may also be detached by index using detach.

If you want to remove a child and its descendants from the arena altogether, see pop_front, pop_back, or, if this is a BranchNodeDeque, remove.

Source

fn detach_back( &self, arena: &mut Arena<N::Base>, ) -> Option<<N::Base as Node>::Token>
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Detaches this branch node’s last child, returning its token.

If this branch node is empty then there is no child to detach, so None is returned. Otherwise, the child is removed from this branch node’s children, but remains in the arena.

This function is useful if you want to move a node from one parent to another.

§See also

The first child may also be detached using detach_front. If this is a BranchNodeDeque, children may also be detached by index using detach.

If you want to remove a child and its descendants from the arena altogether, see pop_front, pop_back, or, if this is a BranchNodeDeque, remove.

Source

fn pop_front( &self, arena: &mut Arena<N::Base>, ) -> Option<<N::Base as BaseNode>::Representation>
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Removes this branch node’s first child.

If this branch node is empty then there is no child to remove, so None is returned. Otherwise, the removed node is returned.

§See also

The last child may also be removed using pop_back. If this is a BranchNodeDeque, children may also be removed by index using remove.

If you don’t want to remove a child from the arena, but merely make it a root node or move it to another parent, see detach_front, detach_back, or, if this is a BranchNodeDeque, detach.

Source

fn pop_back( &self, arena: &mut Arena<N::Base>, ) -> Option<<N::Base as BaseNode>::Representation>
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Removes this branch node’s last child.

If this branch node is empty then there is no child to remove, so None is returned. Otherwise, the removed node is returned.

§See also

The first child may also be removed using pop_front. If this is a BranchNodeDeque, children may also be removed by index using remove.

If you don’t want to remove a child from the arena, but merely make it a root node or move it to another parent, see detach_front, detach_back, or, if this is a BranchNodeDeque, detach.

Source

fn push_front(&self, arena: &mut Arena<N::Base>, new: <N::Base as Node>::Token)
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Pushes the given new token’s node to the beginning of this branch node’s children.

§Panics

This method will panic if the given new token refers to either:

§See also

A child may also be pushed to the end with push_back. If this is a BranchNodeDeque, children may also be inserted by index using insert.

Source

fn push_back(&self, arena: &mut Arena<N::Base>, new: <N::Base as Node>::Token)
where N: BranchNode<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Pushes the given new token’s node to the end of this branch node’s children.

§Panics

This method will panic if the given new token refers to either:

§See also

A child may also be pushed to the beginning with push_front. If this is a BranchNodeDeque, children may also be inserted by index using insert. If this is a BranchNodeDeque, children may also be inserted by index using insert.

Source

fn detach( &self, arena: &mut Arena<N::Base>, index: usize, ) -> <N::Base as Node>::Token
where N: BranchNodeDeque<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Available on crate feature deque only.

Detaches the child at the given index, returning its token.

This function is useful if you want to move a node from one parent to another.

§Panics

This method will panic if the given index is out of bounds.

§See also

The first child or last child may be detached with detach_front and detach_back respectively.

If you want to remove a child and its descendents from the arena altogether, see remove, pop_front, or pop_back.

Source

fn remove( &self, arena: &mut Arena<N::Base>, index: usize, ) -> <N::Base as BaseNode>::Representation
where N: BranchNodeDeque<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Available on crate feature deque only.

Removes the child at the given index.

§Panics

This method will panic if the given index is out of bounds.

§See also

The first child or last child may be removed with pop_front and pop_back respectively.

If you don’t want to remove a child from the arena, but merely make it a root node or move it to another parent, see detach, detach_front, or detach_back.

Source

fn insert( &self, arena: &mut Arena<N::Base>, index: usize, new: <N::Base as Node>::Token, )
where N: BranchNodeDeque<Token = Self>, for<'base> &'base mut N: TryFrom<&'base mut N::Base>, for<'base> <&'base mut N as TryFrom<&'base mut N::Base>>::Error: Debug,

Available on crate feature deque only.

Inserts the given new token’s node at the given index.

§Panics

This method will panic if:

  • the given index is greater than the len(); or
  • the given new token refers to either:
§See also

A child can also be pushed to the beginning or end of this branch node’s children with push_front and push_back respectively.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§

Source§

impl<BranchData, LeafData> NodeToken<SplitNode<BranchData, LeafData>> for SplitToken<BranchData, LeafData>
where BranchData: Debug, LeafData: Debug,

Available on crate feature split only.
Source§

impl<BranchData, LeafData> NodeToken<SplitNodeDeque<BranchData, LeafData>> for SplitTokenDeque<BranchData, LeafData>
where BranchData: Debug, LeafData: Debug,

Available on crate features deque and split only.
Source§

impl<N: Node> NodeToken<<N as Node>::Base> for RootToken<N>

Source§

impl<N: Node<Token = Self>> NodeToken<N> for Token<N>