atree

支持节点删除的基于区域的树结构

一个基于区域的树结构，由一个自定义分配器（最终基于 Vec）支持，使得节点删除成为可能。除了基本的节点插入和删除操作外，还提供了多种不可变和可变迭代器，用于各种树遍历操作。

该crate中的大部分代码都是 unsafe 代码，除了可变迭代器，其中 unsafe 代码来自Rust核心实现的 IterMut。

API通用指南

该crate包含三个主要的 struct： Arena<T>、Token 和 Node<T>。 Arena<T> 提供了所有数据存储的区域。然后可以通过用 Token 索引 Arena<T> 来访问数据。Node<T> 是一个封装树上数据的容器。

一般来说，影响内存布局的方法，如分割和合并区域，或者创建和销毁节点的方法（无论现有树结构如何，如创建空闲节点），都在Arena<T>上定义。改变现有树结构的方法，如根据现有节点添加节点（例如append或insert_after）或分割和连接现有树，在Tokens上定义。

在迭代方面，可以从Token和Node<T>上的方法创建迭代器。有两种迭代器版本，一个是遍历标记的迭代器，另一个是节点引用的引用。两者都可以通过Token和Node<T>上的方法创建。然而，由于借用检查的规则，只有可变节点引用迭代器在Token上定义。

库特性标志

• serde：支持serde 1.x。可选特性/依赖。

使用示例

我们可以先初始化一个空区域，并在以后添加内容

use atree::Arena;

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

// create a tree in the arena
let data = "Indo-European";
let token = arena.new_node(data);
assert_eq!(arena.node_count(), 1)

上述操作的快捷方式

use atree::Arena;

let data = "Indo-European";
let (mut arena, token) = Arena::with_data(data);
assert_eq!(arena.node_count(), 1)

要向树中添加更多数据，请调用标记上的append方法（由于借用检查的限制，我们不能直接对节点执行此操作）。

use atree::Arena;

let root_data = "Indo-European";
let (mut arena, root_token) = Arena::with_data(root_data);
root_token.append(&mut arena, "Romance");
assert_eq!(arena.node_count(), 2);

要访问/修改树中的现有节点，我们可以使用索引或get/get_mut。

use atree::Arena;

let root_data = "Indo-European";
let (mut arena, root_token) = Arena::with_data(root_data);

// add some more stuff to the tree
let branch1 = root_token.append(&mut arena, "Romance");
let branch2 = root_token.append(&mut arena, "Germanic");
let branch3 = root_token.append(&mut arena, "Slavic");
let lang1 = branch2.append(&mut arena, "English");
let lang2 = branch2.append(&mut arena, "Swedish");
let lang3 = branch3.append(&mut arena, "Polish");

// Access data by indexing the arena by a token. This operation panics if the
// token is invalid.
assert_eq!(arena[branch3].data, "Slavic");

// Access data by calling "get" on the arena with a token.
assert_eq!(arena.get(lang1).unwrap().data, "English");

// We can also do so mutably (with "get" or through indexing). As you can
// see, calling the "get" functions is more verbose but you get to avoid
// surprise panic attacks (if you don't unwrap like I do here).
arena.get_mut(lang1).unwrap().data = "Icelandic";
assert_eq!(arena[lang1].data, "Icelandic");

// On the flip side, we can access the corresponding token if we already
// have the node
let branch3_node = &arena[branch3];
assert_eq!(branch3, branch3_node.token());

我们可以通过在标记或节点上调用迭代器来遍历元素。有关迭代器的列表，请参阅Token或Node<T>的文档。每个迭代器都有一个版本，该版本遍历标记而不是节点引用。有关详细信息，请参阅文档。

use atree::Arena;

let root_data = "Indo-European";
let (mut arena, root_token) = Arena::with_data(root_data);

// add some more stuff to the tree
let branch1 = root_token.append(&mut arena, "Romance");
let branch2 = root_token.append(&mut arena, "Germanic");
let branch3 = root_token.append(&mut arena, "Slavic");
let lang1 = branch2.append(&mut arena, "English");
let lang2 = branch2.append(&mut arena, "Swedish");
let lang3 = branch3.append(&mut arena, "Polish");

// Getting an iterator from a token and iterate
let children: Vec<_> = root_token.children(&arena).map(|x| x.data).collect();
assert_eq!(&["Romance", "Germanic", "Slavic"], &children[..]);

// Getting an iterator from a node reference (that is if you already have it
// around. To go out of your way to get the node reference before getting
// the iterator seems kind of dumb).
let polish = &arena[lang3];
let ancestors: Vec<_> = polish.ancestors(&arena).map(|x| x.data).collect();
assert_eq!(&["Slavic", "Indo-European"], &ancestors[..]);

// We can also iterate mutably. Unfortunately we can only get mutable
// iterators from the tokens but not from the node references because of
// borrow checking.
for lang in branch2.children_mut(&mut arena) {
    lang.data = "Not romantic enough";
}
assert_eq!(arena[lang1].data, "Not romantic enough");
assert_eq!(arena[lang2].data, "Not romantic enough");

要从区域中删除单个节点，请使用remove方法。这将断开节点所有子节点与树的连接（但不会从内存中删除它们）。

use atree::Arena;
use atree::iter::TraversalOrder;

// root node that we will attach subtrees to
let root_data = "Indo-European";
let (mut arena, root) = Arena::with_data(root_data);

// the Germanic branch
let germanic = root.append(&mut arena, "Germanic");
let west = germanic.append(&mut arena, "West");
let scots = west.append(&mut arena, "Scots");
let english = west.append(&mut arena, "English");

// detach the west branch from the main tree
let west_children = arena.remove(west);

// the west branch is gone from the original tree
let mut iter = root.subtree(&arena, TraversalOrder::Pre)
    .map(|x| x.data);
assert_eq!(iter.next(), Some("Indo-European"));
assert_eq!(iter.next(), Some("Germanic"));
assert!(iter.next().is_none());

// its children are still areound
let mut iter = west_children.iter().map(|&t| arena[t].data);
assert_eq!(iter.next(), Some("Scots"));
assert_eq!(iter.next(), Some("English"));
assert!(iter.next().is_none());

要从区域中拔除树，请调用区域上的uproot方法。请注意，它还将删除节点的所有后代。删除后，如果插入新数据，将重用“释放”的内存。

use atree::Arena;

let root_data = "Indo-European";
let (mut arena, root_token) = Arena::with_data(root_data);

// add some more stuff to the tree
let branch1 = root_token.append(&mut arena, "Romance");
let branch2 = root_token.append(&mut arena, "Germanic");
let branch3 = root_token.append(&mut arena, "Slavic");
let lang1 = branch2.append(&mut arena, "English");
let lang2 = branch2.append(&mut arena, "Swedish");
let lang3 = branch3.append(&mut arena, "Polish");

assert_eq!(arena.node_count(), 7);
arena.uproot(branch2);  // boring languages anyway
assert_eq!(arena.node_count(), 4);