Expand description
FingerVec<T>: a persistent vector for the Calcit runtime.
Layout: a front buffer, a relaxed B-tree of chunks in the middle, and a back buffer. Buffers make operations on both ends cheap; the tree keeps indexing, slicing and concatenation logarithmic.
get,assoc:O(log₃₂ n)push_left,push_right,drop_left,drop_right:O(1)amortized with a chunk copy of at most 32 elementsconcat,split,slice,insert,dissoc:O(log n)- lists with at most 32 elements live in one buffer
All operations return new values and share structure with the input.
Structs§
- Finger
Vec - Persistent vector with cheap operations at both ends.
- Iter
- Borrowing iterator over a
FingerVec. Forward iteration walks the chunks in order;next_backindexes from the end.