News for hackers. Stuff that matters.

A comment on A Brief Glance at How Various Text Editors Manage Their Textual Data (2015).

Re:A Brief Glance at How Various Text Editors Manage Their T... by erichocean on Tuesday March 08, 2016 @01:35PM (#11247362)
Unsorted counted B-trees are an interesting way to manage text in a text editor:

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtre...

You can do all the normal editing operations in log time, and B-trees can (obviously) be run from disk, so you don't need to use a lot of RAM, either, and can efficiently edit extremely large text files. In-memory, B-trees also use the memory hierarchy efficiently.

[ Parent | on HN ]
Re:A Brief Glance at How Various Text Editors Manage Their T... by inspectahdeck on Tuesday March 08, 2016 @02:53PM (#11248012)
This seems functionally pretty similar to the 'rope' [0] data structure used by GtkTextBuffer

[0] https://en.wikipedia.org/wiki/Rope_(data_structure)

[ Parent | on HN ]
Re:A Brief Glance at How Various Text Editors Manage Their T... by jhallenworld on Tuesday March 08, 2016 @02:48PM (#11247965)
Yeah, the "goto this byte offset" operation is possibly fast enough that you can just use byte offsets for buffer pointers instead of anything more elaborate (pointing to the data structure internals). The leaf nodes could be gap buffers.

You could have (a secondary index of) line counts as well as bytes so that you can also seek to specific lines in log time.

[ Parent | on HN ]