im_ternary_tree

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.

Usage

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:

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