Как мне получить доступ к T в опции <T>, не вызывая ход?

Question

Я работаю над функцией вставки в реализации бинарного дерева поиска. Вот мой код:

pub struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

fn insert_at_root(mut root_node: Node, new_node: Node) -> Node { //not reference because root_node will be mutated
    if root_node.data > new_node.data { // value less than root
        if let Some(left) = root_node.left {
            insert_node(*left, new_node); // *left is a way to downcast box, i.e. *left = T from Box<T>
        }
        else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if root_node.data < new_node.data {
        if let Some(right) = root_node.right {
            insert_node(*right, new_node);
        }
        else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

fn insert_node(mut exist_node: Node, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left {
            insert_node(*left, new_node);
        }
        else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right {
            insert_node(*right, new_node);
        }
        else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}

У меня есть две функции вставки, поэтому я могу сохранить переменную с узлом root при вызове insert_at_node.

Моя текущая проблема - строка if let Some(left) = root_node.left { (и строка if let Some(right) = root_node.right {) в функции insert_at_root, которая, очевидно, вызывает движение. В результате я не могу вернуть root_node в конце insert_at_node:

error[E0382]: use of moved value: `root_node`
  --> src/lib.rs:34:5
   |
19 |         if let Some(left) = root_node.left {
   |                     ---- value moved here
...
34 |     root_node
   |     ^^^^^^^^^ value used here after partial move
   |
   = note: move occurs because value has type `std::boxed::Box<Node>`, which does not implement the `Copy` trait

error: aborting due to previous error

Цель этих строк - проверить, является ли дочерний узел left (или right) не None, в основном root_node.left != None. Есть ли способ достичь этого, не вызывая движения? Может быть, что-то со знаком != или ==.

Answer 1

Ваша проблема не в том, что вы проверяете, является ли left / right Some или None. Кстати, это можно сделать с помощью тестов .is_some() и .is_none().

. Проблема в том, что вы связываете переменную left с Node, который находится в Option. Таким образом вы перемещаете владение содержимым Option в переменную left.

В общем, если вы не хотите переносить владение, вам придется работать со ссылками. Когда переменная находится внутри Option, и вам нужно просмотреть ее как ссылку, вы должны преобразовать ее тип из Option<T> в Option<&T>. Когда вы заглядываете внутрь опции, это всего лишь ссылка, и поэтому она не перемещает владельца.

В Option доступны две функции, которые делают это преобразование: .as_ref() для преобразования в неизменяемая ссылка и .as_mut(), которая преобразуется в изменяемую ссылку. Поскольку вы хотите изменить содержимое left, вам нужна изменяемая ссылка, поэтому .as_mut() как то, что вы хотите.

Используя .as_mut(), вы получите left вместо ссылки на переменную. само по себе, поэтому право собственности не было передано.

Следующая проблема, которую вы получаете, заключается в том, что вы не можете передать ссылку в insert_node, поскольку сигнатура типа этой функции требует получить переменную вместо ссылки. При этом требуется передать владение внутри этой вспомогательной функции, чтобы она также не работала. Таким образом, мы конвертируем подпись insert_node в &mut Box<Node> вместо Node. Опять же, мы берем только ссылку, а не право собственности.

pub fn insert_at_root(mut root_node: Node, new_node: Node) -> Node {
    //not reference because root_node will be mutated
    if root_node.data > new_node.data {
        // value less than root
        if let Some(left) = root_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    } else if root_node.data < new_node.data {
        if let Some(right) = root_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

pub fn insert_node(exist_node: &mut Box<Node>, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    } else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}