search

aalhour / C-Sharp-Algorithms

:books: :chart_with_upwards_trend: Plug-and-play class-library project of standard Data Structures and Algorithms in C#
MIT License
5.91k stars 1.4k forks source link

Data structure request: Generic Rope #151

Open nloum opened 3 years ago

nloum commented 3 years ago

Is your data structure request related to a computational problem? Please describe. I'm working on a Conflict-Free Replicated Data Type (CRDT) for strings, and I would like to use a rope-like structure like what is described here: http://archagon.net/blog/2018/03/24/data-laced-with-history/#representing-non-string-objects.

Describe the solution you'd like The rope data type is specific to strings, but I would like a generic version of it where the item type is generic. Specifically, I'd like to have two generic Rope implementations, one where you can specify just the key and the other where you can specify the key and the value. These could be internally implemented by RedBlackTrees, to keep the tree balanced. (I don't think rope dictates a particular method of keeping the tree balanced.)

I would also like a virtual method for reindexing nodes that lets the user override the Rope class to index more than just the number of characters. This would let you skip not just a certain number of items when you want to iterate starting at an offset, but it could also let you skip a certain number of pages of text, or lines of text. That means there would have to be arbitrary properties available in the nodes, so I think that might have to be another generic parameter. Of course, there can be one class that only counts items and doesn't require a generic parameter for the per-node indexing properties.

Describe alternatives you've considered I've tried to use an ordered dictionary, but the problem with that is you can't index the dictionary in a way that lets you easily skip an arbitrary number of items in the list, which is important in rope structures. E.g., if I had an ordered dictionary of chars and I wanted to display page 20 of the string (ropes are good for really long strings, they are often used in text editors), to get a list of the characters starting on page 20 I would have to iterate all the 19 pages prior to page 20.

With ropes, the internal structure is a binary tree, and each node in the tree has a field that records how many items there are on the left child of the node. This makes it easy to start iterating nodes at a certain offset without iterating all the nodes leading up to that offset.

Additional context Some good information on ropes: https://medium.com/underrated-data-structures-and-algorithms/rope-data-structure-e623d7862137

nloum commented 3 years ago

I would be happy to implement this myself, but I wanted to open this issue first.

github-actions[bot] commented 3 years ago

Thanks for supporting the development of C# Algorithms with your first issue! We look forward to handling it.

aalhour commented 3 years ago

Hi @nloum, would be great to have this data structure, can you open a pull request?