Android compose状态缓存算法

Gap Buffer 是一种数据结构，用于以有效的方式编辑和存储当前正在编辑的文本。它也类似于数组，但在数组中引入了一个间隙，用于处理光标处的多个更改。让我们假设一个间隙是另一个包含空格的数组。

示例：考虑一个初始间隙大小为 10 的示例，最初，数组或间隙大小相同，因为我们将元素插入数组中，类似地元素将被插入间隙缓冲区，唯一的区别是每次插入时间隙大小都会减小。

前面插入字符的基本情况。现在，每当需要在某个位置插入字符时，我们只需使用 left() 和 right()将间隙向上移动到该位置，然后尝试插入字符。

需要间隙缓冲器

• 数组是一种将项目存储在连续内存位置的数据结构。但是，在数组末尾需要 O(1) 插入，而前面需要 O(n) 时间，因为数组将向右移动 n
  个位置，n 是数组的长度。
• 当涉及到文本编辑器时，我们需要一个更快的数据结构来进行插入和修改，因为光标位置有多个更改。
• 在最坏的情况下，数组将花费 O(n) 时间来插入或修改，如下例所示。
• 为了在前面插入“GEEKS”，通过移动数组来为插入每个字符留出空间。

Gap Buffer中的基本操作

• insert()：这是一个用于在给定位置将字符插入文本的过程。它首先检查间隙是否为空，如果发现间隙为空，则调用过程grow()并调整间隙的大小，现在可以插入元素。
• left() ：这是一个用于将光标向左移动的过程，该光标点用作更改的位置。
  
• right：这是一个用于将光标向右移动的程序，该光标点用作更改的位置。
  
• 增长：这是在间隙大小变为零时使用的过程，因此我们需要通过在所需位置插入间隙来调整数组的大小。
  

间隙缓冲器与绳索

现在，虽然它的插入需要 O(1) 时间，但还有另一个函数**grow()**大约需要 O(n) 时间。因此可能会认为这可能与绳索数据结构花费相同的时间，但增长的成本正在通过其他更便宜的过程（例如 left()、right() 和 insert()）的摊销成本来补偿。因此，这种数据结构在文本编辑器中优于其他数据结构，例如绳索，因为它易于实现。

实现间隙缓冲区

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

输出

初始化大小为 10 的间隙缓冲区
_ _ _ _ _ _ _ _ _ _ 


将字符串插入缓冲区：GEEKSGEEKS
输出：GEEKSGEEKS _ _ _ _ _ _ _ _ _ _

将字符串插入缓冲区：FOR
输出：GEEKSFOR _ _ _ _ _ _ _ GEEKS

插入的时间复杂度：O(1) 增长的时间复杂度：O(n)

https://www.geeksforgeeks.org/gap-buffer-data-structure/