im_ternary_tree

Crates.ioim_ternary_tree
lib.rsim_ternary_tree
version0.0.18
sourcesrc
created_at2021-11-01 06:40:05.743231
updated_at2024-02-25 14:59:02.544857
descriptionStructural sharing ternary tree, i.e. immutable data structure
homepagehttps://github.com/calcit-lang/ternary-tree.rs/
repositoryhttps://github.com/calcit-lang/ternary-tree.rs/
max_upload_size
id475041
size740,628
题叶 (tiye)

documentation

https://docs.rs/crate/im_ternary_tree/

README

Persistent structrual sharing tree for Calcit

a variant of 2-3 tree, with enhancements on ternary branching, optimized with tricks like finger-tree.

t.pop_left() and t.push_right(..) is optimized to be amortized O(1) at best cases and O(log n) when restructuring involed.

Tree layout from 0 to 159 watch video or try live demo.

ternary-tree illustrated

Usage

crate

Docs https://docs.rs/im_ternary_tree/ .

use im_ternary_tree::TernaryTreeList;

println!("{}", TernaryTreeList::<usize>::from(&[]));

// assoc
let origin5 = [1, 2, 3, 4, 5];
let data5 = TernaryTreeList::from(&origin5);
let updated = data5.assoc(3, 10);

println!("{}", data5.format_inline());
println!("{}", updated.format_inline());

assert_eq!(updated.unsafe_get(3), 10);

Optimizations

方案设计的中文介绍 https://www.bilibili.com/video/BV1z44y1a7a6/

This library has special optimizations on push_right and pop_left with tricks from finger-tree.

And as its size grows, it's always operating on a shallow branch at right end, wasting fewer nodes for indexing new elements, a random demo looks like:

ternary-tree illustrated

Also the left branches are kept shallow on purpose so it can be cheaper in pop_left. Totally inspired by finger-tree.

Known Issues

  • no optimizations on pop_right and push_left.
  • elements in the middle could be inside deep branches, leading to slow performance.

License

MIT

Commit count: 75

cargo fmt