Gap Buffer

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 30 minutes | Coding time: 10 minutes

Gap buffer is a data structure used to edit array of text in an efficient manner which is currently being edited. Correct example to understand the concept of Gap Buffer would be text editors. In text editors, you can insert the text instantly at the position of your cursor. This process uses the concept of gap buffers. Lets look at it with an example.

Operations like insertion and deletion takes place in constant time and hence, performs well and can be direct alternative to Rope Data Structure.

Understanding Gap Buffer

Consider the empty buffer below with size of 10.

"__________"

Note, '_' (underscore) means buffer gap element

Now we insert "open" in this buffer at 0, our array would now look like this,

"open______"

inserting "-" at 4, and our array would reflect as,

"open-_____"

And finally inserting "genus" at 5. Our array would look like this,

"open-genus"

Lets insert "welcome-" at 5, but for that we don't have any space left on the buffer. So we wont be able to add anything without deleting the existing array as it is contrained. With using Gap Buffers, we can produce any number of blank spaces starting from given index and then we can add our "welcome-" string.

Add welcome- at 5 operation would be executed as below,

go to 5
check gap on the right > length of the string
If true add the string
else grow the array and add string to it.

Note: This is very high level idea.

"open-_genus"
"open-welcome__genus"

Now lets delete 5th element, the operation would look like

go to 5
replace the element with the gap.

"open-___elcomegenus"

Basic Operations in Gap Buffer

There are number of coined operations in gap buffer and also till now you might have figured out some already.

1. insert()

As the name suggest, this operation will insert the element at the specified location of the buffer. Buffer contain the information of the gap, such as information about the starting point and ending point of the gap. Now when we call insert and pass the position to which we want to insert, this gap will move in such a way that it will position left gap point at the "to be inserted" position. Now the gap will be filled it will reduced in size.

Lets see the algorithmic steps

insert(string str, position p)
    if left_gap != p then move_gap_to(p)
    for char in string
        buffer[left_gap] = char
        left_gap++

The increase in left gap value will decrease the length of gap as right gap is not being change.

2. grow()

This operation will grow the gap from the specified location. How much should be grow? I would say it depends on the programmer. Some prefer fixed length and some on the input string length. For the sake of this article, we would stick to the fixed length.

Lets say we fixed the growth size to 10. During insert operation, our gap reduces every time. We should call grow() operation when left gap index is equal to the right gap index.

When grow() is called the index which succeeds the gap index are to be shift to +10 indexes as we have fixed the growth size. And we will create gap in next 10 indexes.

Lets see the algorithmic steps

grow(position p)
    buffer = buffer[:p]+ ['_']*10 + buffer[p:]
    left_gap = p
    right_gap = p+10

The first line adds gap starting to buffer from p to p+10.

3. left()

This operation will move the gap left from the current position. This operation will transfer left element from gap to right element.

Pseudocode:

move_left(pos):
    while(left_gap != pos):
        left_gap = left_gap - 1
        right_gap = right_gap - 1
        main_array[right_gap+1] = main_array[left_gap]
        main_array[left_gap] = '_'

4. right()

This operation will move the gap right from the current position. This operation will transfer right element from the gap to left element.

Pseudocode:

move_right(pos):
    while(left_gap != pos):
        left_gap = left_gap + 1
        right_gap = right_gap + 1
        main_array[left_gap-1] = main_array[right_gap]
        main_array[right_gap] = '_'

5. delete()

This operation will delete the specified element in the buffer. As insert reduced gap by increasing only left gap, delete operation reduced gap by reducing right gap only.

Pseudocode:

delete( pos):
    if left_gap != pos:
        move_gap(pos)

    right_gap = right_gap + 1
    main_array[right_gap] = '_'

Python implementation


class GapBuffer:
    def __init__(self):
        self.main_array = ['_']*50
        self.buffer_length = 10
        self.left_gap = 0
        self.right_gap = 9
    
    def print_buffer(self):
        for x in range(self.buffer_length):
            print(self.main_array[x], end="")
        print("\n")
        # print(self.main_array)

        return
    
    def grow(self, pos):
        temp_main_array = self.main_array[:self.buffer_length]
        for x in range(pos):
            self.main_array[x] = temp_main_array[x]
        
        for x in range(10):
            self.main_array[pos+x] = '_'
        
        for x in range(pos, len(temp_main_array)):
            self.main_array[x+10] = temp_main_array[x]
        
        self.right_gap = self.right_gap + 10
        self.buffer_length = self.buffer_length + 10

        return
    
    def move_left(self, pos):
        while(self.left_gap != pos):
            self.left_gap = self.left_gap - 1
            self.right_gap = self.right_gap - 1
            self.main_array[self.right_gap+1] = self.main_array[self.left_gap]
            self.main_array[self.left_gap] = '_'

        return
    
    def move_right(self, pos):
        while(self.left_gap != pos):
            self.left_gap = self.left_gap + 1
            self.right_gap = self.right_gap + 1
            self.main_array[self.left_gap-1] = self.main_array[self.right_gap]
            self.main_array[self.right_gap] = '_'
        return

    
    def move_gap(self, pos):
        if pos < self.left_gap:
            self.move_left(pos)
        else:
            self.move_right(pos)
        
        return

    
    def insert(self, in_string, pos):
        if self.left_gap != pos:
            self.move_gap(pos)
        
        for x in range(len(in_string)):
            if (self.left_gap == self.right_gap):
                self.grow(pos+x)
            self.main_array[pos+x] = in_string[x]
            self.left_gap = self.left_gap + 1
    
    def delete(self, pos):
        if self.left_gap != pos:
            self.move_gap(pos)
        
        self.right_gap = self.right_gap + 1
        self.main_array[self.right_gap] = '_'
        return  

if __name__ == '__main__':
    gp = GapBuffer()
    gp.print_buffer()
    gp.insert("open-genus", 0)
    gp.print_buffer()
    gp.insert("welcome-", 5)
    gp.print_buffer()
    gp.delete(5)
    gp.print_buffer()

Complexity

The insert or insertion operation takes O(1) time but growing operation takes O(n) cause we need to shift the values as the buffer size increases. But comparing to other options, it is quit faster than Ropes.

Due to this reason, this data type is the first choice for text editors.

Following table summarizes the time complexity:

Operation	Time Complexity
Insert	O(1)
Delete	O(1)
Grow	O(N)
Move left	O(N)
Move right	O(N)