calcit_fingertrees

Crates.iocalcit_fingertrees
lib.rscalcit_fingertrees
version0.0.3
sourcesrc
created_at2021-11-25 09:19:55.923313
updated_at2021-11-26 05:16:47.035959
description(Calcit fork of )Immutable persisten `fingertrees`
homepage
repositoryhttps://github.com/calcit-lang/fingertree-rs
max_upload_size
id487501
size81,747
题叶 (tiye)

documentation

README

FingerTree

Build Status Coverage Status MIT License Crate API Docs

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.

Links:

Notes:

  • This implementation does not use non-regular recursive types as implementation described in the paper. As rust's monomorphization does not play well with such types.
  • Implmentation abstracts over reference counted types Rc/Arc. Using type family trick.
  • Uses strict spine in implementation.
  • Iterator returns cloned value, and in general this implementation assumes that value stored in a tree is cheaply clonable, if it is not you can always put it in a Rc/Arc or anything else.

Examples:

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(),
);
Commit count: 62

cargo fmt