Crates.io | calcit_fingertrees |
lib.rs | calcit_fingertrees |
version | 0.0.3 |
source | src |
created_at | 2021-11-25 09:19:55.923313 |
updated_at | 2021-11-26 05:16:47.035959 |
description | (Calcit fork of )Immutable persisten `fingertrees` |
homepage | |
repository | https://github.com/calcit-lang/fingertree-rs |
max_upload_size | |
id | 487501 |
size | 81,747 |
Finger trees is a functional representation of persistent sequences
supporting access to the ends in amortized constant time, and concatenation
and splitting in time logarithmic in the size of the smaller piece. It also
has split
operation defined in general
form, which can be used to implement sequence, priority queue, search tree,
priority search queue and more datastructures.
Rc/Arc
. Using type family trick.Rc/Arc
or
anything else.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(),
);