3 ms·
Unsorted counted B-trees are an interesting way to manage text in a text editor: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html http://www.
by erichocean 11y ago
Unsorted counted B-trees are an interesting way to manage text in a text editor:
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html 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.
- jhallenworld 11y agoYeah, 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.
- inspectahdeck 11y agoThis seems functionally pretty similar to the 'rope' [0] data structure used by GtkTextBuffer [0] https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure)
- deleted 11y ago[deleted]