I\'m looking for a persistent data structure similar to array (but immutable), a

Question

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations.

Clojure provides persistent Vector, but it's only for fast append. Scala's Vector has effectively constant-time append and prepend, but I can't get how it's implemented, since it's based on same data structure (bit-mapped vector trie) as Clojure vector, and, as I understand, bit-mapped vector trie can't have fast prepend without some tricks.

I'm interested not in ready to use implementation but in a description of how to implement such a data structure myself.

Explanation / Answer

I have described one implementation of such a data structure in my article about incremental regular expression matching - see http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation and the text below and above that section.

It's a variety of a constant-height tree (like B-trees or 2-3 trees). Basically it's a (2,3) tree, whose leaves are (N, 2N-1) arrays, in order to avoid per-element overhead. (A (N, 2N-1) array is an array whose lengths in the range N..2N-1.) Larger N gives you smaller overhead but linearly increases the complexity of splitting and concatenation. Operations such as indexing, splitting and concatenation are very similar to the way they work in 2-3 trees, generalizing to (N, 2N-1) at the leaf level.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.