Qué estructura/s de datos se utiliza en la implementación de editores como bloc de notas. Esta estructura de datos debe ser extensible, y debe admitir varias características como edición, eliminación, desplazamiento, selección de rango de texto, etc.¿Cuál es la mejor estructura de datos adecuada para implementar editor como bloc de notas?
Mira la implementación de Notepad ++, puede ver la fuente de SourceForge
Salida Ropes. Maneja inserción/eliminación/edición rápida de cadenas. Los rangos suelen ser compatibles con las implementaciones de Rope, y el desplazamiento se puede realizar con un índice invertido en la cuerda.
Lo habitual es tener algo así como una lista o una matriz de matrices de caracteres. Se han hecho muchas cosas al respecto a lo largo de los años: puede echarle un vistazo al this google search.
Escribimos un editor para una máquina vieja (tenga en cuenta que esto fue hace un momento, alrededor de 1986, así que esto es de memoria, y el estado del arte puede haber avanzado un poco desde entonces) que logramos obtener para gritar, en cuanto al rendimiento, mediante el uso de bloques de memoria fija de grupos autogestionados.
Tenía dos piscinas, cada una con un número fijo de bloques de tamaño específico (un grupo era para estructuras de línea, el otro para estructuras de segmento de línea). Básicamente era una lista vinculada de listas enlazadas.
La memoria fue preasignada (para cada región) de una llamada similar a 'malloc()', y utilizamos 65,535 bloques (0 a 65,534 inclusive, el bloque número 65,535 se consideró el bloque nulo, un indicador de fin de lista)
Esto permitió cada uno para 65, 535 líneas (384K o 512K para la versión acolchada) y aproximadamente 1.6G de tamaño de archivo (teniendo 2G de espacio asignado), que era bastante grande en aquel entonces. Ese fue el límite de tamaño de archivo teórico - No creo que alguna vez nos hayamos aproximado a esto en realidad ya que nunca asignamos el conjunto completo de estructuras de segmento de línea.
No tener que llamar al malloc() por cada pequeño bloque de memoria nos dio un gran aumento de velocidad, especialmente porque pudimos optimizar nuestras propias rutinas de asignación de memoria para bloques de tamaño fijo (incluida la inclusión de llamadas en la versión optimizada final).
Las estructuras en las dos piscinas eran como sigue, siendo cada línea de un solo byte):
Line structure (6/8 bytes) Line-segment structure (32 bytes)
+--------+ +--------+
|NNNNNNNN| |nnnnnnnn|
|NNNNNNNN| |nnnnnnnn|
|PPPPPPPP| |pppppppp|
|PPPPPPPP| |pppppppp|
|bbbbbbbb| |LLLLLLLL|
|bbbbbbbb| |LLLLLLLL|
|........| |xxxxxxxx|
|........| :25 more :
+--------+ : x lines:
+--------+
donde: letras
x punto a la piscina segmento de línea .N era un número de bloque para la siguiente línea (null significa que esta era la última línea del archivo).P el número de bloque para la línea anterior (null significa que esta era la primera línea en el archivo).b era el número de bloque para el primer segmento de línea en esa línea (nulo significa que la línea estaba vacía).. se reservó el relleno (para superar la estructura a 8 bytes).n era el número de bloque para el siguiente segmento de línea (null significa que este era el último segmento en la línea).p era el número de bloque para el segmento de línea anterior (null significa que este era el primer segmento en la línea).L era el número de bloque para el bloque de línea del segmento.x fueron los 26 caracteres en ese segmento de línea.La razón la estructura de línea se impregnó era acelerar la conversión de números de bloque en ubicaciones de memoria reales (desplazando dejados por 3 bits era mucho más rápido que multiplicando por 6 en que la arquitectura particular y de memoria adicional utiliza sólo 128K fue , mínimo en comparación con el almacenamiento total utilizado) aunque proporcionamos la versión más lenta para los que se preocuparon más por la memoria.
También teníamos una matriz de 100 valores de 16 bits que contenían el segmento de línea (y el número de línea para poder ir rápidamente a líneas específicas) aproximadamente en ese porcentaje (de modo que la matriz [7] era la línea que 7% en el archivo) y dos punteros gratuitos para mantener la lista libre en cada conjunto (esta era una lista de una manera muy simple donde N o n en la estructura indicaban que se asignaron los siguientes bloques libres y libres, y se volvieron a , el frente de estas listas).
No hubo necesidad de contar los caracteres en cada segmento de línea ya que los 0 bytes no eran válidos en los archivos. Se permitió que cada segmento de línea tuviera 0 bytes al final que se ignoraron por completo. Las líneas se comprimieron (es decir, los segmentos de línea se combinaron) cada vez que se modificaron. Esto mantuvo el uso de bloques bajo (sin recolección de basura poco frecuente y larga) y también aceleró mucho las operaciones de búsqueda y reemplazo.
El uso de estas estructuras permitió muy edición rápida, inserción, eliminación, búsqueda y navegación alrededor del texto, que es donde es probable que obtenga la mayoría de sus problemas de rendimiento en un editor de texto simple.
El uso de selecciones (que no implementamos esto ya que era un editor de texto que utiliza el modo de vi-como comandos como 3d eliminar 3 líneas o eliminar 6x 6 caracteres) podría ser implementado por tener una tupla {line#/block, char-pos} para marcar posiciones en el texto, y usar dos de esas tuplas para un rango de selección.
Wikipedia dice que muchos editores usan un Gap Buffer. Básicamente es una matriz con un espacio no utilizado en el medio. El cursor se encuentra justo antes del espacio, por lo que la eliminación e inserción en el cursor es O (1). Debería ser bastante fácil de implementar.
Al observar el código fuente de Notepad ++ (como Chris Ballance sugirió en este hilo here) muestra que también utilizan un búfer de brecha. Puede obtener algunas ideas de implementación a partir de eso.
Hay un excelente artículo sobre Piece Chains por James Brown, autor de HexEdit.
En pocas palabras: las cadenas de piezas le permiten registrar los cambios realizados en el texto. Después de cargar, tienes una cadena de piezas que abarca todo el texto. Ahora inserta en algún lugar en el medio.
En lugar de asignar un nuevo búfer, copiar el texto, etc., crea dos piezas nuevas y modifica la existente: la existente ahora contiene el texto hasta el punto de inserción (es decir,simplemente cambie la longitud de la pieza), luego tiene una pieza con el nuevo texto y luego una nueva pieza con todo el texto después de la inserción. El texto original no se modifica.
Para deshacer/rehacer, simplemente recuerde qué piezas ha agregado/eliminado/cambiado.
El área más compleja cuando se usan cadenas de piezas es que ya no existe una correspondencia 1: 1 entre un desplazamiento en el texto visible y la estructura de la memoria. Tienes que buscar en la cadena o debes mantener una estructura de árbol binario de algún tipo.
Emacs también usa esto según wikipedia –