Gap Buffer

Gap Buffer

• Composer가 사용하는 메모리 구조는 Gap Buffer와 유사합니다.

• Gap Buffer는 버퍼 또는 배열의 요소를 동적으로 삽입 및 삭제하기 위한 데이터 구조입니다.

• 요소의 빠르고 동적인 삽입 및 삭제가 중요한 텍스트 편집기와 같은 실시간 응용 프로그램을 위한 효율적인 데이터 구조로 설게되었습니다. 현재 커서 위치에 요소를 삽입하기 위해 O(1)의 평균 시간 복잡도를 제공하므로 짧은 대기 시간이 필요한 응용 프로그램에 적합합니다.

• 효율성 및 실시간 기능 외에도 Gap Buffer는 공간 효율적인 데이터 구조이기도 합니다.

• Gap Buffer 데이터 구조는 구현이 상대적으로 간단합니다.

• 현재 편집중인 텍스트를 효율적으로 편집하고 저장하는 데 사용되는 데이터 구조입니다.

• 간격 크기ㅏ 0이 되어 원차는 위치에 간격을 삽입하여 배열의 크기를 조정해야 할 때 grow 절차를 거쳐야 합니다.

// 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