Буфер разрыва

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

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

Пример

Ниже приведены некоторые примеры операций с пробелами в буфере. Пробел представляет собой пустое пространство между квадратными скобками. Такое представление немного вводит в заблуждение: в типичной реализации конечные точки пробела отслеживаются с помощью указателей или индексов массива, а содержимое пробела игнорируется; это позволяет, например, выполнять удаление путем изменения указателя без изменения текста в буфере.

Исходное состояние:

This is the way [                     ]out.

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

This is the way the world started [   ]out.

Пользователь перемещает курсор перед словом «начало»; система перемещает «старт» из первого буфера во второй буфер.

This is the way the world [   ]started out.

Пользователь добавляет текст, заполняя пробел; система создает новый разрыв:

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

См. также

Динамический массив , частный случай буфера пробелов, где пробел всегда находится в конце.
Zipper (структура данных) , концептуально обобщение буфера пробелов.
Связанный список
Круговой буфер
Веревка (информатика)
Таблица частей — структура данных, используемая Bravo и Microsoft Word.

Ссылки

^ Марк К. Чу-Кэрролл. « Буферы с пробелами, или не связывайтесь веревками? » ScienceBlogs , 18 февраля 2009 г. По состоянию на 30 января 2013 г.
^ Информация о буфере разрыва emacs . По состоянию на 30 января 2013 г.

Внешние ссылки

Реализация на C
Обзор и реализация в .NET/C#
Краткий обзор и пример кода C++
Реализация циклического буфера отсортированных пробелов в .NET/C#
Использование буфера пробелов в раннем редакторе. (Впервые написано где-то между 1969 и 1971 годами)
Информация о буфере пробелов emacs (ссылка на буфер пробелов Emacs)
Flexichain: редактируемая последовательность и ее реализация с буфером промежутков.
Текстовое вскрытие: буферы разрывов против веревок

[chucarroll-1] Марк К. Чу-Кэрролл. « Буферы с пробелами, или не связывайтесь веревками? » ScienceBlogs , 18 февраля 2009 г. По состоянию на 30 января 2013 г.

[elisp-2] Информация о буфере разрыва emacs . По состоянию на 30 января 2013 г.

[1]

[2]