iter-tree

此crate提供了一种简单的方法来在迭代器和树结构之间进行转换。这在构建解析器以将令牌流转换为令牌树时非常有用。

它扩展了迭代器，增加了两个函数

• into_tree 将迭代器转换为 Tree。

• into_tree_deque 将迭代器转换为 TreeDeque。

  要使用此功能，您必须启用 deque 功能标志。

这两种树类型都实现了 IntoIterator 特性。

用法

树创建是通过 Nesting 枚举控制的。此枚举有三个变体

• Nesting::Increase
  • 用于开始将迭代器的项目嵌套到新的节点中。
• Nesting::Maintain
  • 用于将项目保留在与前一个项目相同的节点中
• Nesting::Decrease
  • 用于返回到上一个节点以放置下一个项目。如果没有上一个分支，则创建一个新的父分支。

如果您想检查这类情况，可以使用以下示例中显示的深度计数器等技巧。

示例

use iter_tree::*;

let mut depth = 0;

let before = String::from("a+(b+c)+d");

let tree: Tree<char> = before.chars().into_tree(|&item: &char| match item {
    '(' => {
        depth += 1;
        Nesting::Increase
    }
    ')' => {
        depth -= 1;
        Nesting::Decrease
    }
    _ => Nesting::Maintain,
});

assert!(depth == 0);

println!("{tree:#?}");

let after: String = tree.into_iter().collect();

assert_eq!(before, after);

Node(
    [
        Leaf(
            'a',
        ),
        Leaf(
            '+',
        ),
        Node(
            [
                Leaf(
                    '(',
                ),
                Leaf(
                    'b',
                ),
                Leaf(
                    '+',
                ),
                Leaf(
                    'c',
                ),
                Leaf(
                    ')',
                ),
            ],
        ),
        Leaf(
            '+',
        ),
        Leaf(
            'd',
        ),
    ],
)

NestingFunction 函数

此外，您还可以创建一个实现 NestingFunction 特性的结构，以替换上一个示例中的闭包。

以下是应用此方法的示例

use iter_tree::*;

#[derive(Debug, Default)]
struct StackController<T> {
    stack: Vec<T>,
}

impl<T> StackController<T> {
    pub fn is_empty(&self) -> bool {
        self.stack.is_empty()
    }
}

impl NestingFunction<char> for &mut StackController<char> {
    fn direction(&mut self, item: &char) -> Nesting {
        let &c = item;
        match c {
            '<' | '(' => {
                self.stack.push(c);
                Nesting::Increase
            }
            '>' => {
                if !self.stack.is_empty() && self.stack.last().unwrap() == &'<' {
                    self.stack.pop();
                    Nesting::Decrease
                } else {
                    Nesting::Maintain
                }
            }
            ')' => {
                if !self.stack.is_empty() && self.stack.last().unwrap() == &'(' {
                    self.stack.pop();
                    Nesting::Decrease
                } else {
                    Nesting::Maintain
                }
            }
            _ => Nesting::Maintain,
        }
    }
}

let mut parser = StackController::default();

let td = "< ( < > ) >"
    .chars()
    .filter(|c| !c.is_whitespace())
    .into_tree(&mut parser);

assert!(parser.is_empty());
println!("{td:#?}");




let mut parser = StackController::default();

let td = "<(>)".chars().into_tree(&mut parser);

assert!(!parser.is_empty());
println!("{td:#?}");

接下来是什么？

对于此crate的未来目标包括但不限于

• 添加更多构建树的方法，例如例如一个 tree_map 和 tree_deque_map 方法，在将其包含在树中之前映射项目。

• 提供其他类型的树，特别是那些区分分支初始化和终止项的树。