Gap Buffer | Deletion Operation
We have discussed
and insert operations. In this post,
delete operation
is discussed. When we want to delete a character these three cases may arise.
- Characters to be deleted is at cursor position: Let’s assume we want to delete “FOR” from “FORBeginner”, since the cursor (gap_left) is at desired position the character is deleted i.e. the gap takes the character inside itself and the character gets deleted.
- Characters to be deleted is left of cursor position: For this case since “FOR” is left to the cursor position we must reach to the desired position by using left() as in previous article. Now, we can delete “FOR” as in case 1.
- Characters to be deleted is right of cursor position: For this case also the cursor position is right to the desired position we must reach there by using right() as in previous article. Now, we can delete “FOR” as in case 1.
Implementing Gap Buffer with Deletion
CPP
// C++ program of implementation // of gap buffer with Deletion #include <bits/stdc++.h> using namespace std; char buffer[50]; int gap_size = 10; int gap_left = 0; int gap_right = gap_size - gap_left - 1; int size = 10; // Function that is used to grow the gap // at index position and return the array void grow( int k, int position) { char a[size]; // Copy characters of buffer to a[] // after position for ( int i = position; i < size; i++) { a[i - position] = buffer[i]; } // Insert a gap of k from index position // gap is being represented by '-' for ( int i = 0; i < k; i++) { buffer[i + position] = '_' ; } // Reinsert the remaining array for ( int i = 0; i < position + k; i++) { buffer[position + k + i] = a[i]; } size += k; gap_right += k; } // Function that is used to move the gap // left in the array void left( int position) { // Move the gap left character by character // and the buffers while (position < gap_left) { gap_left--; gap_right--; buffer[gap_right + 1] = buffer[gap_left]; buffer[gap_left] = '_' ; } } // Function that is used to move the gap // right in the array void right( int position) { // Move the gap right character by character // and the buffers while (position > gap_left) { gap_left++; gap_right++; buffer[gap_left - 1] = buffer[gap_right]; buffer[gap_right] = '_' ; } } // Function to control the movement of gap // by checking its position to the point of // insertion void move_cursor( int position) { if (position < gap_left) { left(position); } else { right(position); } } // Function to insert the string to the buffer // at point position void insert(string input, int position) { int len = input.length(); int i = 0; // If the point is not the gap check // and move the cursor to that point if (position != gap_left) { move_cursor(position); } // Insert characters one by one while (i < len) { // If the gap is empty grow the size if (gap_right == gap_left) { int k = 10; grow(k, position); } // Insert the character in the gap and // move the gap buffer[gap_left] = input[i]; gap_left++; i++; position++; } } // Function to delete the character buffer // at point position void deleetion( int position) { // If the point is not the gap check // and move the cursor to that point if (position + 1 != gap_left) { move_cursor(position + 1); } // Reduce the gap_left gap_left -= 1; buffer[gap_left] = '_' ; } // Driver code int main() { // Initializing the gap buffer with size 10 for ( int i = 0; i < 10; i++) { buffer[i] = '_' ; } cout << "Initializing the gap buffer " << "with size 10" << endl; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } cout << endl; // Inserting a string to buffer string input = "BeginnerBeginner" ; int position = 0; insert(input, position); cout << endl; cout << "Inserting a string to buffer" << ": BeginnerBeginner" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } input = "FOR" ; position = 5; // Inserting a string to buffer insert(input, position); cout << endl; cout << endl; cout << "Inserting a string to buffer" << ": FOR" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } position = 5; // Deletion a character from buffer deleetion(position); cout << endl; cout << endl; cout << "Deleting character at position 5" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } position = 6; // Deletion a character from buffer deleetion(position); cout << endl; cout << endl; cout << "Deleting character at position 6" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } position = 5; // Deletion a character from buffer deleetion(position); cout << endl; cout << endl; cout << "Deleting character at position 5" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } input = "HELLO" ; position = 0; // Inserting a string to buffer insert(input, position); cout << endl; cout << endl; cout << "Inserting a string to buffer" << ": HELLO" << endl; cout << "Output: " ; for ( int i = 0; i < size; i++) { cout << buffer[i] << " " ; } return 0; } |
Java
public class GapBuffer { // Define the buffer and gap variables private char [] buffer; private int gapSize = 10 ; private int gapLeft = 0 ; private int gapRight = gapSize - 1 ; private int size = 10 ; // Constructor to initialize the gap buffer public GapBuffer() { buffer = new char [ 50 ]; for ( int i = 0 ; i < 10 ; i++) { buffer[i] = '_' ; } } // Function to increase the size of the gap public void grow( int k, int position) { char [] a = new char [size]; System.arraycopy(buffer, position, a, 0 , size - position); for ( int i = 0 ; i < k; i++) { buffer[i + position] = '_' ; } System.arraycopy(a, 0 , buffer, position + k, size - position); size += k; gapRight += k; } // Function to move the gap to the left public void left( int position) { while (position < gapLeft) { gapLeft--; gapRight--; buffer[gapRight + 1 ] = buffer[gapLeft]; buffer[gapLeft] = '_' ; } } // Function to move the gap to the right public void right( int position) { while (position > gapLeft) { gapLeft++; gapRight++; buffer[gapLeft - 1 ] = buffer[gapRight]; buffer[gapRight] = '_' ; } } // Function to move the cursor to the desired position public void moveCursor( int position) { if (position < gapLeft) { left(position); } else { right(position); } } // Function to insert a string at a given position public void insert(String input, int position) { int len = input.length(); int i = 0 ; if (position != gapLeft) { moveCursor(position); } while (i < len) { if (gapRight == gapLeft) { int k = 10 ; grow(k, position); } buffer[gapLeft] = input.charAt(i); gapLeft++; i++; position++; } } // Function to delete a character at a given position public void deletion( int position) { if (position + 1 != gapLeft) { moveCursor(position + 1 ); } gapLeft -= 1 ; buffer[gapLeft] = '_' ; } // Function to print the current state of the buffer public void printBuffer() { for ( int i = 0 ; i < size; i++) { System.out.print(buffer[i] + " " ); } System.out.println(); } // Main function to demonstrate the gap buffer operations public static void main(String[] args) { GapBuffer gapBuffer = new GapBuffer(); System.out.println( "Initializing the gap buffer with size 10" ); gapBuffer.printBuffer(); System.out.println( "\nInserting a string to buffer: BeginnerBeginner" ); gapBuffer.insert( "BeginnerBeginner" , 0 ); gapBuffer.printBuffer(); System.out.println( "\nInserting a string to buffer: FOR" ); gapBuffer.insert( "FOR" , 5 ); gapBuffer.printBuffer(); System.out.println( "\nDeleting character at position 5" ); gapBuffer.deletion( 5 ); gapBuffer.printBuffer(); System.out.println( "\nDeleting character at position 6" ); gapBuffer.deletion( 6 ); gapBuffer.printBuffer(); System.out.println( "\nDeleting character at position 5" ); gapBuffer.deletion( 5 ); gapBuffer.printBuffer(); System.out.println( "\nInserting a string to buffer: HELLO" ); gapBuffer.insert( "HELLO" , 0 ); gapBuffer.printBuffer(); } } |
Python3
class GapBuffer: def __init__( self ): # Initializing the gap buffer self . buffer = [ '_' ] * 50 self .gapSize = 10 self .gapLeft = 0 self .gapRight = self .gapSize - 1 self .size = 10 def grow( self , k, position): # Increasing the size of the gap a = self . buffer [position: self .size] self . buffer [position:position + k] = [ '_' ] * k self . buffer [position + k:position + k + self .size - position] = a self .size + = k self .gapRight + = k def left( self , position): # Moving the gap to the left while position < self .gapLeft: self .gapLeft - = 1 self .gapRight - = 1 self . buffer [ self .gapRight + 1 ] = self . buffer [ self .gapLeft] self . buffer [ self .gapLeft] = '_' def right( self , position): # Moving the gap to the right while position > self .gapLeft: self .gapLeft + = 1 self .gapRight + = 1 self . buffer [ self .gapLeft - 1 ] = self . buffer [ self .gapRight] self . buffer [ self .gapRight] = '_' def moveCursor( self , position): # Moving the cursor to the desired position if position < self .gapLeft: self .left(position) else : self .right(position) def insert( self , input , position): # Inserting a string at a given position len_input = len ( input ) i = 0 if position ! = self .gapLeft: self .moveCursor(position) while i < len_input: if self .gapRight = = self .gapLeft: k = 10 self .grow(k, position) self . buffer [ self .gapLeft] = input [i] self .gapLeft + = 1 i + = 1 position + = 1 def deletion( self , position): # Deleting a character at a given position if position + 1 ! = self .gapLeft: self .moveCursor(position + 1 ) self .gapLeft - = 1 self . buffer [ self .gapLeft] = '_' def printBuffer( self ): # Printing the current state of the buffer print ( ' ' .join( self . buffer [: self .size])) if __name__ = = "__main__" : gapBuffer = GapBuffer() print ( "Initializing the gap buffer with size 10" ) gapBuffer.printBuffer() print ( "\nInserting a string to buffer: BeginnerBeginner" ) gapBuffer.insert( "BeginnerBeginner" , 0 ) gapBuffer.printBuffer() print ( "\nInserting a string to buffer: FOR" ) gapBuffer.insert( "FOR" , 5 ) gapBuffer.printBuffer() print ( "\nDeleting character at position 5" ) gapBuffer.deletion( 5 ) gapBuffer.printBuffer() print ( "\nDeleting character at position 6" ) gapBuffer.deletion( 6 ) gapBuffer.printBuffer() print ( "\nDeleting character at position 5" ) gapBuffer.deletion( 5 ) gapBuffer.printBuffer() print ( "\nInserting a string to buffer: HELLO" ) gapBuffer.insert( "HELLO" , 0 ) gapBuffer.printBuffer() |
C#
using System; using System.Linq; public class GapBuffer { private char [] buffer; private int gapSize; private int gapLeft; private int gapRight; private int size; public GapBuffer() { // Initializing the gap buffer this .buffer = Enumerable.Repeat( '_' , 50).ToArray(); this .gapSize = 10; this .gapLeft = 0; this .gapRight = this .gapSize - 1; this .size = 10; } private void Grow( int k, int position) { // Increasing the size of the gap var a = this .buffer.Skip(position).Take( this .size - position).ToArray(); Array.Copy(a, 0, this .buffer, position + k, this .size - position); Array.Fill( this .buffer, '_' , position, k); this .size += k; this .gapRight += k; } private void Left( int position) { // Moving the gap to the left while (position < this .gapLeft) { this .gapLeft--; this .gapRight--; this .buffer[ this .gapRight + 1] = this .buffer[ this .gapLeft]; this .buffer[ this .gapLeft] = '_' ; } } private void Right( int position) { // Moving the gap to the right while (position > this .gapLeft) { this .gapLeft++; this .gapRight++; this .buffer[ this .gapLeft - 1] = this .buffer[ this .gapRight]; this .buffer[ this .gapRight] = '_' ; } } public void MoveCursor( int position) { // Moving the cursor to the desired position if (position < this .gapLeft) { this .Left(position); } else { this .Right(position); } } public void Insert( string input, int position) { // Inserting a string at a given position int len_input = input.Length; int i = 0; if (position != this .gapLeft) { this .MoveCursor(position); } while (i < len_input) { if ( this .gapRight == this .gapLeft) { int k = 10; this .Grow(k, position); } this .buffer[ this .gapLeft] = input[i]; this .gapLeft++; i++; position++; } } public void Deletion( int position) { // Deleting a character at a given position if (position + 1 != this .gapLeft) { this .MoveCursor(position + 1); } this .gapLeft--; this .buffer[ this .gapLeft] = '_' ; } public void PrintBuffer() { // Printing the current state of the buffer Console.WriteLine( new string ( this .buffer.Take( this .size).ToArray())); } } class Program { static void Main( string [] args) { var gapBuffer = new GapBuffer(); Console.WriteLine( "Initializing the gap buffer with size 10" ); gapBuffer.PrintBuffer(); Console.WriteLine( "\nInserting a string to buffer: BeginnerBeginner" ); gapBuffer.Insert( "BeginnerBeginner" , 0); gapBuffer.PrintBuffer(); Console.WriteLine( "\nInserting a string to buffer: FOR" ); gapBuffer.Insert( "FOR" , 5); gapBuffer.PrintBuffer(); Console.WriteLine( "\nDeleting character at position 5" ); gapBuffer.Deletion(5); gapBuffer.PrintBuffer(); Console.WriteLine( "\nDeleting character at position 6" ); gapBuffer.Deletion(6); gapBuffer.PrintBuffer(); Console.WriteLine( "\nDeleting character at position 5" ); gapBuffer.Deletion(5); gapBuffer.PrintBuffer(); Console.WriteLine( "\nInserting a string to buffer: HELLO" ); gapBuffer.Insert( "HELLO" , 0); gapBuffer.PrintBuffer(); } } |
Javascript
class GapBuffer { constructor() { // Initializing the gap buffer this .buffer = Array(50).fill( '_' ); this .gapSize = 10; this .gapLeft = 0; this .gapRight = this .gapSize - 1; this .size = 10; } grow(k, position) { // Increasing the size of the gap let a = this .buffer.slice(position, this .size); this .buffer.splice(position, this .size - position, ...Array(k).fill( '_' )); this .buffer.splice(position + k, a.length, ...a); this .size += k; this .gapRight += k; } left(position) { // Moving the gap to the left while (position < this .gapLeft) { this .gapLeft--; this .gapRight--; this .buffer[ this .gapRight + 1] = this .buffer[ this .gapLeft]; this .buffer[ this .gapLeft] = '_' ; } } right(position) { // Moving the gap to the right while (position > this .gapLeft) { this .gapLeft++; this .gapRight++; this .buffer[ this .gapLeft - 1] = this .buffer[ this .gapRight]; this .buffer[ this .gapRight] = '_' ; } } moveCursor(position) { // Moving the cursor to the desired position if (position < this .gapLeft) { this .left(position); } else { this .right(position); } } insert(input, position) { // Inserting a string at a given position let len_input = input.length; let i = 0; if (position != this .gapLeft) { this .moveCursor(position); } while (i < len_input) { if ( this .gapRight == this .gapLeft) { let k = 10; this .grow(k, position); } this .buffer[ this .gapLeft] = input[i]; this .gapLeft++; i++; position++; } } deletion(position) { // Deleting a character at a given position if (position + 1 != this .gapLeft) { this .moveCursor(position + 1); } this .gapLeft--; this .buffer[ this .gapLeft] = '_' ; } printBuffer() { // Printing the current state of the buffer console.log( this .buffer.slice(0, this .size).join( ' ' )); } } // Main function to demonstrate the gap buffer operations let gapBuffer = new GapBuffer(); console.log( "Initializing the gap buffer with size 10" ); gapBuffer.printBuffer(); console.log( "\nInserting a string to buffer: BeginnerBeginner" ); gapBuffer.insert( "BeginnerBeginner" , 0); gapBuffer.printBuffer(); console.log( "\nInserting a string to buffer: FOR" ); gapBuffer.insert( "FOR" , 5); gapBuffer.printBuffer(); console.log( "\nDeleting character at position 5" ); gapBuffer.deletion(5); gapBuffer.printBuffer(); console.log( "\nDeleting character at position 6" ); gapBuffer.deletion(6); gapBuffer.printBuffer(); console.log( "\nDeleting character at position 5" ); gapBuffer.deletion(5); gapBuffer.printBuffer(); console.log( "\nInserting a string to buffer: HELLO" ); gapBuffer.insert( "HELLO" , 0); gapBuffer.printBuffer(); |
Output
Initializing the gap buffer with size 10 _ _ _ _ _ _ _ _ _ _ Inserting a string to buffer: BeginnerBeginner Output: G E E K S G E E K S _ _ _ _ _ _ _ _ _ _ Inserting a string to buffer: FOR Output: G E ...
Contact Us