Моделирование слоистого дерева в ржавчине

Question

Я пытаюсь смоделировать структуру для библиотеки пользовательского интерфейса, где существует ViewNode, которому принадлежит RenderNode, которому принадлежит LayoutNode.Эти структуры должны одновременно образовывать три разных дерева.ViewTree, RenderTree и Layout tree.

Есть ли способ моделирования этого владения без использования 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())
}

Answer 1

Вы можете использовать арену памяти, которая использует индексы вместо указателей с подсчетом ссылок.

Используя indextree в качестве примера:

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 :Хотя это Graph вместо Tree, вы можете использовать его как дерево.