CODEWITHSUNDEEP
c#stringropes
luvieere
luvieere

Reputation: 37494

Public implementation of ropes in C#?

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

Upvotes: 14

Views: 4732

Answers (5)

Shailen Sukul
Shailen Sukul

Reputation: 510

My colleague has written a Rope implementation in C# here.

Also available as NuGet package FlatlinerDOA.Rope.

Upvotes: 2

Adam
Adam

Reputation: 79

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#.

Upvotes: 1

Svetlin Nakov
Svetlin Nakov

Reputation: 1669

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

Upvotes: 2

Juliet
Juliet

Reputation: 81526

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

Upvotes: 14

Richard
Richard

Reputation: 30618

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.

Upvotes: 15

Related Questions