data-structures - uso - tipos de editores de texto
Teoría del editor de texto (11)
Como siempre estoy insatisfecho con los editores existentes, un proyecto que siempre quise comenzar es mi propio editor de texto. Sin embargo, la edición de texto es un asunto serio.
Además de analizar el código fuente de los editores de texto existentes, ¿hay algún libro u otro recurso (como trabajo académico) sobre este tema? Me interesa especialmente algo que enseñe cómo manejar la memoria y cómo administrar la inserción de texto (si tienes un archivo de 100 MB y quieres agregar un carácter en la posición x , no puedes simplemente memmove el gran bloque de texto ...) )
cómo administrar la inserción de texto (si tiene un archivo de 100 MB y desea agregar un carácter en la posición x, no puede memorizar el enorme bloque de texto ...).
Haga que el archivo de texto sea una lista vinculada, donde cada línea es una entrada.
A lo largo de los años escribí bastantes editores de texto diferentes. Ciertamente, la forma más simple es administrar una larga secuencia de caracteres, donde se copia todo para insertar cualquier carácter. Otras técnicas que he usado incluyen:
- Represente el archivo de texto como una lista de líneas de texto doblemente vinculadas.
- Construya una estructura de datos similar a un árbol (a veces llamada "rope" ) que comienza como una cadena sólida de caracteres, pero tiene la capacidad de dividir, insertar y eliminar bloques de texto sin tener que mover todo el resto del texto .
Muchos de los viejos libros de ejemplo de Borland usaron un editor de texto como ejemplo de tutorial. Ocasionalmente puede encontrar copias de estos en librerías usadas casi gratis.
Así es como lo hacen los "profesionales" en Microsoft:
MS Word usa la estructura de datos de la tabla pieza. Una matriz ascendente de posiciones de caracteres se mantiene en paralelo con una matriz de estructuras más grandes que contienen punteros en el archivo original (texto cargado en la carga de archivos) o en un búfer de solo agregación de caracteres recién agregados.
El control EDIT utilizado en todas partes en Windows no utiliza ninguna estructura de datos. Notepad simplemente usa un control EDIT de varias líneas. Compruébalo con un visor de montón. El control EDIT mantiene solo un buffer de saltos de línea y tab-stops.
Si vas a crear un editor de texto sencillo sin formato en Windows, podrías fácilmente subclasificar el control EDITAR para agregar características.
Bien, si usted sabe que, en general, la gente tendrá relativamente pocos puntos de inserción, podría mantener una serie de punteros en su búfer de texto original y cuando el usuario intente insertar dentro de él, "divide" el búfer al generar otro puntero al resto del búfer, haciendo la primera longitud del puntero para que se detenga en el punto de inserción y agregue un 3er puntero para que el texto se inserte entremedio, como:
long original text la la la
^ *^
| 2nd part
1st part
Y la estrella señala un nuevo búfer de texto donde comienza a agregar el texto que se insertará.
Cuando renderiza (o analiza en general) su archivo de texto, recorre el conjunto de punteros y luego hace su trabajo en cada buffer. Por supuesto, si el búfer es lo suficientemente pequeño, omita agregar una nueva parte del búfer, pero eso es solo heurística, pruebe cada uno y obtenga una idea de cuál funciona mejor.
También podría considerar dividir el archivo de texto en carga en varios almacenamientos intermedios, por ejemplo, cada 1 MB, porque si carga el archivo en un solo búfer necesitará crear un nuevo búfer para el texto insertado debido al tamaño. De nuevo, esta es una optimización heurística.
Echa un vistazo a la descripción de Rob Pike de su editor de texto Sam . Asegúrese de navegar más allá de la vista general de alto nivel y el lenguaje de comandos. Describe el análisis sintáctico, la administración de la memoria y las estructuras de datos más adelante en el documento.
Además, eche un vistazo a la implementación simple de expresiones regulares de Russ Cox. Es fácil de seguir y puede abrir algunas puertas fuera de las bibliotecas de expresiones regulares existentes.
El componente Scintilla utiliza un búfer dividido, a lo largo de la teoría explicada en un texto vinculado en su página de Sitios relacionados de Scintilla y SciTE .
La página vinculada es estructuras de datos en un editor de texto asignado a bits .
El búfer dividido demostró que funciona bien incluso con archivos de megabytes. Usar estructuras secundarias (por ejemplo, una lista de inicios de línea) también puede ser útil.
Hay un excelente tutorial disponible aquí que cubre una gran cantidad de temas relevantes en un contexto más moderno:
Las otras respuestas a esta pregunta cubren el búfer de brecha.
Otra cobertura moderna son las descripciones de AvalonEdit
y detalles adicionales de:
- http://wiki.sharpdevelop.net/AvalonEdit.ashx
- http://danielgrunwald.de/coding/AvalonEdit/document.php
- http://danielgrunwald.de/coding/AvalonEdit/rendering.php
y hay una gran cantidad de detalles / contenido (sobre SharpDevelop) en el libro:
Promocionado para responder por solicitud:
Las antiguas " Herramientas de software en Pascal " de Kernighan y Plaugher implementan el editor ed en un lenguaje sin cadenas reales ni punteros. Contiene una gran visión general de las consideraciones de diseño que subyacen a cualquier editor de texto.
Un viejo método que todavía funciona se llama buffer de brecha. La idea básica es que coloque el texto en un búfer, pero en lugar de ponerlo todo en un bloque, crea un "espacio" en el cursor, coloca todo el texto antes del cursor al principio del búfer, y todo texto después del cursor al final del búfer. La mayoría de las inserciones tienen lugar en el cursor, lo que puede hacer sin mover nada (hasta que salga del buffer o a menos que lo haga). Cuando el usuario mueve el cursor, mueve el texto apropiado de un lado a otro de la división.
Dados los controles típicos (cursor izquierda, derecha, arriba, abajo, página arriba, página abajo), el movimiento más grande con el que normalmente se enfrenta es una página a la vez, que suele ser fácil de manejar bastante más rápido de lo que repite un teclado. Por supuesto, puede ralentizar un poco si tiene un archivo realmente grande y un comando "ir a la línea", o algo en ese orden. Si vas a hacer mucho de eso, indudablemente hay mejores estructuras para usar ...
Este documento compara muchas estructuras de datos que pueden usarse para editores de texto, incluidas algunas ya mencionadas aquí (por ejemplo, memorias intermedias), así como varias otras (por ejemplo, tablas de piezas). El artículo es antiguo, pero creo que sigue cubriendo todas las opciones principales, y lo compara muy bien en términos de rendimiento, complejidad y gastos generales.
Sé que las respuestas de no son simplemente enlaces, pero esta sigue siendo la mejor fuente de información que he encontrado para la información solicitada, y es demasiado larga para resumir aquí en una respuesta. En caso de que el enlace quede obsoleto, busque " Estructuras de datos para secuencias de texto " por Charles Crowley de la Universidad de Nuevo México.
The Craft of Text Editing, de Craig Finseth, basado en su tesis de maestría, cubre estos temas. Es gratis en la web. OTOH es bastante viejo y no menciona algunas ideas como cuerdas que eran menos prácticas en las pequeñas computadoras de antaño.