内容树

这是一个用于管理打包的运行长度编码数据的复杂数据结构。它类似于

• 绳子，但适用于任意数据。
• 类似于列表/数组，但具有内联运行长度编码，并支持在任何位置高效地插入和删除
• 类似于B树，但每个项目不是具有固定键，而是根据其在列表中的当前位置进行索引。当在当前位置之前插入或删除其他项目时，每个项目的位置将发生变化。

此库当前实现为一个B树，但我计划使用跳表（例如jumprope）重写它。我相信这将使代码更小并提高性能。

待办事项：此库没有获得MIRI的批准。我将在跳表方向的改写期间添加。

功能

• 基于合理优化的B树（每秒可处理数百万次编辑）的高性能
• 内联RLE压缩。项目会根据需要自动拆分和合并。
• 支持自定义项目内部索引
• 支持外部索引 - 即使用外部数据结构在B树中查找项目。

示例

假设你想存储位RLE运行。我们可以为我们的数据创建自己的SplitableSpan RLE类型，但在这个例子中，我们可以使用内置的RleRun<bool>类型

use content_tree::{ContentTree, RleRun};

fn main() {
    let mut list = ContentTree::new();
    list.push(RleRun { val: false, len: 10 });

    // Insert in the middle (at offset 5) in the run of 10 items:
    list.insert_at_offset(5, RleRun { val: true, len: 2 });
    println!("List contains {:?}", list.iter().collect::<Vec<RleRun<bool>>>());

    // List contains [
    //  RleRun { val: false, len: 5 },
    //  RleRun { val: true, len: 2 },
    //  RleRun { val: false, len: 5 }
    // ]
}

但你不限于简单的项目运行。假设你想存储自动压缩的标识符范围。我们可以为那个创建一个自定义的结构体，只要它实现

• SplitableSpan
• Copy
• Default（尽管通过一些工作可以删除此约束。如果有问题，请提出问题）。

对于范围类型，我们的实现可能如下所示

#[derive(Debug, Clone, Copy, Default)]
struct RleRange {
    // Sadly we can't just embed a Range because it doesn't implement
    // Copy. And Copy is needed for ContentTree.
    start: usize,
    end: usize,
}

impl SplitableSpan for RleRange {
    fn len(&self) -> usize { self.end - self.start }

    fn truncate(&mut self, at: usize) -> Self {
        let old_end = self.end;

        // Truncate self to [start..start+at)
        self.end = self.start + at;

        // And return the trimmed remainder
        RleRange { start: self.end, end: old_end }
    }

    fn can_append(&self, other: &Self) -> bool {
        self.end == other.start
    }

    fn append(&mut self, other: Self) {
        self.end = other.end;
    }
}

然后你可以使用你的类型创建一个内容树

fn main() {
    let mut list = ContentTree::new();
    list.push(RleRange { start: 0, end: 15 });
    list.push(RleRange { start: 15, end: 20 });
    
    // Both items are automatically merged!
    println!("List contains {:?}", list.iter().collect::<Vec<RleRange>>());
    // List contains [RleRange { start: 0, end: 20 }]
}

有关完整示例，请参阅examples/custom_entry.rs

待办事项

• 为最后的光标位置添加缓存
• 使用列表配置的特质进行迁移
• 以更简洁的方式处理通知函数 - 最好通过类型的通用参数传递
• 考虑删除内部列表大小

此代码是作为菱形类型的一部分实现的。