An implementation of a Rope data structure in Kotlin.
Please note this library has a different license from the other forkhandles libraries due to being derived from an upstream library.
Ropes are much faster than Strings, StringBuffers, or CharArrays for insert and delete operations. When inserting or deleting, they don't copy the data meaning that the working data set size is much smaller.
Really a lot, see the performance charts. These show comparitive performance of Ropes, Strings and StringBuffers for a few operations. The numbers themselves are not relevant, only the relative speeds.
Inserts, Prepends, and Deletes are effectively hundreds of times faster.
Because Ropes are stored as trees, getting characters by index is slower, so random-access into Ropes is not the best access pattern. In-Order and Reversed-Order iteration of Ropes is relatively efficient in this implementation.
A Rope implements the following interfaces:
- CharSequence
- Iterable
- Comparable
- Serializable
Your code should refer to CharSequence wherever possible. If it does, then using a Rope is as simple as:
val r = Rope.of("123")If you have a CharArray, you can use ofCopy - This is to highlight that CharArrays are copied right now.
var r = Rope.ofCopy("123".toCharArray())The Rope doesn't copy your CharSequence, but Ropes are supposed to be immutable, so if you modify the underlying CharSequence
undefined behaviour will happen.
The current implementation does copy a CharArray on construction, and option is planned later to make a zero-copy version.
Appending 500 subsequences of a 200kB charsequence to itself.
Instantiating a 200kB instance. A Rope based on a CharSequence does no copy, so it's way faster than the others, that all copy in some way.
Deleting 500 subsequences from an original 200kB.
Indexing into a 200kB char string.
Inserting subsequences of a rope into itself
Inserting subsequences of a rope into a different rope
Prepending 500 subsequences of a 200kB character string onto itself.
Running simple regex against 200kB character string
Finding simple string in 200kB character string.
Iterating over 200kB character string
This version started off as Ropes for Java and the original code is GPL Licence
The original author of Ropes for Java was Amin Ahmad.