Crate calcit_fingertrees

Finger Trees

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:

• Original paper: Finger Trees: A Simple General-purpose Data Structure
• Wikipedia article: FingerTree

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 calcit_fingertrees::measure::Size;
use calcit_fingertrees::monoid::Sum;
use calcit_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(),
);

Re-exports

• pub use crate::measure::Measured;
• pub use crate::monoid::Monoid;

Modules

• measure
  Measured trait and implementations
• monoid
  Monoid trait and implementations
• rc
  Rc based implementation of FingerTree
• sync
  Arc based implementation of FingerTree

Macros

• fingertree_define_refs
  Helper macro to define custom Refs for FingerTree

Structs

• FingerTree
  FingerTree implemenetation
• TreeInner
  Only visible to defne custom Refs

Enums

• ArcRefs
  References type family
• NodeInner
  Only visible to defne custom Refs
• RcRefs
  References type family

Traits

• Ref
  Interface that all reference types should impelmenet
• Refs
  Interface which defines all reference types needed by finger tree implementation.