可变切片树

Question

一些算法递归地将数组分割成更小的部分。您可以构建一个由这样的过程产生的显式二叉树，其中每个叶子都包含数组的不相交切片。如果需要更改或重新排序叶子中的元素，则其切片必须是可变的。

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

假设我需要分割所有大于某个阈值的叶子。简单：从根部递归地走下树；当我找到一片叶子足够长时，将其分成两半，将它们包装成两片叶子的子树，然后替换叶子。

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));
            },
        }
    }
}

不幸的是，借用检查器无法为该ref mut leaf模式找到合适的生命周期。它希望它在允许分配给 之前死掉*self，但我不知道如何使分配脱离匹配臂。

如何使这项工作有效？

Answer 1

您可以使用两个技巧使其工作，代码中对此进行了解释。

use std::mem;

enum Tree<'a> {
    Branch(Box<[Tree<'a>; 2]>),
    Leaf(&'a mut[f32]),
    Placeholder, // it's not very nice hack, but it's 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!()
            }
        }
    }
}