tree-cursor

状态

据我所知，它功能齐全，但存在潜在的可靠性问题，我需要更仔细地研究。请随意使用，但要做好准备，可能会出现潜在的不可靠性。文档也需要做一些工作。

lib.rs:

摘要

这个包提供了一个简单、非侵入式的树游标，支持无需 Cell/RefCell 的节点修改。

可靠性

简而言之：我不知道这个包是否可靠。我 认为 它是，但在使用之前您仍然应该自己检查。

当前的实现使用不安全代码来绕过借用检查器的严格性。到目前为止，我还没有正式证明它是内存安全的，特别是在恶意代码存在的情况下。我已经尽力编写了对抗性测试，并将继续研究边缘情况，直到我个人满意为止，但我可能需要更好地理解借用检查器才能正式证明它。

概念

为了本包的目的...

• 一棵树有且只有一个根节点（没有空树）
• 每个节点可以有零个或多个子节点
• "向上"是指向根的方向
• "向下"是指离根的方向
• 在任何时刻，游标都恰好有一个 活动 的节点，也称为游标的 位置

导游

让我们看看一个简单的树以及如何使用游标遍历它。

use tree_cursor::cursor::TreeCursor;
use tree_cursor::prelude::*;

struct Node(&'static str, Vec<Node>);

// This trait impl is used by TreeCursor::down to determine the next child
// to visit. You can create a TreeCursor for something that doesn't
// implement Down; you just won't be able to call TreeCursor::down.
impl Down for Node {
    fn down(&self, idx: usize) -> Option<&Self> {
        // idx starts at 0 when we visit this node going downward and
        // increments every time we visit it going upward. This allows us
        // to visit each child in order by going back up to this node after
        // each one.
        self.1.get(idx)
    }
}

let foobar = Node("foo", vec![
    Node("bar", vec![]),
    Node("zup", vec![]),
]);
// foobar is a tree; its root, "foo", has two children, named "bar" and
// "zup".

let mut cur = TreeCursor::new(&foobar);
assert_eq!(cur.get().0, "foo"); // The cursor starts at the root, "foo".
// TreeCursor::get() returns a reference to the active node.

assert!(cur.down());
// TreeCursor::down returns true if the position actually moved.
assert_eq!(cur.get().0, "bar");

assert!(!cur.down());
// "bar" has no children so we can't move the cursor down.

assert!(cur.up());
assert_eq!(cur.get().0, "foo"); // The cursor is at the root again.

assert!(cur.down());
assert_eq!(cur.get().0, "zup");

assert!(cur.up());
assert_eq!(cur.get().0, "foo"); // Back at the root.

assert!(!cur.down()); // No more children to visit.
assert!(!cur.up()); // The root has no parent.

当游标被创建时，它的初始位置在树的根。 down 和 up 是两种重新定位游标的方法。除了 down 之外，还有其他几种方法可以向下移动树；通常，当完全遍历树时使用 down，正如我们刚才看到的。如果你事先不知道树的形状，以下是如何进行完全遍历的两种方法：

#
#
#
#
fn process_tree_pre_order(root: &Node) {
    let mut cur = TreeCursor::new(root);
    'outer: loop {
        process_node(cur.get());
        while !cur.down() {
            if !cur.up() { break 'outer; }
        }
    }
}

fn process_tree_post_order(root: &Node) {
    let mut cur = TreeCursor::new(root);
    loop {
        while cur.down() { }
        process_node(cur.get());
        if !cur.up() { break; }
    }
}

当你需要更复杂的行为或者当节点的子节点没有特定顺序时，你可以使用 down_map 方法，传递一个闭包来确定要访问的下一个子节点。

可变性和节点引用

TreeCursor 是树游标的不可变版本，意味着它持有对树的共享引用，防止你在游标超出作用域之前修改树。如果你需要修改树，请使用 TreeCursorMut，它为你提供了对活动节点的可变引用。