¿Cómo implementarías un gap buffer para un editor de texto?

1. Problema y contexto

Implementa el búfer central para un editor de texto de un solo cursor. El texto lógico es una secuencia de caracteres; el cursor se ubica entre dos caracteres. Admite left(), right(), insert(ch), delete() y text().

Representa el almacenamiento como un arreglo con un intervalo no utilizado llamado gap (hueco). Considera gapStart inclusivo y gapEnd exclusivo. El texto visible es el prefijo antes de gapStart seguido del sufijo en y después de gapEnd. El ejercicio de ETH Zurich utiliza esta representación y pide a los candidatos verificar tanto el comportamiento como los límites. Un reporte público de una entrevista L4 de Google también describe una ronda de implementación de editor de texto/contabilidad que enfatizó las ventajas y desventajas de las estructuras de datos, pruebas manuales (dry runs) y complejidad precisa.

2. Qué evalúa el entrevistador

• Modelado de estado: ¿Puedes indicar qué significan los dos índices sin confundir la longitud lógica y la capacidad del arreglo?
• Invariantes: ¿Cada operación y redimensionamiento preservan los límites válidos y el mismo texto lógico?
• Disciplina en los límites: ¿Se manejan explícitamente los búferes vacíos, llenos, en el borde izquierdo, en el borde derecho y de un solo carácter?
• Razonamiento sobre complejidad: ¿Puedes explicar por qué las ediciones cercanas son económicas y un salto largo del cursor es lineal con respecto a la distancia?
• Criterio de diseño: ¿Puedes indicar cuándo un gap buffer deja de ser adecuado para archivos grandes, múltiples cursores o edición colaborativa?

Una respuesta débil escribe primero los movimientos de arreglos y descubre errores de tipo "off-by-one" más tarde. Una respuesta sólida deriva cada movimiento a partir de la representación y lo prueba contra un modelo de cadena simple.

3. Preguntas para aclarar primero

¿El cursor es un índice de carácter o un límite?

Usa un límite: cursor equivale al número de caracteres lógicos a su izquierda. Esto hace que cursor=0 sea el borde izquierdo y cursor=length el borde derecho, y define delete() como la eliminación del carácter inmediatamente anterior al cursor.

¿Qué significa delete en la posición del cursor?

Confirma si se refiere a Backspace o a Delete. Este artículo utiliza la semántica de Backspace: mover el gap un espacio a la izquierda y agrandarlo. Una operación de borrado hacia adelante (forward-delete) consumiría en su lugar el primer carácter después del gap.

¿Qué modelo de almacenamiento y texto se requieren?

Aclara si se usan bytes o valores escalares de Unicode, el tamaño máximo del documento y si se requieren deshacer (undo), búsqueda aleatoria de líneas, múltiples cursores o ediciones concurrentes. Esos requisitos pueden cambiar la estructura de datos en lugar de simplemente añadir métodos.

4. Estructura de respuesta de 30 segundos

“Almacenaría el documento en un solo arreglo con un gap en la posición del cursor. gapStart es el límite del cursor y gapEnd marca el primer carácter del sufijo; el texto lógico es el prefijo más el sufijo. La inserción escribe en gapStart y lo avanza. Backspace mueve un carácter del prefijo a través del gap y decrementa ambos índices. Moverse hacia la derecha copia un carácter del sufijo al lado del prefijo y avanza ambos índices. Si el gap está vacío, se redimensiona el arreglo aumentando su tamaño y se crea un gap más grande. Aseguraría los límites y la equivalencia con un modelo de cadena después de cada operación. Las ediciones cercanas toman tiempo constante amortizado; mover el gap es lineal respecto a la distancia, por lo que archivos grandes o muchos cursores pueden requerir una piece table o un rope”.

5. Solución paso a paso

Paso 1: Establecer el invariante de representación

Para una capacidad n, se requiere 0 ≤ gapStart ≤ gapEnd ≤ n. La longitud lógica es n - (gapEnd - gapStart). La secuencia lógica es buffer[0:gapStart] concatenada con buffer[gapEnd:n]. Los valores dentro del gap se ignoran y no necesitan inicializarse.

Paso 2: Mover a la izquierda

Si gapStart == 0, el cursor ya está en el borde izquierdo. De lo contrario, decrementa gapStart y gapEnd, luego copia el carácter que estaba inmediatamente antes del cursor en la nueva última posición del gap. El prefijo pierde un carácter y el sufijo no gana ninguno; el carácter copiado queda ahora lógicamente antes del gap.

Paso 3: Mover a la derecha

Si gapEnd == n, el cursor está en el borde derecho. De lo contrario, copia buffer[gapEnd] en buffer[gapStart], luego incrementa ambos índices. El primer carácter del sufijo cruza el gap, preservando el orden de la secuencia. El orden de la copia y de las actualizaciones de índices es importante cuando el gap tiene una sola ranura.

Paso 4: Insertar

Si gapStart == gapEnd, llama a grow() antes de escribir. Almacena el carácter en buffer[gapStart] e incrementa gapStart. El nuevo carácter se convierte en el último elemento del prefijo, exactamente en el límite anterior del cursor.

Paso 5: Eliminar hacia atrás

Si gapStart == 0, no hay ningún carácter a la izquierda. De lo contrario, decrementa gapStart; el gap ahora incluye el carácter eliminado. No es necesario realizar ningún desplazamiento en el arreglo. La secuencia lógica pierde su carácter final del prefijo.

Paso 6: Aumentar el tamaño sin cambiar el texto

Asigna un arreglo más grande, copia el prefijo en los mismos índices y copia el sufijo al final del nuevo arreglo. Mantén gapStart sin cambios y establece el nuevo gapEnd de modo que la longitud del sufijo se mantenga constante. Una política de capacidad geométrica, como duplicar el tamaño, proporciona inserción en tiempo constante amortizado cuando las ediciones se mantienen cerca del gap, pero los límites de memoria pueden justificar un factor de crecimiento menor.

Paso 7: Elegir deliberadamente la siguiente estructura

Un gap buffer resulta atractivo para un solo cursor activo y ediciones locales porque la región activa se mantiene contigua. Una piece table conserva búferes originales y de solo adición (append-only), siendo útil para editores orientados a deshacer acciones. Un rope o árbol de fragmentos maneja documentos grandes y ediciones distribuidas en posiciones distantes. Un editor colaborativo añade requisitos de transformación operacional o CRDT que un gap buffer no resuelve.

6. Respuesta de muestra de alta calidad

“Modelaría el cursor como un límite y mantendría dos índices alrededor de un gap no utilizado. El invariante es 0 ≤ gapStart ≤ gapEnd ≤ capacity; el texto lógico es el prefijo antes del gap más el sufijo después de este. La inserción consume una ranura del gap. Backspace decrementa gapStart, y la flecha derecha copia un carácter del sufijo al lado del prefijo mientras incrementa ambos índices. La flecha izquierda realiza la copia simétrica en la dirección opuesta. Cuando el gap está vacío, incremento el almacenamiento copiando el sufijo a la nueva cola, lo que preserva la secuencia lógica.

Probaría las operaciones comparándolas con un modelo simple de cadena más cursor, incluyendo un búfer vacío, un gap lleno, ambos bordes, texto de un solo carácter, inversiones repetidas y crecimiento. Las ediciones locales son de costo amortizado O(1); un movimiento de cursor cuesta O(1) por cada carácter cruzado, y un redimensionamiento cuesta O(n). Para archivos grandes, múltiples cursores o ediciones colaborativas cambiaría a una piece table o rope, ya que el único gap contiguo se convierte en el cuello de botella”.

7. Errores comunes

• Tratar gapEnd como inclusivo → Copia o verifica límites una celda más allá → Define el gap como [gapStart, gapEnd) y prueba con un gap vacío.
• Mover a la derecha después de incrementar primero → Lee la celda de sufijo incorrecta → Copia buffer[gapEnd] a buffer[gapStart] antes de cambiar cualquiera de los índices.
• Eliminar limpiando una celda del arreglo → Deja la longitud lógica y el cursor sin cambios → Expande el gap decrementando gapStart.
• Crecer moviendo solo el gap → Reordena o pierde el sufijo → Copia el sufijo como un bloque al final del nuevo arreglo.
• Usar bytes sin un contrato → Puede dividir un carácter multibyte → Declara la semántica de bytes o escalares antes de implementar el movimiento del cursor.
• Afirmar que cada edición es O(1) → Ignora los desplazamientos largos del cursor y el redimensionamiento → Especifica el costo amortizado de edición local y los casos lineales de movimiento/crecimiento.
• Usar un gap buffer para colaboración → Confunde el almacenamiento local con la semántica de fusión → Elige una arquitectura de piece table, rope o CRDT según los requisitos de colaboración.

8. Preguntas de seguimiento

¿Cómo implementarías forward Delete?

Si gapEnd == capacity, no hay ningún carácter después del cursor. De lo contrario, incrementa gapEnd; el primer carácter del sufijo entra en el gap y desaparece de la secuencia lógica. Este es el espejo de Backspace y preserva el mismo invariante.

¿Cuál es el peor caso al mover el cursor?

Moverse a través de k caracteres realiza k copias de tiempo constante, por lo que es O(k). Saltar de un extremo al otro es O(length). Un índice de líneas o una estructura fragmentada puede reducir el trabajo de navegación cuando el editor salta frecuentemente a posiciones distantes.

¿Cómo añadirías la función de deshacer (undo)?

Registra comandos de edición o rangos inversos en lugar de instantáneas de todo el arreglo. Una piece table puede hacer que el texto insertado sea de solo adición y simplificar las referencias históricas, mientras que un gap buffer necesita un registro de operaciones explícito y posiciones del cursor.

¿Cómo verificas la implementación?

Ejecuta trazas de operaciones aleatorias contra un par de referencia (string, cursor). Después de cada operación, compara text(), la posición del cursor y los límites. Agrega aserciones de que cada acceso al arreglo esté dentro de la capacidad; el ejercicio de ETH Zurich solicita explícitamente la verificación del comportamiento y de los límites.