Tree of mutable pieces

Question

Some algorithms recursively split an array into smaller fragments. You can build an explicit binary tree, which is obtained from a process where each leaf contains a disjoint slice of the array. If you need to change or rearrange the order of elements in a sheet, its slice must be changed.

enum Tree<'a> {
    Branch(Box<[Tree<'a>; 2]>),
    Leaf(&'a mut[f32]),
}

Suppose I need to break all leaves that are greater than a certain threshold. Easy: recursively walk the tree from the root; when I find a sheet with a slice long enough, break it into two halves, wrap them in a two-leaf subtree and replace the sheet.

impl<'a> Tree<'a> {
    fn split(&mut self, max: usize) {
        match self {
            &mut Tree::Branch(ref mut trees) => {
                trees[0].split(max);
                trees[1].split(max);
            },
            &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                let trees = [Tree::Leaf(l), Tree::Leaf(r)];
                *self = Tree::Branch(Box::new(trees));
            },
        }
    }
}

Unfortunately, the borrower cannot find a suitable life time for the template ref mut leaf. He wants him to be dead before allowing the assignment *self, but I don’t see how to make the appointment out of the hands of the match.

?

Answer 1

, .

use std::mem;

enum Tree<'a> {
    Branch(Box<[Tree<'a>; 2]>),
    Leaf(&'a mut[f32]),
    Placeholder, // it not very nice hack, but it required for mem::replace
}

impl<'a> Tree<'a> {
    fn split(&mut self, max: usize) {
        let mut needs_split = false;
        match self {
            &mut Tree::Branch(ref mut trees) => {
                trees[0].split(max);
                trees[1].split(max);
            },
            &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
                // Postpone modification of *self. We can't do it now while
                // a part of *self is borrowed
                needs_split = true;
            },
            _ => {}
        }
        if needs_split {
            // move *self into cself, to be able to
            // deconstruct content, while keeping *self not borrowed
            let cself = mem::replace(self, Tree::Placeholder);
            if let Tree::Leaf(leaf) = cself {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                let trees = [Tree::Leaf(l), Tree::Leaf(r)];
                *self = Tree::Branch(Box::new(trees));
            } else {
                unreachable!()
            }
        }
    }
}

Answer 2

, , . -, self:

fn split(&'a mut self, max: usize)

- ; ( ) :

_ => unimplemented!()

, trees ; , :

&mut Tree::Branch(ref mut trees) => {
    for tree in trees.iter_mut() {
        tree.split(max);
    }
}

:

error[E0506]: cannot assign to `*self` because it is borrowed
  --> <anon>:18:17
   |
14 |             &mut Tree::Leaf(ref mut leaf) if leaf.len() > max => {
   |                             ------------ borrow of `*self` occurs here
...
18 |                 *self = Tree::Branch(Box::new(trees));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `*self` occurs here

, Leaf :

impl<'a> Tree<'a> {
    fn get_trees(&'a mut self, max: usize) -> Option<[Tree<'a>; 2]> {
        if let &mut Tree::Leaf(ref mut leaf) = self {
            if leaf.len() > max {
                let mid = leaf.len() / 2;
                let (l, r) = leaf.split_at_mut(mid);
                Some([Tree::Leaf(l), Tree::Leaf(r)])
            } else {
                None
            }
        } else {
            None
        }
    }
}

&mut Tree::Leaf(_) => {
    let trees = self.get_trees(max).unwrap(); // safe (under a valid match arm)
    *self = Tree::Branch(Box::new(trees));
}

, self . Clone ( trees self), ; , - .

Rust