Menu
This is an interview question. What data structure would you use to store the text in a text editor?
907
For example, the original vi used an array of lines, which sort of explains some of its quirky line-oriented idioms. The BSD clone of vi, nvi, uses an entire database to represent buffers. Vim uses a fairly complex rope-like data structure with page-oriented blocks, which may be stored out-of-order in its swap file.
A Rope data structure is a tree data structure which is used to store or manipulate large strings in a more efficient manner. It allows for operations like insertion, deletion, search and random access to be executed faster and much more efficiently in comparison to a traditional String.
A structure editor, also structured editor or projectional editor, is any document editor that is cognizant of the document's underlying structure.
On good old ZX-Spectrum one (or more, I do not know) text exditor used very simple structure.
There was one big buffer, which occupied all free RAM. Text was split in two parts at the cursor. Part before the cursor, was placed at the beginning of the buffer, and the rest at the end of the buffer. As text typed, data simply added to the end of first part, and when cursor is moved, text is copied forth and back.
Buffer layout:
Hello, World! ^------Cursor here +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |H|e|l|l|o|,| |W| <free> |o|r|l|d|!| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ^ ^ | begin cur1 cur2 end That's, how some edit operations was made:
Type a char: buffer[cur1++] = character Backspace: cur1-- Cursor left: buffer[--cur2] = buffer[--cur1] Cursor right: buffer[cur1++] = buffer[cur2++] Buffer in action:
Hello, W..............orld! Press right ^ ^ Hello, Wo..............rld! Press backspace ^ ^ Hello, W...............rld! Press 0 ^ ^ Hello, W0..............rld! ^ ^ If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
