\nthe simpler data structures. A classic structure for implementing editor
\nbuffers is called a gap buffer<\/em>. I’ll explain the details below.
\nThe drawback of a gap buffer is that large cursor motions are relatively
\nexpensive – the cost of moving the cursor is proportional to the distance
\nthat you move it.<\/p>\n
So I wrote a test. I implemented a basic gap buffer. Then I built a
\ntest that did 300,000 inserts of five characters; then slid the cursor
\nfrom the end, to the beginning, back to the end, back to the beginning,
\nand back to the end again. Total execution time? 150 milliseconds. And
\nthat includes resizing the buffer 12 times, because of a deliberately
\nstupid buffer sizing and copying strategy.<\/p>\n
And with that, out the window went the ropes. Because in Java<\/em>, <\/p>\n Ok. So, what’s a gap buffer?<\/p>\n It’s a fascinatingly simple data structure – exactly the kind of For example, below is a diagram of a gap buffer. In the first version, it contains the text “Hello there readers”, with the cursor The next version In the third version, we insert the string “my” – just write the characters “m” and “y” into the next positions in the pre-gap region, That’s all there is to it. A gap buffer is just a character array, with two pointers\/indices to track the position of the beginning and ending segments. It’s incredibly simple – and yet, it’s also For its simplicity, it still manages to achieve outstanding performance on all of the most common actions in an edit buffer:<\/p>\n
\nusing a slapped together, sloppy piece of test code, which does things in a dumb
\nbrute force way, it can do something much more complicated than anything an editor
\nwill encounter in routine use, the gap buffer achieves performance that is more than
\nadequately fast. (Based on some experiments I did back at IBM, delays of 1\/10th
\nof a second are roughly when people start to notice that an editor is slow. If you can respond is less than 1\/10th of a second, people don’t perceive a troublesome delay.)
\nIf the gap buffer can achieve the needed perfomance that easily, then there’s
\nabsolutely no reason<\/em> to do anything more complicated.<\/p>\n
\nthing that appeals to my sense of software aesthetics. It’s a great big
\nbuffer – an array of characters. It’s got two segments of text – one at
\nthe beginning of the buffer, which grows upwards; and one at the end of
\nthe buffer, which grows downwards. The space between those two segments
\nis called the gap<\/em>. The gap is<\/em> the cursor in the
\nbuffer. To move the cursor forwards, you just move the gap<\/em>: move one character from the
\nbeginning of the end segment to the end of the beginning segment. To
\ninsert a character at the cursor, you add a character to the beginning
\nsegment. To delete the character before the cursor, you just subtract one
\nfrom the length of the beginning segment.<\/p>\n
\nafter the “r” in “readers”.<\/p>\n![\"hgaps.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_365.png?resize=538%2C244\")
<\/div>\n
\nmoves the cursor backwards one step. So we copy one character from
\nthe end of the pre-gap region to the beginning of the post-gap region,
\nand then adjust the pointers. We don’t even bother to erase the buffer
\nposition within the gap that used to contain the “r” – we just move
\nthe pre-gap pointer.<\/p>\n
\nand advance the pre pointer. The resulting buffer contains the text
\n“Hello there myreaders”.<\/p>\n
\nquite surprising. I certainly wouldn’t have thought of it on my own!<\/p>\n\n
\nO(1) cost for a single character cursor move, O(n) for arbitrary
\ncursor motions.<\/li>\n
\naverage cost of O(1). (The reason for that amortized cost is
\nbecause you sometimes need to expand the buffer, which
\nrequires a lot of copying.)<\/li>\n
\na pointer – O(1).<\/li>\n
\nsearch have an absolute linear-time lower bound, which is
\nobviously achieved by the gap buffer. And as important,
\nimplementing stream-oriented operations is extremely
\neasy to do correctly on a gap buffer.<\/li>\n<\/ul>\n