Tree of mutable slices

Viewed 111

Some algorithms recursively partition an array into smaller pieces. You can build an explicit binary tree that results from such a process, where each leaf holds a disjoint slice of the array. If you need to alter or reorder elements in the leaf, its slice must be mutable.

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

Suppose I need to split all the leaves that are larger than some threshold. Easy: recursively walk down the tree from the root; when I find a leaf with a slice long enough, split it into 2 halves, wrap them into a 2-leaf subtree, and replace the leaf.

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 borrow-checker is unable to find a suitable lifetime for the ref mut leaf pattern. It wants it dead before allowing the assignement to *self, but I don't see how to make the assignment out of the match arm.

How to make this work?

2 Answers
Related