Подтвердить что ты не робот

Структура данных для текстового редактора

Это вопрос интервью. Какую структуру данных вы бы использовали для хранения текста в текстовом редакторе?

4b9b3361

ОТВЕТЫ

Ответ 1

На хорошем старом ZX-Spectrum один (или более, я не знаю) текст exditor использовал очень простую структуру.

Был один большой буфер, который занимал всю свободную ОЗУ. Текст был разделен на две части курсором. Часть перед курсором была помещена в начале буфера, а остальная часть - в конец буфера. При вводе текста данные просто добавляются в конец первой части, а когда курсор перемещается, текст копируется вперед и назад.

Буферная компоновка:

Hello, World!
        ^------Cursor here

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|H|e|l|l|o|,| |W| <free>  |o|r|l|d|!|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                ^         ^        |
begin           cur1      cur2    end

Итак, как некоторые операции редактирования были сделаны:

Type a char:    buffer[cur1++] = character

Backspace:      cur1--

Cursor left:    buffer[--cur2] = buffer[--cur1]

Cursor right:   buffer[cur1++] = buffer[cur2++]

Буфер в действии:

             Hello, W..............orld!
Press right          ^             ^
             Hello, Wo..............rld!
Press backspace       ^             ^
             Hello, W...............rld!
Press 0              ^              ^
             Hello, W0..............rld!
                      ^             ^

Ответ 2

Rope

Канат по существу представляет собой двоичное дерево, листья которого представляют собой массивы символов. A node в дереве имеет левый дочерний элемент и правый дочерний элемент - левый ребенок является первой частью строки, а правый - конечной частью строки. Конкатенация двух веревок просто включает в себя создание нового дерева node с двумя канатами в качестве детей. Для обеспечения логарифмической индексации времени и операций подстроки результирующая веревка может потребоваться сбалансировать. Возможны различные стратегии балансировки.

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

Ответ 3

Я знаю, что слишком поздно для ответа, но я нашел The Craft of Text Editing действительно полезной. Он содержит описание нескольких моделей буферов со своими плюсами и минусами. К сожалению, он не упоминает структуру данных Ropes.