Public implementation of ropes in C#?

Question

Is there a public implementation of the Rope data structure in C#?

Dawn

If you have a scenario where this data structure is more optimal than a string builder, I would be curious to know what it is. It has been my experience that rope data structures are almost never a win over the raw speed of native string or string builder operations in typical cases, so I am very interested to see realistic scenarios where its a win. – Ornas

I'm so very much curious as you are... that's why there goes another question! – Dawn

For one task, I want to start from an empty string and then insert a character in the middle of a string for millions of times. A string will not be efficient in this case. Rope may not be right in its original form, but we can adapt it to my particular application. – Dispersal

Answer 1

For what its worth, here is an immutable Java implementation. You could probably convert it to C# in less than an hour.

Spelter

Heh, this is a reference in the wikipedia article the poster linked to! :) – Equimolecular

@Vinko: I love irony. Wait... is that irony? I never know anymore. – Advantageous

Btw, if you are looking for a public Rope implementation, did you convert this one? and if, did you make it public? I would rather find it strange if not... – Phlegmy

Answer 2

I'm not aware of a Rope implementation (though there probably is one!), but if you're only after doing concatenation, StringBuilder will do the job.

Hygiene

Very true here. I did an implementation in C# a while ago where I used a 'linked list' of char arrays and no matter what, it could not beat the StringBuilder class. The problem comes when you are trying to tie those together for concatenation, you do not have access to a couple of native methods that the StringBuilder class has access to for allocating a buffer and copying the characters in. – Dime

@Dime - could you post your C# implementation (hopefully under a LGPL / BSD type license)? Perhaps we could investigate some additional strategies for perf. – Perspex

@torial: unfortunately I do not have that anymore. I did this for prototyping back when I was on the Windows team at Microsoft, so even if I had it, I could no share it out, sorry! – Dime

Answer 3

The BigList<T> class from Wintellect Power Collections (a C# data structure library) is somehow similar to rope: http://docs.pushtechnology.com/docs/4.5.7/dotnet/externalclient/html/class_wintellect_1_1_power_collections_1_1_big_list_3_01_t_01_4.html

I measured its performance and it performs pretty well in "start of string inserts":

const int InsertCount = 150000;

var startTime = DateTime.Now;
var ropeOfChars = new BigList<char>();
for (int i = 0; i < InsertCount; i++)
{
    ropeOfChars.Insert(0, (char)('a' + (i % 10)));
}
Console.WriteLine("Rope<char> time: {0}", DateTime.Now - startTime);

startTime = DateTime.Now;
var stringBuilder = new StringBuilder();
for (int i = 0; i < InsertCount; i++)
{
    stringBuilder.Insert(0, (char)('a' + (i % 10)));
}
Console.WriteLine("StringBuilder time: {0}", DateTime.Now - startTime);

Results:

Rope<char> time: 00:00:00.0468740
StringBuilder time: 00:00:05.1471300

But it performs not well in "middle of string inserts":

const int InsertCount = 150000;

var startTime = DateTime.Now;
var ropeOfChars = new BigList<char>();
for (int i = 0; i < InsertCount; i++)
{
    ropeOfChars.Insert(ropeOfChars.Count / 2, (char)('a' + (i % 10)));
}
Console.WriteLine("Rope<char> time: {0}", DateTime.Now - startTime);

startTime = DateTime.Now;
var stringBuilder = new StringBuilder();
for (int i = 0; i < InsertCount; i++)
{
    stringBuilder.Insert(stringBuilder.Length / 2, (char)('a' + (i % 10)));
}
Console.WriteLine("StringBuilder time: {0}", DateTime.Now - startTime);

Results:

Rope<char> time: 00:00:15.0229452
StringBuilder time: 00:00:04.7812553

I am not sure if this is a bug or unefficient implementation, but "rope of chars" is expected to be faster that StringBuilder in C#.

You can install Power Collections from NuGet:

Install-Package XAct.Wintellect.PowerCollections

Abomination

Answer 4

Here is a public implementation of Ropes in C#, based on the immutable java implementation listed above. Note that you won't get the same polymorphism benefits as the java version because strings can't be inherited and CharSequence doesn't exist natively in C#.

Starr