Struct Arena 

pub struct Arena<T> { /* private fields */ }

An Arena structure containing certain Nodes.

Implementations

impl<T> Arena<T>

pub fn new() -> Arena<T>

Creates a new empty Arena.

Examples found in repository

examples/simple.rs (line 5)

pub fn main() {
    // 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).count(), 2);
}

examples/tree-macro.rs (line 4)

fn main() {
    let mut arena = Arena::new();

    // It works with existing nodes
    let root_node = arena.new_node("my root node");
    tree!(
        &mut arena,
        root_node => {
            "1",
            "2" => {
                "2_1" => { "2_1_1" },
                "2_2",
            },
            "3" => {},
        }
    );

    println!("{}", root_node.debug_pretty_print(&arena));

    // It can also create a root node for you!
    let root_node = tree!(
        &mut arena,
        "my root node, but automagically created" => {
            "1",
            "2" => {
                "2_1" => { "2_1_1" },
                "2_2",
            },
            "3",
        }
    );

    println!("{}", root_node.debug_pretty_print(&arena));
}

pub fn with_capacity(n: usize) -> Self

Creates a new empty Arena with enough capacity to store n nodes.

pub fn capacity(&self) -> usize

Returns the number of nodes the arena can hold without reallocating.

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

Reserves capacity for additional more nodes to be inserted.

The arena may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

pub fn get_node_id(&self, node: &Node<T>) -> Option<NodeId>

Retrieves the NodeId corresponding to a Node in the Arena.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let node = arena.get(foo).unwrap();

let node_id = arena.get_node_id(node).unwrap();
assert_eq!(*arena[node_id].get(), "foo");

pub fn get_node_id_at(&self, index: NonZeroUsize) -> Option<NodeId>

Retrieves the NodeId corresponding to the Node at index in the Arena, if it exists.

Note: We use 1 based indexing, so the first element is at 1 and not 0.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let node = arena.get(foo).unwrap();
let index: NonZeroUsize = foo.into();

let new_foo = arena.get_node_id_at(index).unwrap();
assert_eq!(foo, new_foo);

foo.remove(&mut arena);
let new_foo = arena.get_node_id_at(index);
assert!(new_foo.is_none(), "must be none if the node at the index doesn't exist");

pub fn new_node(&mut self, data: T) -> NodeId

Creates a new node from its associated data.

Panics

Panics if the arena already has usize::max_value() nodes.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");

assert_eq!(*arena[foo].get(), "foo");

Examples found in repository

examples/simple.rs (line 8)

pub fn main() {
    // 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).count(), 2);
}

examples/tree-macro.rs (line 7)

fn main() {
    let mut arena = Arena::new();

    // It works with existing nodes
    let root_node = arena.new_node("my root node");
    tree!(
        &mut arena,
        root_node => {
            "1",
            "2" => {
                "2_1" => { "2_1_1" },
                "2_2",
            },
            "3" => {},
        }
    );

    println!("{}", root_node.debug_pretty_print(&arena));

    // It can also create a root node for you!
    let root_node = tree!(
        &mut arena,
        "my root node, but automagically created" => {
            "1",
            "2" => {
                "2_1" => { "2_1_1" },
                "2_2",
            },
            "3",
        }
    );

    println!("{}", root_node.debug_pretty_print(&arena));
}

pub fn count(&self) -> usize

Returns the number of nodes in the arena, including removed nodes.

Removed nodes are still counted because they remain in the internal storage. Use iter() with Node::is_removed() to count only live nodes.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let _bar = arena.new_node("bar");
assert_eq!(arena.count(), 2);

foo.remove(&mut arena);
// The removed node is still counted.
assert_eq!(arena.count(), 2);

pub fn is_empty(&self) -> bool

Returns true if arena has no nodes, false otherwise.

Examples

let mut arena = Arena::new();
assert!(arena.is_empty());

let foo = arena.new_node("foo");
assert!(!arena.is_empty());

foo.remove(&mut arena);
assert!(!arena.is_empty());

pub fn get(&self, id: NodeId) -> Option<&Node<T>>

Returns a reference to the node with the given id if in the arena.

Returns None if not available.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("foo"));

Note that this does not check whether the given node ID is created by the arena.

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let bar = arena.new_node("bar");
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("foo"));

let mut another_arena = Arena::new();
let _ = another_arena.new_node("Another arena");
assert_eq!(another_arena.get(foo).map(|node| *node.get()), Some("Another arena"));
assert!(another_arena.get(bar).is_none());

pub fn get_mut(&mut self, id: NodeId) -> Option<&mut Node<T>>

Returns a mutable reference to the node with the given id if in the arena.

Returns None if not available.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("foo"));

*arena.get_mut(foo).expect("The `foo` node exists").get_mut() = "FOO!";
assert_eq!(arena.get(foo).map(|node| *node.get()), Some("FOO!"));

pub fn iter(&self) -> Iter<'_, Node<T>>

Returns an iterator of all nodes in the arena in storage-order.

Note that this iterator returns also removed elements, which can be tested with the is_removed() method on the node.

Examples

let mut arena = Arena::new();
let _foo = arena.new_node("foo");
let _bar = arena.new_node("bar");

let mut iter = arena.iter();
assert_eq!(iter.next().map(|node| *node.get()), Some("foo"));
assert_eq!(iter.next().map(|node| *node.get()), Some("bar"));
assert_eq!(iter.next().map(|node| *node.get()), None);

let mut arena = Arena::new();
let _foo = arena.new_node("foo");
let bar = arena.new_node("bar");
bar.remove(&mut arena);

let mut iter = arena.iter();
assert_eq!(iter.next().map(|node| (*node.get(), node.is_removed())), Some(("foo", false)));
assert_eq!(iter.next().map_or(false, |node| node.is_removed()), true);
assert_eq!(iter.next().map(|node| (*node.get(), node.is_removed())), None);

pub fn iter_node_ids(&self) -> impl Iterator<Item = NodeId> + '_

Returns an iterator of NodeIds of all non-removed nodes in the arena in storage-order.

Unlike iter(), this skips removed nodes and yields NodeIds instead of &Node<T>.

Examples

let mut arena = Arena::new();
let foo = arena.new_node("foo");
let bar = arena.new_node("bar");
let baz = arena.new_node("baz");
bar.remove(&mut arena);

let ids: Vec<_> = arena.iter_node_ids().collect();
assert_eq!(ids, vec![foo, baz]);

pub fn iter_mut(&mut self) -> IterMut<'_, Node<T>>

Returns a mutable iterator of all nodes in the arena in storage-order.

Note that this iterator returns also removed elements, which can be tested with the is_removed() method on the node.

Example

let arena: &mut Arena<i64> = &mut Arena::new();
let a = arena.new_node(1);
let b = arena.new_node(2);
assert!(a.checked_append(b, arena).is_ok());

for node in arena.iter_mut() {
    let data = node.get_mut();
    *data = data.wrapping_add(4);
}

let node_refs = arena.iter().map(|i| i.get().clone()).collect::<Vec<_>>();
assert_eq!(node_refs, vec![5, 6]);

pub fn clear(&mut self)

Clears all the nodes in the arena, but retains its allocated capacity.

Note that this does not marks all nodes as removed, but completely removes them from the arena storage, thus invalidating all the node ids that were previously created.

Any attempt to call the is_removed() method on the node id will result in panic behavior.

pub fn as_slice(&self) -> &[Node<T>]

Returns a slice of the inner nodes collection.

Note that this does not return root elements, it simply returns a slice into the internal representation of the arena.

Trait Implementations

impl<T: Clone> Clone for Arena<T>

fn clone(&self) -> Arena<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Arena<T>

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

Formats the value using the given formatter.

impl<T> Default for Arena<T>

fn default() -> Self

Returns the “default value” for a type.

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<T: PartialEq> PartialEq for Arena<T>

fn eq(&self, other: &Arena<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for Arena<T>

impl<T> StructuralPartialEq for Arena<T>