FlatlinerDOA.Rope 1.1.0

Rope

C# implementation of a Rope<T> immutable data structure. See the paper Ropes: an Alternative to Strings: h.-j. boehm, r. atkinson and m. plass

A Rope is an immutable sequence built using a b-tree style data structure that is useful for efficiently applying and storing edits, most commonly used with strings, but any list or sequence can be efficiently edited using the Rope data structure.

Where a b-tree has every node in the tree storing a single entry, a rope contains arrays of elements and only subdivides on the edits. The data structure then decides at edit time whether it is optimal to rebalance the tree using the following heuristic: A rope of depth n is considered balanced if its length is at least Fn+2.

Note: This implementation of Rope<T> has a hard-coded upper-bound depth of 46 added to the heuristic from the paper. As this seemed to be optimal for my workloads, your mileage may vary.

Example Usage

// Converting to a Rope<char> doesn't allocate any strings (simply points to the original memory).
Rope<char> text = "My favourite text".ToRope();

// With Rope<T>, splits don't allocate any new strings either.
IEnumerable<Rope<char>> words = text.Split(' '); 

// Calling ToString() allocates a new string at the time of conversion.
Console.WriteLine(words.First().ToString()); 

// Warning: Concatenating a string to a Rope<char> converts to a string (allocating memory).
string text2 = text + " My second favourite text";

// Better: This makes a new rope out of the other two ropes, no string allocations or copies.
Rope<char> text3 = text + " My second favourite text".ToRope();

// Value-like equivalence.
"test".ToRope() == ("te".ToRope() + "st".ToRope());
"test".ToRope().GetHashCode() == ("te".ToRope() + "st".ToRope()).GetHashCode();

Comparison with StringBuilder

A comparison could be drawn between a Rope and a StringBuilder as they use a very similar technique for efficient edits.

Performance and Memory Allocation Comparison with StringBuilder

Working with a string of length - 32644 characters. - MaxLeafLength = ~32kb, Max Depth = 46

Performance and Memory Allocation Comparison with List<T>