手指树

手指树是一种支持以摊销常数时间访问端点、以较小部分大小对数时间进行连接和拆分的持久序列的函数表示。它还定义了通用的 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")]);

// concatenate
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(),
);