Rope, a heavier String

I have been developing the data structure called a "rope" in my
free time. Ropes were described in the 1995 article "Ropes: an
Alternative to Strings" by Boehm, Atkinson, and Plass.

I share my rope here because more than one person has brought a question
or concern about String indices being invalidated by String mutations.
Indices on my rope can survive mutation. That property may be useful
enough that, even though my rope is not a one-for-one substitution for a
String, it is helpful or inspiring to someone.

The classic rope data structure is a binary tree with text nodes
at the leaves. In my variation on the rope, some leaves are
counterparts for the program's indices. If you delete a text-only
range from the rope, then all of the counterparts move, and their
indices remain valid. If you delete a range from the rope that
covers any counterparts, then you invalidate only the indices
corresponding with the covered conterparts. If you destroy an
index, then its counterpart is marked as garbage through some
weak-reference magic.

(In my text-editing application I need to store text attributes,
I need pretty fast random access, multiple embedded cursors, and
"containers" that basically correspond with multiple selections.
My rope provides all of that, too.)

I tossed the work in progress onto GitHub,
https://github.com/gnuoyd/rope/, for feedback. If you have advice about
how to make the Swift code more idiomatic or reusable, or if you think
you would like to improve or use the code, please get in touch.

Dave

8 Likes

As essentially an announcement of a related project, this may be more appropriate for the Community Showcase category. Do you mind if I move it?

1 Like

That sounds fine.

Dave

Done, thanks!

Terms of Service

Privacy Policy

Cookie Policy