Ropes - An alternative to strings

[A3aan]

Hi Everyone ,

When searching for an efficient way to handle long texts I stumbled on this Wikipedia article:
https://en.wikipedia.org/wiki/Rope_(data_structure)

After reading I decided to implement the Rope data type as a unit so Ropes could be used as an alternative to Strings. Ropes have an advantage over Strings when texts grow large since they reduce the amount of data movement when inserting or deleting parts of the text. Also the implementation uses a reference counting scheme to avoid unnecessary duplication of text fragments. This behavior is often desired in word processing when multiple versions of the text must be held in memory to allow for recovering from erroneous changes.

The Ropes unit, documentation, and a demo in the form of a small text editor program can be found here:
http://home.hccnet.nl/fam.rappard/adriaan/fpc/ropes.zip

Hope you like it 

Adriaan Rappard

[marcov]

Can't load the link. The correct link should be http://home.hccnet.nl/fam.rappard/adriaan/fpc/Ropes.zip

Afaik many better programming oriented texteditors use a similar structure, but in general will be more line oriented. (since they don't display endless continuous text, but texts broken up in lines).

At least that is what Martin tried to explain to me about the lazarus editor implementation once :_)

[A3aan]

Hi marcov,

Thanx! I corrected the link  .

[Thaddy]

I learned it as "cord". It is based on a Trie, not tree, and not very memory efficient on long texts, so it needs a windowing scheme too.

[sash]

> when multiple versions of the text must be held in memory to allow for recovering from erroneous changes

IMO you should not hold multiple versions (as a full snapshot copies). It is enough to keep some base version, current version and set of replayable/undoable changes between them.

[Thaddy]

Yes, sash. That's exactly what this does. Speed efficient at the cost of space.

[A3aan]

Yes, you're right. If you want to see how much faster at what memory cost download the zip file and read page 16 and 17 of the reference guide (Ropes.pdf)  .