Crate indextree_ng

Arena based tree data structure

This is a fork of the indextree crate which allows to remove nodes. The original version was not capable of removing nodes as the initial idea was to drop all nodes at the same time if the lifetime of the underlying memory arena has ended.

The arena tree structure is using a single Vec, a HashMap and numerical identifiers. Every node holds an id which is mapped to an index of the vector via the HashMap. This allows to drop single nodes before the lifetime of the arena hash ended.

There is no RefCell and mutability is handled in a way much more idiomatic to Rust through unique (&mut) access to the arena.

Example usage

use indextree_ng::Arena;

// Create a new arena
let arena = &mut Arena::new();

// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);

// Append b to a
a.append(b, arena);
assert_eq!(b.ancestors(arena).into_iter().count(), 2);

//Access a node
assert_eq!(arena[b].data, 2);

// Remove a node
arena.remove_node(a);
assert_eq!(b.ancestors(arena).into_iter().count(), 1);

Re-exports

pub use self::IndexTreeError::*;

Structs

Ancestors

An iterator of references to the ancestors a given node.

Arena

An Arena structure containing certain Nodes

Children

An iterator of references to the children of a given node.

Descendants

An iterator of references to a given node and its descendants, in tree order.

FollowingSiblings

An iterator of references to the siblings after a given node.

Node

A node within a particular Arena

NodeId

A node identifier within a particular Arena

PrecedingSiblings

An iterator of references to the siblings before a given node.

ReverseChildren

An iterator of references to the children of a given node, in reverse order.

ReverseTraverse

An iterator of references to a given node and its descendants, in reverse tree order.

Traverse

An iterator of references to a given node and its descendants, in tree order.

Enums

IndexTreeError

Use this for catching errors that can happen when using indextree_ng::Tree.

NodeEdge

Indicator if the node is at a start or endpoint of the tree