Un búfer de brecha en informática es una matriz dinámica que permite operaciones de inserción y eliminación eficientes agrupadas cerca de la misma ubicación. Los búferes de espacios son especialmente comunes en los editores de texto , donde la mayoría de los cambios en el texto ocurren en o cerca de la ubicación actual del cursor . El texto se almacena en un búfer grande en dos segmentos contiguos, con un espacio entre ellos para insertar texto nuevo. Mover el cursor implica copiar texto de un lado del espacio al otro (a veces la copia se retrasa hasta la siguiente operación que cambia el texto). La inserción agrega texto nuevo al final del primer segmento; la eliminación lo elimina.
El texto en un búfer de espacio se representa como dos cadenas , que ocupan muy poco espacio adicional y que se pueden buscar y mostrar muy rápidamente, en comparación con estructuras de datos más sofisticadas , como listas enlazadas . Sin embargo, las operaciones en diferentes ubicaciones del texto y las que llenan el espacio (que requieren la creación de un nuevo espacio) pueden requerir copiar la mayor parte del texto, lo que es especialmente ineficaz para archivos grandes. El uso de búfer de brechas se basa en la suposición de que tal copia de seguridad ocurre raramente lo suficiente como para que su costo se pueda amortizar sobre las operaciones baratas más comunes. Esto hace que el búfer de espacios sea una alternativa más simple a la cuerda para usar en editores de texto [1] como Emacs . [2]
Ejemplo
A continuación se muestran algunos ejemplos de operaciones con espacios de búfer. El espacio está representado por el espacio vacío entre los corchetes. Esta representación es un poco engañosa: en una implementación típica, los puntos finales de la brecha se rastrean utilizando punteros o índices de matriz, y el contenido de la brecha se ignora; esto permite, por ejemplo, realizar eliminaciones ajustando un puntero sin cambiar el texto en el búfer. Es una práctica de programación común usar un intervalo semiabierto para los punteros de espacio, es decir, el inicio del espacio apunta al carácter no válido que sigue al último carácter en el primer búfer, y el final del espacio apunta al primero. carácter válido en el segundo búfer (o de manera equivalente, se considera que los punteros apuntan "entre" caracteres).
Estado inicial:
Esta es la salida [].
El usuario inserta un texto nuevo:
Así es como empezó el mundo [].
El usuario mueve el cursor antes de "iniciado"; el sistema se mueve "iniciado" desde el primer búfer al segundo búfer.
Así es como empezó el mundo [].
El usuario agrega texto para llenar el vacío; El sistema crea una nueva brecha:
Así es como empezó el mundo tal como lo conocemos [].
Ver también
- Matriz dinámica , el caso especial de un búfer de espacio donde el espacio siempre está al final
- Cremallera (estructura de datos) , conceptualmente una generalización del búfer de brecha.
- Lista enlazada
- Búfer circular
- Cuerda (informática)
- Tabla de piezas : estructura de datos utilizada por Bravo y Microsoft Word
Referencias
- ^ Mark C. Chu-Carroll. "¿ Buffers, o no se atan con cuerdas? " ScienceBlogs , 2009-02-18. Consultado el 30 de enero de 2013.
- ^ Información del búfer de brecha de emacs Consultado el 30 de enero de 2013.
enlaces externos
- Descripción general e implementación en .NET / C #
- Breve descripción general y código C ++ de muestra
- Implementación de un búfer de brecha ordenada cíclicamente en .NET / C #
- Uso de búfer de brecha en el editor temprano. (Escrito por primera vez entre 1969 y 1971)
- información de búfer de brecha de emacs (referencia de búfer de brecha de Emacs)
- Flexichain: una secuencia editable y su implementación de búfer de brechas