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

Question

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

Answer 1

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

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

Макет буфера:

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!
                      ^             ^

Answer 2

Rope

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

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

Answer 3

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

Answer 4

Это может показаться вам интересным, даже если оно не совсем отвечает на ваш вопрос:

Наиболее эффективная структура данных для добавления стилей к тексту

Я надеюсь, что обсуждение пойдет в увлекательные места: -)

Answer 5

Поскольку @Vovanium уже упомянул основную теорию о том, как можно использовать буфер с гэпом, я реализовал версию C / C ++.

Код:

#include <stdio.h>
#define SZ 1000

char leftArray[SZ], rightArray[SZ];
int leftCount, rightCount;
int cursorPos;

/*
 * Private APIs
 */

void printArray(){

    for(register int i = 0; i < leftCount; i++){
        printf("%c", leftArray[i]);
    }

    for(register int i = rightCount - 1; i >= 0; i--){
        printf("%c", rightArray[i]);
    }
    printf("\n");
}

void adjust(int pos){

    while(leftCount > pos){
        rightArray[rightCount++] = leftArray[--leftCount];
    }

    while(leftCount < pos){
        leftArray[leftCount++] = rightArray[--rightCount];
    }
}


/*
 * Public APIs for Text Editor
 */

void init(){

    cursorPos = leftCount = rightCount = 0;
}

void addWord(char word[], int len){

    adjust(cursorPos);

    for(register int i = 0; i < len; i++){
        leftArray[leftCount++] = word[i];
    }
    leftArray[leftCount] = 0;
}

void addBackSpace(){

    adjust(cursorPos);
    leftCount--;
}

void moveCurson(int newPosition){

    cursorPos = newPosition;
}

void subString(int pos, int length, char result[]){

        adjust(cursorPos);

    int k = 0;
        int l = 0;
    while(k + pos < leftCount && k < length){
        result[k] = leftArray[pos + k];
        k++;
    }

    length -= k;
    while( l < length){
        result[k++] = rightArray[rightCount - 1 - l];
        l++;
    }
}