Skip to main content

Crate finger_vec

Crate finger_vec 

Source
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 elements
  • concat, 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§

FingerVec
Persistent vector with cheap operations at both ends.
Iter
Borrowing iterator over a FingerVec. Forward iteration walks the chunks in order; next_back indexes from the end.

Constants§

BRANCH
Maximum number of children in one branch.
CHUNK
Maximum number of elements in one leaf chunk.