Add a finger or cursor to Rope
Opened this issue · 4 comments
Since the primary use-case for our Rope is text editing, we ought to provide some kind of cursor/finger/zipper for our Rope, a structure that optimises edit speeds around a particular location. In a text editor, a majority of editing takes place around a cursor position in the document, and if we provide a cursor over a Rope, we can use it to make a majority of Rope operations much faster.
Some references:
- Finger trees (in haskell): http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
- Rust std's
Cursor
: https://doc.rust-lang.org/beta/std/io/struct.Cursor.html- this is for I/O, not for a data structure, but it might provide an example of what an API for a Cursor might look like
- https://internals.rust-lang.org/t/pseudo-rfc-cursors-reversible-iterators/386/15
- a simple finger list: http://cglab.ca/~abeinges/blah/too-many-lists/book/infinity-double-single.html
- skip-list based rope in C: https://github.com/josephg/librope
somewhat related to #31, would it make sense to have the rope split a node on a newline? would make lines()
easier and probably also speed up edits like inserting/removing a line
@twisted-pear: yeah; see also #32. @cjm00 and i have definitely at least discussed doing that in the past. might make a lot of sense for our use case. this also has the rather nice side benefit of letting branches could also store their line count, making line counting nicely fast
I suspect we could probably rewrite a lot of our messy iterator & slice code to use a base cursor structure and then add different behaviours to it with traits...