Доступ к значениям во вложенной структуре в штучной упаковке

Я новичок в Rust и хочу реализовать AVL-Tree.

Я использую следующее перечисление для представления своего дерева:

enum AvlTree<T> {
    Leaf,
    Node {
        left: Box<AvlTree<T>>,
        right: Box<AvlTree<T>>,
        value: T
    }
}

При реализации одной из функций баланса у меня возникают проблемы с владением и заимствованием.

Я пытаюсь написать функцию, которая принимает AvlTree<T> и возвращает другой AvlTree<T>. Моя первая попытка была примерно такой:

fn balance_ll(tree: AvlTree<T>) -> AvlTree<T> {
    if let AvlTree::Node {left: t, right: u, value: v} = tree {
        if let AvlTree::Node {left: ref tl, right: ref ul, value: ref vl} = *t {
            AvlTree::Leaf // Return a new AvlTree here
        } else {
            tree
        }
    } else {
        tree
    }
}

Даже в этом минимальном примере компилятор возвращает ошибку:

error[E0382]: use of partially moved value: `tree`             
  --> avl.rs:67:17             
   |                           
63 |         if let AvlTree::Node {left: t, right: u, value: v} = tree {                                                       
   |                                     - value moved here    
...                            
67 |                 tree      
   |                 ^^^^ value used here after move           
   |                           
   = note: move occurs because `(tree:AvlTree::Node).left` has type `std::boxed::Box<AvlTree<T>>`, which does not implement the `Copy` trait

Я думаю, я правильно понимаю сообщение об ошибке, поскольку деструктуризация AvlTree::Node отнимет право собственности на пример дерева. Как я могу этого избежать? Я уже пробовал разные вещи и (де-) ссылки на tree-переменную только для того, чтобы столкнуться с большим количеством ошибок.

Кроме того, я хочу использовать некоторые извлеченные значения, такие как u, tl и vl в новой структуре. Возможно ли это, и не могли бы вы предоставить минимальный пример, делающий именно это? Мне не нужен доступ к старому дереву после выполнения функции.


enums rust ownership avl-tree
person lschuermann    schedule 04.07.2017    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Я думаю, я правильно понимаю сообщение об ошибке, поскольку деструктуризация AvlTree::Node отнимет право собственности на пример дерева.

да. Если вам все еще нужно иметь возможность использовать tree и после этого, вам нужно будет либо сделать его копию:

#[derive(Clone)]
enum AvlTree<T> {...}

fn balance_ll<T: Clone>(tree: AvlTree<T>) -> AvlTree<T> {
    let copy = tree.clone();

    if let AvlTree::Node { left: t, right: u, value: v } = tree {
        if let AvlTree::Node { left: ref tl, right: ref ul, value: ref vl } = *t {
            AvlTree::Leaf // Return a new AvlTree here
        } else {
            copy
        }
    } else {
        tree
    }
}

или используйте вспомогательную функцию, которая быстро освобождает его от владения - но я не думаю, что это возможно без шаблонов ящиков:

#![feature(box_patterns)]

impl<T> AvlTree<T> {
    fn is_left_node(&self) -> bool {
        if let &AvlTree::Node { left: ref t, right: ref u, value: ref v } = self {
            if let &box AvlTree::Node { left: ref tl, right: ref ul, value: ref vl } = t {
                true
            } else {
                false
            }
        } else {
            false
        }
    }
}

fn balance_ll<T>(tree: AvlTree<T>) -> AvlTree<T> {
    if tree.is_left_node() {
        AvlTree::Leaf
    } else {
        tree
    }
}

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

person ljedrz    schedule 04.07.2017