Valeurs d'accès dans une structure imbriquée en boîte

Question

Je suis assez nouveau pour Rust et je veux implémenter un AVL-Tree.

J'utilise le ENUM suivant pour représenter mon arbre:

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

Lors de la mise en œuvre l'un des balanciers fonctions, je suis confronté à des problèmes de propriété et d'emprunt.

J'essaye d'écrire une fonction, qui prend un AvlTree<T> et renvoie un autre AvlTree<T>. Ma première tentative a été quelque chose comme ceci:

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 
    } 
} 

Même avec cet exemple minimal, le compilateur renvoie une erreur:

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     

Je pense, je comprends le message d'erreur correctement, dans ce destructuration le AvlTree::Node enlèvera la propriété de l'exemple d'arbre. Comment puis-je empêcher cela? J'ai déjà essayé plusieurs choses et (dé) référencer la variable tree uniquement pour faire face à plus d'erreurs.

En outre, je veux utiliser certaines des valeurs extraites comme u, tl et vl dans la nouvelle structure. Est-ce possible et pourriez-vous fournir un exemple minimal en faisant exactement cela? Je n'ai pas besoin d'accéder à l'ancien arbre après l'exécution de la fonction.

Answer 1

I think, I'm understanding the error message correctly, in that destructuring the AvlTree::Node will take away the ownership of the tree example.

Oui. Si vous avez encore besoin de pouvoir utiliser tree après, vous devrez soit faire une copie de celui-ci:

#[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 
    } 
} 

ou utiliser une fonction d'assistance qui libère rapidement sa propriété - mais je ne pense pas qu'il est possible sans motifs de la boîte:

#![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 
    } 
} 

Puisque vous voulez peut-être utiliser les valeurs déstructurés vous préféreront probablement la variante clone, mais peut-être l'autre vous donnera quelques idées supplémentaires.