Буферное окно
Буферное окно (Шаблон:Lang-en) в информатике это динамический массив, который позволяет эффективно производить вставку и удаление элемента в некоторой области. Буферное окно особенно распространено в текстовых редакторах, где большинство изменений текста происходят около позиции курсора. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Перемещение курсора вызывает копирование текста с одной стороны окна в другую (иногда копирование задерживается до операции изменения текста). Вставка добавляет новый текст в конец первого сегмента. Удаление увеличивает размер окна.
Текст в буферном окне делится на две символьные строки, которые используют очень мало дополнительной памяти и которые могут быть легко отображены или использованы в поиске, в сравнение с другими структурами данных, к примеру связанных списков. Однако, операции в разных местах файла и те, которые заполняют окно (требуют создания нового окна) могут потребовать копирования большого объёма текста, что особенно неэффективно для больших файлов.
Использование буферного окна основано на предположении, что перекопирование происходит достаточно редко и его стоимость может быть амортизирована более дешевыми операциями. Это делает буферное окно более простой альтернативой Шаблон:Нп1 для использования в текстовых редакторах<ref name="chucarroll">Mark C. Chu-Carroll. «Gap Buffers, or, Don’t Get Tied Up With Ropes? Шаблон:Wayback» ScienceBlogs, 2009-02-18. Accessed 2013-01-30.</ref> таких как Emacs.<ref>Шаблон:Cite web</ref>
Пример
Ниже приведено несколько примеров операции над буферным окном. Окно представлено пустым пространством между квадратными скобками. Это представление немного обманчиво: обычно в реализации концы представлены указателями или индексами массива и содержимое окна игнорируется, что позволяет, к примеру, производить удаление лишь установкой указателя без изменения текста в буфере. Это общая практика использования полуоткрытого интервала для указателей окна, то есть указатель начала_окна установлен после последнего символа в первом сегменте и указатель на конец_окна на первый символ во втором сегменте (или, что эквивалентно, указатели установлены на точки «между» символами)
Начальное состояние:
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 — концептуально обобщение буферного окна
- Связный список
- Кольцевой буфер
- Шаблон:Нп1
Примечания
| {{#switch: {{{1}}}
| узкие = columns reflist-narrow
| широкие = columns reflist-wide
| #default = columns
}}
| {{#switch: {{{1}}}
| 1 =
| 2 | 3 = columns
| #default = columns reflist-narrow
}}
}}
| columns
}}
}}" style="{{#if:
| column-width:{{{colwidth}}};
| {{#if:
| {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие =
| #default = column-width:{{{1}}};
}}
}}
}}
}} list-style-type: {{#switch:
| upper-alpha
| upper-roman
| lower-alpha
| lower-greek
| lower-roman = {{{group}}}
| #default = decimal
}};">
<references group="" responsive="{{#if:
| 0
| {{#if:
| {{#iferror: {{#expr: {{{1}}} > 1 }}
| {{#switch: {{{1}}}
| узкие | широкие = 1
| #default = 0
}}
| {{#switch: {{{1}}}
| 1 = 0
| #default = 1
}}
}}
| 1
}}
}}"></references>Ошибка скрипта: Модуля «Check for unknown parameters» не существует.
Ссылки
- Overview and implementation in .NET/C#
- Brief overview and sample C++ code
- Implementation of a cyclic sorted gap buffer in .NET/C#
- Use of gap buffer in early editor. (First written somewhere between 1969 and 1971)
- emacs gap buffer info(Emacs gap buffer reference)
- Text Editing
