Struct generational_indextree::NodeId

pub struct NodeId { /* private fields */ }

A node identifier within a particular Arena.

This ID is used to get Node references from an Arena.

Implementations

impl NodeId

pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<'_, T>

Returns an iterator of IDs of this node and its ancestors.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |       `-- 1_1_1_1
//     _-- 1_2
//     `-- 1_3

let mut iter = n1_1_1.ancestors(&arena);
assert_eq!(iter.next(), Some(n1_1_1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), None);

pub fn preceding_siblings<T>(self, arena: &Arena<T>) -> PrecedingSiblings<'_, T>

Returns an iterator of IDs of this node and the siblings before it.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1_2.preceding_siblings(&arena);
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), None);

pub fn following_siblings<T>(self, arena: &Arena<T>) -> FollowingSiblings<'_, T>

Returns an iterator of IDs of this node and the siblings after it.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1_2.following_siblings(&arena);
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn children<T>(self, arena: &Arena<T>) -> Children<'_, T>

Returns an iterator of IDs of this node’s children.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.children(&arena);
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<'_, T>

Returns an iterator of IDs of this node’s children, in reverse order.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.reverse_children(&arena);
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), None);

pub fn descendants<T>(self, arena: &Arena<T>) -> Descendants<'_, T>

An iterator of the IDs of a given node and its descendants, as a pre-order depth-first search where children are visited in insertion order.

i.e. node -> first child -> second child

Parent nodes appear before the descendants. Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |       `-- 1_1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_1_1));
assert_eq!(iter.next(), Some(n1_1_1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn traverse<T>(self, arena: &Arena<T>) -> Traverse<'_, T>

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where node sides are visited start to end and children are visited in insertion order.

i.e. node.start -> first child -> second child -> node.end

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.traverse(&arena);
assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1)));
assert_eq!(iter.next(), None);

pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<'_, T>

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where nodes are visited end to start and children are visited in reverse insertion order.

i.e. node.end -> second child -> first child -> node.start

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.reverse_traverse(&arena);
assert_eq!(iter.next(), Some(NodeEdge::End(n1)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));
assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));
assert_eq!(iter.next(), None);

let traverse = n1.traverse(&arena).collect::<Vec<_>>();
let mut reverse = n1.reverse_traverse(&arena).collect::<Vec<_>>();
reverse.reverse();
assert_eq!(traverse, reverse);

pub fn detach<T>(self, arena: &mut Arena<T>)

Detaches a node from its parent and siblings. Children are not affected.

Examples

// arena
// `-- (implicit)
//     `-- 1
//         |-- 1_1
//         |   `-- 1_1_1
//         |-- 1_2 *
//         `-- 1_3

n1_2.detach(&mut arena);
// arena
// |-- (implicit)
// |   `-- 1
// |       |-- 1_1
// |       |   `-- 1_1_1
// |       `-- 1_3
// `-- (implicit)
//     `-- 1_2

assert!(arena[n1_2].parent().is_none());
assert!(arena[n1_2].previous_sibling().is_none());
assert!(arena[n1_2].next_sibling().is_none());

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn append<T>(self, new_child: NodeId, arena: &mut Arena<T>)

Appends a new child to this node, after existing children.

Panics

Panics if:

• the given new child is self

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.append(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.append(n1_2, &mut arena);
let n1_3 = arena.new_node("1_3");
n1.append(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_append<T>(
    self,
    new_child: NodeId,
    arena: &mut Arena<T>
) -> Result<(), NodeError>

Appends a new child to this node, after existing children.

Failures

• Returns NodeError::AppendSelf error if the given new child is self.
• Returns NodeError::Removed error if the given new child or self is removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_append(n1, &mut arena).is_err());

let n1_1 = arena.new_node("1_1");
assert!(n1.checked_append(n1_1, &mut arena).is_ok());

pub fn prepend<T>(self, new_child: NodeId, arena: &mut Arena<T>)

Prepends a new child to this node, before existing children.

Panics

Panics if:

• the given new child is self, or
• the current node or the given new child was already removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.prepend(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.prepend(n1_2, &mut arena);
let n1_3 = arena.new_node("1_3");
n1.prepend(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_3
//     |-- 1_2
//     `-- 1_1

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), None);

pub fn checked_prepend<T>(
    self,
    new_child: NodeId,
    arena: &mut Arena<T>
) -> Result<(), NodeError>

Prepends a new child to this node, before existing children.

Failures

• Returns NodeError::PrependSelf error if the given new child is self.
• Returns NodeError::Removed error if the given new child or self is removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_prepend(n1, &mut arena).is_err());

let n1_1 = arena.new_node("1_1");
assert!(n1.checked_prepend(n1_1, &mut arena).is_ok());

pub fn insert_after<T>(self, new_sibling: NodeId, arena: &mut Arena<T>)

Inserts a new sibling after this node.

Panics

Panics if:

• the given new sibling is self, or
• the current node or the given new sibling was already removed.

Examples

// arena
// `-- 1
//     |-- 1_1
//     `-- 1_2

let n1_3 = arena.new_node("1_3");
n1_1.insert_after(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_3
//     `-- 1_2

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), None);

pub fn checked_insert_after<T>(
    self,
    new_sibling: NodeId,
    arena: &mut Arena<T>
) -> Result<(), NodeError>

Inserts a new sibling after this node.

Failures

• Returns NodeError::InsertAfterSelf error if the given new sibling is self.
• Returns NodeError::Removed error if the given new sibling or self is removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_insert_after(n1, &mut arena).is_err());

let n2 = arena.new_node("2");
assert!(n1.checked_insert_after(n2, &mut arena).is_ok());

pub fn insert_before<T>(self, new_sibling: NodeId, arena: &mut Arena<T>)

Inserts a new sibling before this node.

Panics

Panics if:

• the given new sibling is self, or
• the current node or the given new sibling was already removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.append(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.append(n1_2, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     `-- 1_2

let n1_3 = arena.new_node("1_3");
n1_2.insert_before(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_3
//     `-- 1_2

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), None);

pub fn checked_insert_before<T>(
    self,
    new_sibling: NodeId,
    arena: &mut Arena<T>
) -> Result<(), NodeError>

Inserts a new sibling before this node.

Failures

• Returns NodeError::InsertBeforeSelf error if the given new sibling is self.
• Returns NodeError::Removed error if the given new sibling or self is removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_insert_before(n1, &mut arena).is_err());

let n2 = arena.new_node("2");
assert!(n1.checked_insert_before(n2, &mut arena).is_ok());

pub fn remove<T>(self, arena: &mut Arena<T>)

Removes a node from the arena.

Children of the removed node will be inserted to the place where the removed node was.

Please note that the node will not be removed from the internal arena storage, but marked as removed. Traversing the arena returns a plain iterator and contains removed elements too.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     |   |-- 1_2_1
//     |   `-- 1_2_2
//     `-- 1_3

n1_2.remove(&mut arena);

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2_1));
assert_eq!(iter.next(), Some(n1_2_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn remove_subtree<T>(self, arena: &mut Arena<T>)

Removes a node and its descendants from the arena.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     |   |-- 1_2_1
//     |   `-- 1_2_2
//     `-- 1_3

n1_2.remove_subtree(&mut arena);

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

Trait Implementations

impl Clone for NodeId

fn clone(&self) -> NodeId

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for NodeId

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

Formats the value using the given formatter.

impl Display for NodeId

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

Formats the value using the given formatter.

impl From<NodeId> for Index

fn from(node_id: NodeId) -> Index

Performs the conversion.

impl Hash for NodeId

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

impl<T> Index<NodeId> for Arena<T>

type Output = Node<T>

The returned type after indexing.

fn index(&self, node: NodeId) -> &Node<T>

Performs the indexing (container[index]) operation.

impl<T> IndexMut<NodeId> for Arena<T>

fn index_mut(&mut self, node: NodeId) -> &mut Node<T>

Performs the mutable indexing (container[index]) operation.

impl Ord for NodeId

fn cmp(&self, other: &NodeId) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl PartialEq<NodeId> for NodeId

fn eq(&self, other: &NodeId) -> bool

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

fn ne(&self, other: &NodeId) -> bool

This method tests for !=.

impl PartialOrd<NodeId> for NodeId

fn partial_cmp(&self, other: &NodeId) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Copy for NodeId

impl Eq for NodeId

impl StructuralEq for NodeId

impl StructuralPartialEq for NodeId