Управление линией в текстовом редакторе

Question

Я работаю над текстовым редактором в течение некоторого времени.Я сделал собственный элемент управления редактирования с нуля, и теперь у меня есть основы.Проблема, с которой я сталкиваюсь, касается линейного управления.Поскольку моя программа полагается на разделение входного текста на строки (текст печатается построчно), управление строками довольно важно.Я использовал std :: vector для хранения позиций строк.Я использую таблицу фигур для обработки текста, но для простоты, скажем, у меня есть массив символов.Я добавляю / вставляю элемент в вектор строки каждый раз, когда пользователь нажимает ввод.Проблема в том, что каждый раз, когда пользователь вставляет символ, вся структура нарушается.Например:

         0   1   2   3   4   5    6   7   8   9   10
text = ['h','e','l','l','o','\n','W','o','r','l','d']
state of line vector : 
line[0] = 0 
line[1] = 6

Допустим, пользователь вставляет символ ('x') после текста [2]:

         0   1   2   3   4   5    6   7   8   9   10  11
text = ['h','e','l','x','l','o','\n','W','o','r','l','d'] 
state of line vector : 
line[0] = 0 
line[1] = 6

Из-за вставки мне нужно обновитьзначение каждого элемента в векторе линий после текущей строки.То же самое для удаления.Если в программе 1000 строк и пользователь редактирует первую строку, было бы совершенно неэффективно обновить все 999 элементов (кроме первой).

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

Редактировать: Просто для пояснения, я использую структуру данных, называемую Piece Table.Я не использую массив символов.Вот что такое структура данных таблицы элементов: http://www.cs.unm.edu/~crowley/papers/sds.pdf

Answer 1

Классическая структура данных, используемая многими редакторами, - это " Gap Buffer ". В основном это рабочее пространство вокруг курсора, в котором происходит активность, поэтому локальные операции выполняются быстро. Затем, когда курсор перемещается, промежуток, при условии изменения, будет перемещаться вместе с ним.

Что касается линейных вычислений, современные системы достаточно быстры, где вы можете просто сканировать буфер и искать строки. Приятно то, что вам не нужно делать это в большинстве операций, поэтому вы воздерживаетесь от этого все время. Кроме того, существует разница между физическими строками в буфере (то есть коллекциями символов, заканчивающимися маркером EOL) и мягкими строками (перенос слов и т. Д.). Рассмотрим современный текстовый процессор, где абзацы обычно представляют собой одну «строку», но переносятся по полям страницы. Конечно, вы можете справиться с этим в любом случае.

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

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

Answer 2

Вектор будет работать нормально.

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

Вы также можете рассмотреть некоторые виды методов Gap Buffer.

Answer 3

Если я понимаю вопрос, вы отслеживаете позиции линий со вспомогательной структурой данных вдоль этих строк:

line  offset  length
   0       0      65
   1      65      30
   2      95      50
   3     145       1
   4     146      13
 ...

Если длина строки n изменяется на d, то вам необходимо обновить смещение всех оставшихся строк на d. И это медленно, когда много строк.

Вы можете отслеживать достопримечательности. Вместо смещений, относящихся к началу последовательности, они должны быть относительно некоторого ориентира.

Предполагается, что вы создаете ориентир для каждых 100 линий. Первые сто строк отслеживаются точно так же, так как первый ориентир находится в начале файла. Но следующие сто строк просто имеют смещения, а ориентир имеет абсолютное смещение от начала файла для строки 100.

Поэтому, когда вы изменяете длину линии, вам нужно обновить только смещения для остальных линий в этом ориентире, а также смещения оставшихся ориентиров. Это все еще O (n), но есть довольно большой делитель, который сделает его быстрее.

Но мы можем сделать лучше. Вместо того, чтобы просто поддерживать список ориентиров, предположим, что мы поместили их в дерево, где листья дерева - это ваша линия, а корень - весь файл. Чтобы найти смещение данной линии, вы складываете смещения всех ее предков вместе. И если линия изменяется, вы просто обновляете один узел и его предков. Это дает O (log n) за счет некоторой бухгалтерии. Служебная память не намного хуже, чем у двусвязного списка, который вы уже используете.