在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会作废那些会使用它们造成任何进一步的代码指针被打破(当然,我们可以看到,既没有使用更多,但编译器不关注那样的事情).幸运的是,有一个简单的修复方法:两个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

}