Estructura de datos para el editor de texto

Question

Esta es una pregunta de la entrevista. ¿Qué estructura de datos usarías para almacenar el texto en un editor de texto?

Answer 1

En el viejo ZX-Spectrum uno (o más, no sé) text exditor usó una estructura muy simple.

Había un gran búfer, que ocupaba toda la memoria RAM libre. El texto se dividió en dos partes con el cursor. Parte anterior al cursor, se colocó al principio del búfer y el resto al final del búfer. A medida que se escribe el texto, los datos simplemente se agregan al final de la primera parte, y cuando se mueve el cursor, el texto se copia y retrocede. diseño

Buffer:

Hello, World! 
     ^------Cursor here 

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|H|e|l|l|o|,| |W| <free> |o|r|l|d|!| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|    ^  ^  | 
begin   cur1  cur2 end 

eso es, cómo se hizo algunas operaciones de edición:

Type a char: buffer[cur1++] = character 

Backspace:  cur1-- 

Cursor left: buffer[--cur2] = buffer[--cur1] 

Cursor right: buffer[cur1++] = buffer[cur2++] 

búfer en acción:

   Hello, W..............orld! 
Press right  ^   ^
      Hello, Wo..............rld! 
Press backspace  ^   ^
      Hello, W...............rld! 
Press 0   ^   ^
      Hello, W0..............rld! 
        ^   ^

Answer 2

Usted puede encontrar este interesante, incluso si no responde exactamente a su pregunta:

Most efficient data structure to add styles to text

Estoy esperando que la discusión va a ir a lugares fascinantes :-)

Answer 3

Rope

Una cuerda es esencialmente un árbol binario cuyas hojas son matrices de caracteres. Un nodo en el árbol tiene un hijo izquierdo y un hijo derecho: el niño izquierdo es la primera parte de la cadena, mientras que el niño derecho es la parte final de la cadena. La concatenación de dos cables simplemente implica la creación de un nuevo nodo de árbol con ambas cuerdas como elementos secundarios. Para garantizar la indexación del tiempo logarítmico y las operaciones de subcadena, es posible que la cuerda resultante deba equilibrarse. Varias estrategias de equilibrio son posibles.

Las ventajas principales de los cables en comparación con el almacenamiento de cadenas como matrices de caracteres es que permiten una concatenación mucho más rápida que las cadenas ordinarias, y no requieren un gran espacio contiguo de memoria para almacenar una cadena grande. Las principales desventajas son un mayor uso general del espacio y una indexación más lenta, que se vuelven más graves a medida que la estructura del árbol se hace más grande y más profunda. Sin embargo, muchas aplicaciones prácticas de indexación implican solo una iteración sobre la cadena, que permanece rápida siempre que los nodos de hoja sean lo suficientemente grandes como para beneficiarse de los efectos de caché.

Answer 4

Sé que es demasiado tarde para una respuesta, pero encontré el libro The Craft of Text Editing realmente útil. Contiene la descripción de varios modelos de búfer con sus pros y sus contras. Lamentablemente, no menciona la estructura de datos de Ropes.

Answer 5

Como @Vovanium ya mencionó la teoría básica de cómo se puede utilizar el búfer de huecos, he implementado una versión de C/C++.

Código:

#include <stdio.h> 
#define SZ 1000 

char leftArray[SZ], rightArray[SZ]; 
int leftCount, rightCount; 
int cursorPos; 

/* 
* Private APIs 
*/ 

void printArray(){ 

    for(register int i = 0; i < leftCount; i++){ 
     printf("%c", leftArray[i]); 
    } 

    for(register int i = rightCount - 1; i >= 0; i--){ 
     printf("%c", rightArray[i]); 
    } 
    printf("\n"); 
} 

void adjust(int pos){ 

    while(leftCount > pos){ 
     rightArray[rightCount++] = leftArray[--leftCount]; 
    } 

    while(leftCount < pos){ 
     leftArray[leftCount++] = rightArray[--rightCount]; 
    } 
} 


/* 
* Public APIs for Text Editor 
*/ 

void init(){ 

    cursorPos = leftCount = rightCount = 0; 
} 

void addWord(char word[], int len){ 

    adjust(cursorPos); 

    for(register int i = 0; i < len; i++){ 
     leftArray[leftCount++] = word[i]; 
    } 
    leftArray[leftCount] = 0; 
} 

void addBackSpace(){ 

    adjust(cursorPos); 
    leftCount--; 
} 

void moveCurson(int newPosition){ 

    cursorPos = newPosition; 
} 

void subString(int pos, int length, char result[]){ 

     adjust(cursorPos); 

    int k = 0; 
     int l = 0; 
    while(k + pos < leftCount && k < length){ 
     result[k] = leftArray[pos + k]; 
     k++; 
    } 

    length -= k; 
    while(l < length){ 
     result[k++] = rightArray[rightCount - 1 - l]; 
     l++; 
    } 
}