如何在间隙缓冲区（Gap Buffer）中实现光标上下行遍历？

核心思路 #

光标上下移动的本质是：先确定当前光标所在的列数，再在目标行中找到对应列的位置（若目标行长度不足，则停在行尾）。关键难点是正确处理间隙缓冲区的无效区域，避免被间隙内的残留数据干扰。

方案一：局部扫描实现（无额外空间开销） #

这种方案无需维护额外数据结构，仅通过局部扫描完成定位，适合小型文本编辑器场景。核心是扫描时跳过间隙区域。

步骤1：计算当前光标所在列数 #

从光标位置向左扫描，直到遇到换行符或缓冲区开头，统计这段区域内的有效字符数（跳过间隙），即为当前列号。

size_t get_current_column(GapBuffer *gb, size_t cursor) {
    size_t col = 0;
    size_t pos = cursor;
    while (pos > 0) {
        // 遇到间隙，直接跳到间隙起始位置
        if (pos > gb->gap_start && pos <= gb->gap_end) {
            pos = gb->gap_start;
            continue;
        }
        // 找到换行符，停止扫描
        if (gb->buffer[pos - 1] == '\n') {
            break;
        }
        col++;
        pos--;
    }
    return col;
}

步骤2：实现光标向上移动 #

1. 从当前光标位置向左扫描，找到上一个换行符的位置；若找不到，说明已是第一行，无法上移。
2. 从上一行的起始位置（换行符的下一个位置）开始，向右扫描对应列数的有效字符，遇到行尾或换行符则停止。

bool move_cursor_up(GapBuffer *gb, size_t *cursor) {
    size_t current_col = get_current_column(gb, *cursor);
    size_t pos = *cursor;
    size_t prev_newline = 0;
    bool found_newline = false;

    // 查找上一个换行符
    while (pos > 0) {
        if (pos > gb->gap_start && pos <= gb->gap_end) {
            pos = gb->gap_start;
            continue;
        }
        if (gb->buffer[pos - 1] == '\n') {
            prev_newline = pos - 1;
            found_newline = true;
            break;
        }
        pos--;
    }
    if (!found_newline) {
        return false; // 处于第一行，无法上移
    }

    // 定位到目标行的对应列
    pos = prev_newline + 1;
    size_t count = 0;
    while (count < current_col) {
        // 跳过间隙
        if (pos >= gb->gap_start && pos < gb->gap_end) {
            pos = gb->gap_end;
            if (pos >= gb->buffer_size) break;
        }
        // 到达行尾或缓冲区末尾，停止
        if (pos >= gb->buffer_size || gb->buffer[pos] == '\n') {
            break;
        }
        count++;
        pos++;
    }
    *cursor = pos;
    return true;
}

步骤3：实现光标向下移动 #

逻辑与向上移动对称：

1. 从当前光标位置向右扫描，找到下一个换行符的位置；若找不到，说明已是最后一行，无法下移。
2. 从下一行的起始位置开始，向右扫描对应列数的有效字符，遇到行尾则停止。

方案二：维护换行符索引数组（空间换时间） #

如果需要处理大文档，局部扫描的O(n)时间复杂度可能不够高效，可维护一个动态数组存储所有换行符的位置，通过二分查找快速定位行信息。

核心操作 #

• 插入换行符：用二分查找确定新换行符在数组中的位置，插入该索引；若插入位置在已有换行符之前，将后续所有换行符的索引加1。
• 删除换行符：从数组中移除对应索引；若删除位置在已有换行符之前，将后续所有换行符的索引减1。
• 定位上下行：通过二分查找找到当前光标所在行，直接获取上一行/下一行的换行符位置，再定位对应列。

这种方案的行定位时间复杂度为O(log n)，适合大型文本场景。

关键注意事项 #

1. 强制跳过间隙：所有扫描操作必须检查当前位置是否处于gap_start到gap_end之间，若是则直接跳转到间隙末尾（上移时跳转到间隙起始），完全忽略间隙内的残留数据。
2. 边缘场景处理：
   • 光标处于行首/行尾时，移动后需停在目标行的对应边缘。
   • 目标行长度短于当前列数时，光标停在目标行的末尾。
   • 缓冲区为空或仅一行时，禁止上下移动。

内容的提问来源于stack exchange，提问作者SPIGS