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?