Буферное окно

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Буферное окно (англ. Gap buffer) в информатике это динамический массив, который позволяет эффективно производить вставку и удаление элемента в некоторой области. Буферное окно особенно распространено в текстовых редакторах, где большинство изменений текста происходят около позиции курсора. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Перемещение курсора вызывает копирование текста с одной стороны окна к в другую (иногда копирование задерживается до операции изменения текста). Вставка добавляет новый текст в конец первого сегмента. Удаление увеличивает размер окна.

Текст в буферном окне делится на две символьные строки, которые используют очень мало дополнительной памяти и которые могут быть легко отображены или использованы в поиске, в сравнение с другими структурами данных, к примеру связанных списков. Однако, операции в разных местах файла и те, которые заполняют окно (требуют создание нового окна) могут потребовать копирования большого объёма текста, что особенно неэффективно для больших файлов.

Использование буферного окна основано на предположение, что перекопирование происходит достаточно редко и его стоимость может быть амортизирована более дешевыми операциями. Это делает буферное окно более простой альтернативой Rope (англ.) для использования в текстовых редакторах [1] таких как Emacs.[2]

Пример[править | править вики-текст]

Ниже приведено несколько примеров операции над буферным окном. Окно представлено пустым пространством между квадратными скобками. Это представление немного обманчиво: обычно в реализации концы представлены указателями или индексами массива и содержимое окна игнорируется, что позволяет, к примеру, производить удаление лишь установкой указателя без изменения текста в буфере. Это общая практика использования полуоткрытого интервала для указателей окна, то есть указатель начала_окна установлен после последнего символа в первом сегменте и указатель на конец_окна на первый символ во втором сегменте (или, что эквивалентно, указатели установлены на точки "между" символами)

Начальное состояние:

This is the way [                    ]out.

Пользователь добавляет некоторый текст:

This is the way the world started [   ]out.

Пользователь перемещает курсор перед started", система перемещает "started " из первого сегмента во второй.

This is the way the world [   ]started out.

Пользователь добавляет текст, заполняющий окно. Система увеличивает окно.

This is the way the world as we know it [                   ]started out.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Mark C. Chu-Carroll. "Gap Buffers, or, Don’t Get Tied Up With Ropes?" ScienceBlogs, 2009-02-18. Accessed 2013-01-30.
  2. emacs gap buffer info Accessed 2013-01-30.

Ссылки[править | править вики-текст]