Gap Buffer es una estructura de datos utilizada para editar y almacenar texto de manera eficiente que se está editando actualmente . También es similar a una array, pero se introduce un espacio en la array para manejar múltiples cambios en el cursor . Supongamos que un espacio es otra array que contiene espacios vacíos. Ejemplo: considere un ejemplo con un tamaño de espacio inicial de 10, inicialmente, la array o el espacio son del mismo tamaño, a medida que insertamos los elementos en la array, los elementos se insertarán de manera similar en el búfer de espacio, la única diferencia es que el tamaño del espacio se reduce en cada inserción .
Este fue el caso básico para insertar el personaje en el frente. Ahora, cada vez que sea necesario insertar un carácter en cierta posición, simplemente moveremos el espacio hacia esa posición usando izquierda() y derecha() y luego intentaremos insertar el carácter.
Necesidad de búfer de brecha
- Array es una estructura de datos que almacena elementos en una ubicación de memoria contigua. Sin embargo, se necesita la inserción de O(1) al final de la array mientras que el tiempo de O(n) está al frente porque la array se desplazará n lugares a la derecha, siendo n la longitud de la array.
- Cuando se trata de editores de texto, necesitamos una estructura de datos más rápida para la inserción y modificación, ya que hay múltiples cambios en las posiciones del cursor.
- En el peor de los casos, la array tardará O(n) tiempo en insertarse o modificarse, como se muestra en el siguiente ejemplo.
- Para insertar ‘GEEKS’ al frente, se hace espacio para insertar cada carácter cambiando la array.
Operaciones básicas en Gap Buffer
- insert(): es un procedimiento utilizado para insertar caracteres en el texto en una posición determinada. Primero verifica si el espacio está vacío o no, si encuentra que el espacio está vacío, llama al procedimiento grow() y cambia el tamaño del espacio y ahora se puede insertar el elemento.
- left() : Es un procedimiento usado para mover el cursor a la izquierda y este punto del cursor se usa como posición para cambios.
- derecha: Es un procedimiento utilizado para mover el cursor a la derecha y este punto del cursor se utiliza como posición para los cambios.
- grow: es un procedimiento que se usa cuando el tamaño del espacio se ha convertido en cero y, por lo tanto, necesitamos cambiar el tamaño de la array insertando un espacio en la posición deseada.
Gap Buffer vs Cuerdas
Ahora, aunque su inserción toma un tiempo O(1), hay otra función grow() que toma aproximadamente un tiempo O(n). Por lo tanto, podría pensarse que esto puede tomar el mismo tiempo que las estructuras de datos de cuerda , pero el costo de crecimiento se compensa con el costo amortizado de otros procedimientos más baratos como left(), right() e insert(). Por lo tanto, esta estructura de datos obtiene preferencias en los editores de texto sobre otros, como la cuerda , ya que es fácil de implementar.
Implementando Gap Buffer
C++
// C++ program of implementation of gap buffer
#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++;
}
}
// 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 = "GEEKSGEEKS";
int position = 0;
insert(input, position);
cout << endl;
cout << "Inserting a string to buffer"
<< ": GEEKSGEEKS" << endl;
cout << "Output: ";
for (int i = 0; i < size; i++) {
cout << buffer[i]<<" ";
}
input = "FOR";
position = 5;
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]<<" ";
}
return 0;
}
Java
// Java program of implementation of gap buffer
import java.util.*;
class GFG
{
static char []buffer = new char[50];
static int gap_size = 10;
static int gap_left = 0;
static int gap_right = gap_size - gap_left - 1;
static int size = 10;
// Function that is used to grow the gap
// at index position and return the array
static void grow(int k, int position)
{
char []a = new char[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 < 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
static 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
static 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
static 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
static 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.charAt(i);
gap_left++;
i++;
position++;
}
}
// Driver code
public static void main(String[] args)
{
// Initializing the gap buffer with size 10
for (int i = 0; i < 10; i++)
{
buffer[i] = '_';
}
System.out.println("Initializing the gap" +
" buffer with size 10");
for (int i = 0; i < size; i++)
{
System.out.print(buffer[i] + " ");
}
System.out.println();
// Inserting a string to buffer
String input = "GEEKSGEEKS";
int position = 0;
insert(input, position);
System.out.println();
System.out.println("Inserting a string " +
"to buffer: GEEKSGEEKS");
System.out.print("Output: ");
for (int i = 0; i < size; i++)
{
System.out.print(buffer[i] + " ");
}
input = "FOR";
position = 5;
insert(input, position);
System.out.println();
System.out.println();
System.out.println("Inserting a string" +
" to buffer: FOR");
System.out.print("Output: ");
for (int i = 0; i < size; i++)
{
System.out.print(buffer[i] + " ");
}
}
}
// This code is contributed by Princi Singh
C#
// C# program of implementation of gap buffer
using System;
class GFG
{
static char []buffer = new char[50];
static int gap_size = 10;
static int gap_left = 0;
static int gap_right = gap_size - gap_left - 1;
static int size = 10;
// Function that is used to grow the gap
// at index position and return the array
static void grow(int k, int position)
{
char []a = new char[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 < 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
static 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
static 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
static 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
static 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++;
}
}
// Driver code
public static void Main(String[] args)
{
// Initializing the gap buffer with size 10
for (int i = 0; i < 10; i++)
{
buffer[i] = '_';
}
Console.WriteLine("Initializing the gap" +
" buffer with size 10");
for (int i = 0; i < size; i++)
{
Console.Write(buffer[i] + " ");
}
Console.WriteLine();
// Inserting a string to buffer
String input = "GEEKSGEEKS";
int position = 0;
insert(input, position);
Console.WriteLine();
Console.WriteLine("Inserting a string " +
"to buffer: GEEKSGEEKS");
Console.Write("Output: ");
for (int i = 0; i < size; i++)
{
Console.Write(buffer[i] + " ");
}
input = "FOR";
position = 5;
insert(input, position);
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("Inserting a string" +
" to buffer: FOR");
Console.Write("Output: ");
for (int i = 0; i < size; i++)
{
Console.Write(buffer[i] + " ");
}
}
}
// This code is contributed by 29AjayKumar
Producción:
Initializing the gap buffer with size 10 _ _ _ _ _ _ _ _ _ _ Inserting a string to buffer: GEEKSGEEKS Output: G E E K S G E E K S _ _ _ _ _ _ _ _ _ _ Inserting a string to buffer: FOR Output: G E E K S F O R _ _ _ _ _ _ _ G E E K S
Complejidad temporal de inserción: O(1) Complejidad temporal de crecimiento: O(n)
Publicación traducida automáticamente
Artículo escrito por Harshit-Agarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA