Изменение узла в дереве в Rust

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 и т.д .: способ создать &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 приведет к аннулированию тех указателей, которые будут причиной e любой дополнительный код, использующий их для нарушения (конечно, мы можем видеть, что ни один из них не используется больше, но компилятор не обращает внимания на такие вещи). К счастью, есть легко исправить: обе 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) 
    } 
}; 

(Н.Б. порядок операций немного странный, это то же самое, что и let new_val = match node { ... }; *node = new_val;.)

Однако, что дороже, чем делать это, как я уже писал выше, так как он должен выделить 2 новые коробки для нового Branch, в то время как один, который изменяет на месте не должны делать это.

---

Немного "лучше" версия может быть (комментарии рядный):

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

}