A Таблица элементов - это структура данных, обычно используемая для представления последовательности элементов текстовый документ. Создается начальная ссылка (или "диапазон") на весь исходный файл, а последующие вставки и удаления создаются как комбинации одной, двух или трех ссылок на разделы исходного документа или диапазонов, связанных с более ранними. вставки.
Обычно текст исходного документа содержится в одном неизменяемом блоке, а текст каждой последующей вставки сохраняется в новых неизменяемых блоках. Поскольку даже удаленный текст по-прежнему включается в таблицу элементов, это упрощает реализацию многоуровневой или неограниченной отмены с таблицей элементов, чем с альтернативными структурами данных, такими как буфер промежутка.
Это структура данных была изобретена Дж. Стротером Муром.
Для этого описания мы используем buffer как неизменяемый блок для хранения содержимого.
Таблица частей состоит из трех столбцов:
Помимо таблицы, два буферы используются для обработки редактирования:
Определение: Индекс (i)
: вернуть символ в позиции i
Получить i-й символ, считывается соответствующая запись в таблице штук.
Для следующих буферов и таблицы частей:
Buffer | Content |
---|---|
Исходный файл | ipsum sit amet |
Добавить файл | Lorem deletedtext dolor |
Какой | Начальный индекс | Длина |
---|---|---|
Добавить | 0 | 6 |
Исходный | 0 | 6 |
Добавить | 18 | 5 |
Исходный | 6 | 9 |
Для доступа к i-му символу ищется соответствующая запись в таблице штук.
Например, чтобы получить значение Index (15)
, извлекается 3-я запись таблицы частей. Это связано с тем, что третья запись описывает символы от 12 до 17 (первая запись описывает символы от 0 до 5, следующая - от 6 до 11). Запись в таблице элементов инструктирует программу искать символы в буфере «добавить файл», начиная с индекса 18 в этом буфере. Относительный индекс в этой записи равен 3 (15 - 12), что делает значение Index (15)
символом «o».
Для буферов и таблицы частей, приведенных выше, показан следующий текст:
Lorem ipsum dolor sit amet
Буфер подразумевает такую последовательность действий:
начало: ipsum sit amet (таблица единиц теперь Исходная [0,9]) вставка: Lorem ipsum sit amet (таблица единиц теперь Добавлена [0,6], Исходная [0,9]) вставка «удаленного текста» где-то «удаленный текст» удаляется (но остается в буфере добавления) вставка: Lorem ipsum dolor sit amet (таблица элементов заканчивается на конечном состоянии)
Вставка символов в текст состоит из:
Удаление включает только изменение соответствующей записи в таблице элементов.
Хотя таблица элементов сама по себе является структурой данных, в ней не указывается, как ее следует реализовать. Временная сложность операций зависит от того, как таблица реализуется. Одна из возможных реализаций таблицы элементов - это развернутое дерево, поскольку оно обеспечивает быстрый доступ к элементам, к которым недавно осуществлялся доступ.
Некоторые используют часть в ОЗУ внутреннюю таблицу, включая Bravo, Abiword и Visual Studio Code.
Функция "быстрого сохранения" в некоторых версиях Microsoft Word использует таблицу элементов для включения формат файла на диске.
Для представления текстовых файлов на диске в Oberon System используется метод цепочки элементов, который позволяет частям одного документа указывать на сохраненный текст в другом документе, похожем на включение.
.