search

eaburns / T

T is a work-in-progress text editor inspired by the Acme editor from Plan9.
MIT License
8 stars 1 forks source link

rope: fast random access of lines #27

Open ktye opened 5 years ago

ktye commented 5 years ago

Do ropes support accessing a random line without reading each rune from the start and count newlines? I have not studies the theory, but here this is mentioned at least: https://xi-editor.io/docs/rope_science_02.html#line-endings

rope.IndexFunc indicates that no faster method is implemented.

Maybe this is not needed in the current implementation, as you just store the current offset, slice there, read each rune and draw until the screen is full. This needs just a screenfull of reads.

I'm thinking how to implement wrapped lines, where a line within view could be very long and you want to jump to the beginning of the next after drawing the leading runes in the viewport.

eaburns commented 5 years ago

I think you can track how many newlines are in the subtree beneath each node in the rope. Then you do a binary-tree-search-like traversal to find exactly the node that contains the beginning of your line and do a linear scan from there.

I considered this optimization, but I didn't implement it because I was prioritizing getting T v0.1 working first and wasn't sure it would be necessary in practice. Do you find that it is? I haven't really written enough text in T myself.

ktye commented 5 years ago

I guess it's only needed when you want to implement non-wrapped lines. I just started rewriting my ui toolkit, which has an adapter for your textbox including unwrapped lines: github.com/ktye/ui/blob/master/editor/textbox.go

You can try the widget in github.com/ktye/ui/examples/edit if you like. Wrapping can be toggled with the context menu (right click). I have not used this for anything real.

The performance issues are noticable only for very long lines, that I generate when using the widget as a front-end to an interpreter.

But to make long lines be useable, we would also have to implement horizontal scrolling as well, which I haven't done yet. This could be quite some work and would also need support for jumping to a given start position for each line.

draw-unwrapped:
  jump to first line in viewport
  for each line in viewport:
    jump to viewports x offset
    draw chars until out of viewport