Rust пытается обеспечить безопасность памяти, запрещая вам делать вещи, которые потенциально могут быть небезопасными. Поскольку этот анализ выполняется во время компиляции, компилятор может только рассуждать о подмножестве манипуляций, которые, как известно, безопасны.
В Русте, вы можете легко хранить либо ссылка на родитель (путем заимствования родителя, таким образом предотвращая мутацию) или списка дочерних узлов (по владеющим ими, что дает вам больше свободы), но не оба (без использования unsafe). Это особенно проблематично для вашей реализации addNode, которая требует измененного доступа к родительскому элементу данного узла. Однако, если вы храните указатель parent в качестве изменяемой ссылки, тогда, поскольку только одна изменяемая ссылка на конкретный объект может быть использована одновременно, единственный способ получить доступ к родительскому элементу будет через дочерний узел, и вы только иметь единственный дочерний узел, иначе у вас есть две изменяемые ссылки на один и тот же родительский узел.
Если вы хотите избежать небезопасного кода, есть много альтернатив, но все они потребуют некоторых жертв.
Самое простое решение - просто удалить поле parent. Мы можем определить отдельную структуру данных, чтобы помнить родителя узла, пока мы пересекаем дерево, а не сохраняем его в самом узле.
Во-первых, давайте определим Node:
#[derive(Debug)]
struct Node<T> {
data: T,
children: Vec<Node<T>>,
}
impl<T> Node<T> {
fn new(data: T) -> Node<T> {
Node { data: data, children: vec![] }
}
fn add_child(&mut self, child: Node<T>) {
self.children.push(child);
}
}
(я добавил data поле, потому что дерево не очень полезно без данных в узлах!)
Давайте теперь определим еще-структуру для отслеживания родителей, как мы перемещаемся:
#[derive(Debug)]
struct NavigableNode<'a, T: 'a> {
node: &'a Node<T>,
parent: Option<&'a NavigableNode<'a, T>>,
}
impl<'a, T> NavigableNode<'a, T> {
fn child(&self, index: usize) -> NavigableNode<T> {
NavigableNode {
node: &self.node.children[index],
parent: Some(self)
}
}
}
impl<T> Node<T> {
fn navigate<'a>(&'a self) -> NavigableNode<T> {
NavigableNode { node: self, parent: None }
}
}
Это решение работает хорошо, если вам не нужно мутировать дерево, как вы ориентируетесь, и вы можете сохранить родительский NavigableNode (что отлично работает для рекурсивного алгоритма, но не слишком хорошо работает, если вы хотите сохранить NavigableNode в какой-то другой структуре данных и сохранить его). Второе ограничение можно облегчить, используя что-то другое, кроме заимствованного указателя для хранения родителя; если вы хотите максимально типичность, вы можете использовать Borrow trait, чтобы прямые значения, заимствованные указатели, Box Э.С., Rc «S и т.д.
Теперь, давайте поговорим о zippers. В функциональном программировании молнии используются для «фокусировки» на конкретном элементе структуры данных (список, дерево, карта и т. Д.), Так что доступ к этому элементу занимает постоянное время, сохраняя при этом все данные этой структуры данных. Если вам нужно перемещаться по дереву и мутировать во время навигации, сохраняя при этом возможность перемещаться по дереву, вы можете превратить дерево в застежку-молнию и выполнить изменения через молнию.
Вот как мы могли бы реализовать молнию на Node определено выше:
#[derive(Debug)]
struct NodeZipper<T> {
node: Node<T>,
parent: Option<Box<NodeZipper<T>>>,
index_in_parent: usize,
}
impl<T> NodeZipper<T> {
fn child(mut self, index: usize) -> NodeZipper<T> {
// Remove the specified child from the node's children.
// A NodeZipper shouldn't let its users inspect its parent,
// since we mutate the parents
// to move the focused nodes out of their list of children.
// We use swap_remove() for efficiency.
let child = self.node.children.swap_remove(index);
// Return a new NodeZipper focused on the specified child.
NodeZipper {
node: child,
parent: Some(Box::new(self)),
index_in_parent: index,
}
}
fn parent(self) -> NodeZipper<T> {
// Destructure this NodeZipper
let NodeZipper { node, parent, index_in_parent } = self;
// Destructure the parent NodeZipper
let NodeZipper {
node: mut parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
} = *parent.unwrap();
// Insert the node of this NodeZipper back in its parent.
// Since we used swap_remove() to remove the child,
// we need to do the opposite of that.
parent_node.children.push(node);
let len = parent_node.children.len();
parent_node.children.swap(index_in_parent, len - 1);
// Return a new NodeZipper focused on the parent.
NodeZipper {
node: parent_node,
parent: parent_parent,
index_in_parent: parent_index_in_parent,
}
}
fn finish(mut self) -> Node<T> {
while let Some(_) = self.parent {
self = self.parent();
}
self.node
}
}
impl<T> Node<T> {
fn zipper(self) -> NodeZipper<T> {
NodeZipper { node: self, parent: None, index_in_parent: 0 }
}
}
Чтобы использовать эту молнию, вы должны иметь право собственности на корневой узел дерева. Соблюдая узлы, молния может перемещать вещи вокруг, чтобы избежать копирования или клонирования узлов. Когда мы перемещаем застежку-молнию, мы фактически отбрасываем старую застежку-молнию и создаем новую (хотя мы могли бы также сделать это, изменив self, но я подумал, что это было более понятно, плюс это позволяет вам цеплять вызовы методов).
Если указанные выше параметры не являются удовлетворительными, и вы должны абсолютно сохранить родительский узел в узле, то следующий лучшим вариантом является использование Rc<RefCell<Node<T>>>, чтобы обратиться к родителю и к детям. Rc разрешает совместное использование, но добавляет служебные данные для выполнения подсчета ссылок во время выполнения. RefCell обеспечивает внутреннюю изменчивость, но добавляет накладные расходы, чтобы отслеживать активные роли во время выполнения. See DK.'s answer для реализации с использованием Rc и RefCell.
В чем Ваш вопрос? – Shepmaster
Владение не выражается через типы в вашем текущем примере, вы намеревались написать 'std :: vector> children;'?Кроме того, почему деструктор «виртуальный»? Является ли это интерфейсом? –
Узел владеет своими дочерними элементами и принадлежит родительскому объекту. Я не хотел использовать больше шаблонов, чем необходимо. – nulleight