構造体内のボックス化された要素を再構成する

Question

Rustのバイナリ検索ツリーの平衡型（AVL）バージョンのローテーションコードを実装しようとしていますが、再編成するノードの所有権を主張するのに問題があります。

マイ構造：

struct Tree<T> { 
    root: Box<TreeNode<T>>, 
    depth: usize, 
} 

enum TreeNode<T> { 
    Empty, 
    Node { 
     val: T, 
     left: Tree<T>, 
     right: Tree<T>, 
    }, 
} 

私は一種類のみ、またはOption Sを使用することができます知っています。これは少し上手そうだった。私は、ノードを再割り当てする方法を見つけることができません

T1, T2, T3 and T4 are subtrees. 
     z          y 
     /\         / \ 
     y T4  Right Rotate (z)   x  z 
    /\   - - - - - - - - -> /\ /\ 
    x T3        T1 T2 T3 T4 
    /\ 
    T1 T2 

：

私は回転を実装したい

。私は zノード（ Tree<T>ノード）を呼び出す rotate(&mut self, ...)メソッドを持っていますが、コンポーネントを取得するには、 TreeNodeを Nodeバージョンにキャストするために match *self.root {}を使用する必要があります。それはうまくいきますが、抽出した値を使って新しいノードを作成することはできません。私はこれをしようとした場合

：

fn insert(&mut self, ...) { 
    ... 
    // need to rotate 
    rotate(self, ...); 
} 

fn rotate(&mut ztree, ...) { 
    ztree.root = match *ztree.root { 
     // just re assign same tree to test... 
     TreeNode::Node {val, left, right} => 
       Box::new(TreeNode::Node {val: val, left: left, right: right}), 
     _ => panic!("meh"), 
    } ... 

私はこのエラーを取得します。

私はそれが私は箱入り TreeNode上の所有権を取得するために好きではありませんが、私は、私は新しい箱入り TreeNodeを割り当てるつもり錆を伝える方法がわからないと、古い TreeNodeは可能性があることを理解

| 
171 |    ztree.root = match *ztree.root { 
    |         ^^^^^ cannot move out of borrowed content 
172 |     TreeNode::Node {val, left, right} => 
    |         --- ---- ----- ...and here (use `ref right` or `ref mut right`) 
    |         | | 
    |         | ...and here (use `ref left` or `ref mut left`) 
    |         hint: to prevent move, use `ref val` or `ref mut val` 

ローカルで請求することができます。

私がself.rootを新しいボックスに再割り当てしようとしていることを知っているので、ちょうどうまく動作するようにしようとすると、前のボックスと参照されたヒープ構造体は割り当てを解除する必要があります。

Answer 1

Rust がの場合、ztree.rootの値を置き換えると信じているとします。次に書くことができる

fn rotate(&mut ztree, ...) { 
    let locally_owned = ztree.root (and I promise to give it back); 
    // Now, ztree.root is in some undefined state. 
    // Thats OK though, because I promise to fix it before anyone looks! 

    let local_new_value = match locally_owned { 
     // just re assign same tree to test... 
     TreeNode::Node {val, left, right} => 
       Box::new(TreeNode::Node {val: val, left: left, right: right}), 
     // Looks safe-ish, because the whole program will crash, 
     // so the programmer might expect that no one 
     // will see the undefined value of ztree.root 
     // (in fact, there would be problems when the destructor 
     // of ztree.root is called in the panic) 
     _ => panic!("meh"), 
    } 
    // FIXED IT! Put a value back into ztree.root 
    ztree.root = local_new_value; 
} 

これは正常に見えます。しかし、panic("meh")をいくつかのreturn文で置き換えたとします。

ztree.root = Box::new(TreeNode::Empty); 
// Returns without replacing the value of ztree.root 
// because ztree.root is Empty 
rotate(&mut ztree); 
// Now ztree.root is in a undefined state 
rotate(&mut ztree); // So something bad happens here 

基本的に、コンパイラはあなたがztree.rootの値を交換するつもりが、ないコードパスが存在しないことにつながるものではないだけ、ということ自体を説得しなければならない。そして、あなたは、このようなコードを持っている可能性があり値は置き換えられません。これは複雑な方法です。このため、コンパイラにあなたがやろうとしていることをさせる方法はありません。

代わりに、問題を解決して解決することができます。古い値を置き換えるために新しい値を計算しようとするのではなく、実際の値を置き換えずに変更するだけで済みます。 let ref mut root: TreeNode<T> = *ztree.root;作品しかしmatch *ztree.root {...}にはないなぜあなたは迷っている場合は

fn rotate<T>(ztree: &mut Tree<T>) { 
    let ref mut root : TreeNode<T> = *ztree.root; 

    match root { 
     &mut TreeNode::Node {ref mut left, ref mut right, ..} => { 
      std::mem::swap(left, right); 
     }, 
     _ => unimplemented!(), 
    } 
} 

、私は本当にわからないが、それはおそらくthis issueで行うことがあります。これを行う方法の1つは、そうのようなstd::mem::swap（Playground）を使用しています。