녹에서 나무의 노드 변경

Question

주어진 트리 구조의 복사본을 반환하지만 특정 인덱스에서 노드가 변경된 함수를 작성하려고합니다. 여기에 지금까지 무엇을 가지고 :

#[derive(Clone)] 
pub enum Node { 
    Value(u32), 
    Branch(u32, Box<Node>, Box<Node>), 
} 

fn main() { 
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3))); 
    zero_node(&root, 2); 
} 

pub fn zero_node (tree: &Node, node_index: u8) -> Node { 

    let mut new_tree = tree.clone(); 

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 { 
     if (node_index == node_count) { 
      match node { 
       &mut Node::Value(_) => { *node = Node::Value(0); }, 
       &mut Node::Branch(_, ref mut left, ref mut right) => { *node = Node::Branch(0, *left, *right); } 
      } 
      node_count 
     } else { 
      match node { 
       &mut Node::Value(val) => {1}, 
       &mut Node::Branch(_, ref mut left, ref mut right) => { 
        let count_left = zero_rec(&**left, node_count + 1, node_index); 
        let count_right = zero_rec(&**right, node_count + 1 + count_left, node_index); 
        count_left + count_right + 1 
       } 
      } 
     } 
    } 

    zero_rec(&new_tree, 0, node_index); 

    new_tree 

} 

http://is.gd/YdIm0g

내가 좋아하는 오류에서 나의 방법을 작동하지 수

: ""로 변경할 수 불변 빌려 컨텐츠를 빌릴 수 없습니다 "를 빌려 밖으로 이동할 수 없습니다 함유량".

원본을 기반으로 처음부터 새 트리를 만들고 프로세스의 한 노드를 변경할 수 있습니다. 그러나 나는 빌리 체커와 함께이 싸움에서 승리하는 방법을 이해하고 싶습니다.

Answer 1

이 코드는 컴파일 : 내가 만든

#[derive(Clone)] 
pub enum Node { 
    Value(u32), 
    Branch(u32, Box<Node>, Box<Node>), 
} 

fn main() { 
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3))); 
    zero_node(&root, 2); 
} 

pub fn zero_node (tree: &Node, node_index: u8) -> Node { 

    let mut new_tree = tree.clone(); 

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 { 
     if node_index == node_count { 
      match node { 
       &mut Node::Value(ref mut val) => { *val = 0; }, 
       &mut Node::Branch(ref mut val, _, _) => { *val = 0; } 
      } 
      node_count 
     } else { 
      match node { 
       &mut Node::Value(_) => {1}, 
       &mut Node::Branch(_, ref mut left, ref mut right) => { 
        let count_left = zero_rec(&mut **left, node_count + 1, node_index); 
        let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index); 
        count_left + count_right + 1 
       } 
      } 
     } 
    } 

    zero_rec(&mut new_tree, 0, node_index); 

    new_tree 

} 

변화가 있었다 :

• &new_tree → &mut new_tree 및 &**left → &mut **left 등 : 방법은 (AN &mut T 참조가 &mut 연산자를 함께 만들 즉 mut이 필요합니다). 이 경우 cannot borrow immutable borrowed content as mutable 오류를 수정하려면
• node_index == node_count 브랜치를 변경하여 직접 덮어 쓰기하지 말고 값을 직접 변경해야합니다. 이것은 어떤 움직임도 전혀하지 않음으로써 cannot move out of borrowed content 오류를 수정합니다.

덮어 쓰기 실제로 새 값에 스왑, std::mem::replace의 신중한 사용을 달성 할 수있다 (예를 들어 Value(0) 그 만들 저렴하기 때문에)을 left 및 right 참조하십시오. replace 함수는 이전에 존재했던 값, 즉 left 및 right 안에 정확히 새 분기를 만드는 데 필요한 값을 반환합니다. 관련 match 팔이 변경 보이는 비트 같은 :

&mut Node::Branch(_, ref mut left, ref mut right) => { 
    let l = mem::replace(left, Box::new(Node::Value(0))); 
    let r = mem::replace(right, Box::new(Node::Value(0))); 
    *node = Node::Branch(0, l , r); 
} 

는 (파일의 상단에 use std::mem;을 추가 가졌어요.)는 새로운 오류 안타 그러나

:

<anon>:25:9: 25:39 error: cannot assign to `*node` because it is borrowed 
<anon>:25     *node = Node::Branch(0, l , r); 
          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
<anon>:22:26: 22:38 note: borrow of `*node` occurs here 
<anon>:22    &mut Node::Branch(_, ref mut left, ref mut right) => { 
              ^~~~~~~~~~~~ 

left 및 right 값은 node의 이전 내용 깊숙한 포인터이므로 컴파일러가 알고있는 한 (현재까지) node 덮어 쓰면 해당 포인터가 무효화됩니다 (물론 우리는 더 많이 사용되지 않지만 컴파일러는 그런 것들에주의를 기울이지 않는다는 것을 알 수있다.) 다행히 쉽게 수정있다 : 모두 match 팔 새 값에 node을 설정하는, 그래서 우리는 새로운 값을 계산하기 위해 match를 사용하고 계산하고 이후에 node을 설정할 수 있습니다.

*node = match node { 
    &mut Node::Value(_) => Node::Value(0), 
    &mut Node::Branch(_, ref mut left, ref mut right) => { 
     let l = mem::replace(left, Box::new(Node::Value(0))); 
     let r = mem::replace(right, Box::new(Node::Value(0))); 
     Node::Branch(0, l , r) 
    } 
}; 

(NB를가 작업 순서가 다소 이상합니다. 이는 let new_val = match node { ... }; *node = new_val;과 같습니다.이 새로운 Branch을 위해 2 개의 새로운 상자를 할당해야하기 때문에 자리에서 수정 한이 작업을 수행 할 필요가 없습니다 동안)

그러나, 즉, 내가 위에 쓴 그 일을보다 더 비싸다.

---

A는 약간 "더 좋은"버전 (코멘트 인라인)이 될 수 있습니다

#[derive(Clone, Show)] 
pub enum Node { 
    Value(u32), 
    Branch(u32, Box<Node>, Box<Node>), 
} 

fn main() { 
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3))); 
    let root = zero_node(root, 2); 

    println!("{:?}", root); 
} 

// Taking `tree` by value (i.e. not by reference, &) possibly saves on 
// `clone`s: the user of `zero_node can transfer ownership (with no 
// deep cloning) if they no longer need their tree. 
// 
// Alternatively, it is more flexible for the caller if it takes 
// `&mut Node` and returns() as it avoids them having to be careful 
// to avoid moving out of borrowed data. 
pub fn zero_node (mut tree: Node, node_index: u8) -> Node { 

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 { 
     if node_index == node_count { 
      // dereferencing once avoids having to repeat &mut a lot 
      match *node { 
       // it is legal to match on multiple patterns, if they bind the same 
       // names with the same types 
       Node::Value(ref mut val) | 
        Node::Branch(ref mut val, _, _) => { *val = 0; }, 
      } 
      node_count 
     } else { 
      match *node { 
       Node::Value(_) => 1, 
       Node::Branch(_, ref mut left, ref mut right) => { 
        let count_left = zero_rec(&mut **left, node_count + 1, node_index); 
        let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index); 
        count_left + count_right + 1 
       } 
      } 
     } 
    } 

    zero_rec(&mut tree, 0, node_index); 

    tree 

}