Persistetnt 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/imternarytree/ .

```rust use imternarytree::TernaryTreeList;

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

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

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

asserteq!(updated.unsafeget(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