时间戳

首页 > 解决方案 > 在 rust 中建模分层树

rust - 在 rust 中建模分层树

问题描述

我正在尝试为 UI 库建模一个结构，其中存在一个 ViewNode，该 ViewNode 拥有一个拥有 LayoutNode 的 RenderNode。这些结构应该同时形成三棵不同的树。一个视图树、一个渲染树和一个布局树。

有没有任何方法可以在不使用 Rc 的情况下对这种所有权进行建模？我不想使用 Rc<> 因为从我的角度来看所有权是明确的，树不应该拥有它们的孩子（ViewNode 除外），包装器是所有者。每一层也应该能够被拉出到一个库中，我不想强​​迫库的用户使用 Rc<>。

以下是我想要做但不起作用的事情。我应该以不同的方式解决这个问题吗？

#[derive(Debug)]
struct LayoutNode<'a> {
    // .. Some fields
    children: Vec<&'a LayoutNode<'a>>,
}

#[derive(Debug)]
struct RenderNode<'a> {
    // .. Some fields
    layout_node: LayoutNode<'a>,
    children: Vec<&'a RenderNode<'a>>,
}

#[derive(Debug)]
struct ViewNode<'a> {
    // .. Some fields
    render_node: RenderNode<'a>,
    children: Vec<ViewNode<'a>>,
}

fn make_tree<'a>() -> ViewNode<'a> {
    let layout_child = LayoutNode { children: vec![] };
    let layout = LayoutNode { children: vec![&layout_child] };

    let render_child = RenderNode { layout_node: layout_child, children: vec![] };
    let render = RenderNode { layout_node: layout, children: vec![&render_child] };

    let view_child = ViewNode { render_node: render_child, children: vec![] };
    let view = ViewNode { render_node: render, children: vec![view_child] };

    view
}


fn main() {
    println!("{:?}", make_tree())
}

标签： rust

解决方案

您可以使用使用索引而不是引用计数指针的内存领域。

以索引树为例：

pub struct NodeId {
    index: usize,
}

pub struct Node<T> {
    parent: Option<NodeId>,
    previous_sibling: Option<NodeId>,
    next_sibling: Option<NodeId>,
    first_child: Option<NodeId>,
    last_child: Option<NodeId>,
    removed: bool,

    /// The actual data which will be stored within the tree
    pub data: T,
}

pub struct Arena<T> {
    nodes: Vec<Node<T>>,
}

该NodeId结构是一个简单的整数索引。

节点包含对节点关闭的引用（parent、previous_sibling等），以便于遍历。

这种方法的一个缺点是它与手动内存管理非常相似，因为您需要确保正确添加/删除节点以避免悬空引用。由于这个原因，在树中添加/删除节点时indextree有很多错误检查。

您可能还想看看petgraph：虽然这是 aGraph而不是 a，但Tree您可以将其用作树。

推荐阅读