手指树

手指树是一种支持在摊销常数时间内访问端点，以及对较小部分进行对数时间连接和分割的持久序列的函数表示。它还定义了通用的 split 操作，可用于实现序列、优先队列、搜索树、优先搜索队列等更多数据结构。

链接

• 原始论文： Finger Trees: A Simple General-purpose Data Structure
• 维基百科文章： FingerTree

注释

• 此实现不使用非正则递归类型，正如论文中描述的实现。因为Rust的单态化与这种类型不兼容。
• 实现抽象了引用计数的类型 Rc/Arc。使用类型族技巧。
• 在实现中使用严格脊。
• 迭代器返回克隆的值，并且通常此实现假设存储在树中的值可以廉价地克隆，如果不能，您始终可以将它放入 Rc/Arc 或其他任何东西。

示例

use std::iter::FromIterator;
use fingertrees::measure::Size;
use fingertrees::monoid::Sum;
use fingertrees::{FingerTree, Measured, RcRefs};

// construct `Rc` based finger tree with `Size` measure
let ft: FingerTree<RcRefs, _> = vec!["one", "two", "three", "four", "five"]
    .into_iter()
    .map(Size)
    .collect();
assert_eq!(ft.measure(), Sum(5));

// split with predicate
let (left, right) = ft.split(|measure| *measure > Sum(2));
assert_eq!(left.measure(), Sum(2));
assert_eq!(Vec::from_iter(&left), vec![Size("one"), Size("two")]);
assert_eq!(right.measure(), Sum(3));
assert_eq!(Vec::from_iter(&right), vec![Size("three"), Size("four"), Size("five")]);

// concatinate
assert_eq!(ft, left + right);

// push values
assert_eq!(
    ft.push_left(Size("left")).push_right(Size("right")),
    vec!["left", "one", "two", "three", "four", "five", "right"]
         .into_iter()
         .map(Size)
         .collect(),
);