Что лучшая структура данных подходит для реализации редактора как блокнот?

Веревки выезда. Дескрипторы быстро вставляют/удаляют/редактируют строк. Диапазоны обычно поддерживаются в реализациях Веревки, и прокрутка может быть сделана с инвертированным индексом в веревку.

Википедия говорит, что многие редакторы используют Буфер Разрыва. Это - в основном массив с неиспользуемым местом в середине. Курсор находится незадолго до разрыва, таким образом, удаление и вставка в курсоре O (1). Должно быть довольно легко реализовать.

Рассмотрение исходного кода Блокнота ++ (как Chris Ballance, предложенный в этом потоке здесь), показывает, что они также используют буфер разрыва. Вы могли получить некоторые идеи реализации от этого.

Мы записали, редактор для старой машины (имейте в виду, что это было только что, приблизительно в 1986, таким образом, это из памяти, и состояние, возможно, совершенствовалось несколько с тех пор), который нам удалось получить для крика вперед, мудрая производительность, при помощи блоков постоянной памяти от самоуправляемых пулов.

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

Память была предварительно выделена (для каждого региона) от'malloc()подобный ' вызов, и мы использовали 65 535 блоков (0 через 65 534 содержащих, номера блока 65,535, считался пустым блоком, индикатором конца списка).

Это позволило каждому для 65, 535 строк (384K или 512K для заполненной версии) и о 1.6G размера файла (берущий 2G выделенного места), который был довольно большим тогда. Это было теоретическим пределом размера файла - я не думаю, что мы когда-либо приближались к этому в действительности, так как мы никогда не выделяли полный набор структур линейного сегмента.

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

Структуры в двух пулах были следующим образом, при этом каждая строка была единственным байтом):

Line structure (6/8 bytes)     Line-segment structure (32 bytes)
+--------+                     +--------+
|NNNNNNNN|                     |nnnnnnnn|
|NNNNNNNN|                     |nnnnnnnn|
|PPPPPPPP|                     |pppppppp|
|PPPPPPPP|                     |pppppppp|
|bbbbbbbb|                     |LLLLLLLL|
|bbbbbbbb|                     |LLLLLLLL|
|........|                     |xxxxxxxx|
|........|                     :25 more :
+--------+                     : x lines:
                               +--------+

где:

• Строчные буквы кроме x укажите на пул линейного сегмента.
• Прописные буквы указывают на пул строки.
• N был номер блока для следующей строки (пустой указатель, означающий, что это было последней строкой в файле).
• P номер блока для предыдущей строки (пустой указатель, означающий это, был первой строкой в файле).
• b был номер блока для первого линейного сегмента в той строке (пустой указатель, означающий, что строка была пуста).
• . был зарезервирован, дополнив (для столкновения структуры к 8 байтам).
• n был номер блока для сегмента следующей строки (пустой указатель, означающий, что это было последним сегментом в строке).
• p был номер блока для предыдущего линейного сегмента (пустой указатель, означающий, что это было первым сегментом в строке).
• L был номер блока для блока строки сегмента.
• x были эти 26 символов в том линейном сегменте.

Причина структура строки была дополнена, состояла в том, чтобы убыстриться, преобразование номеров блока в фактические ячейки памяти (смещающийся оставленный на 3 бита было намного быстрее, чем умножение на 6 в той конкретной архитектуре и используемой дополнительной памяти было только 128K, минимально по сравнению с общим используемым устройством хранения данных), хотя мы действительно предоставляли более медленную версию тем, кто заботился больше о памяти.

У нас также был массив 100 16-разрядных значений, которые содержали линейный сегмент (и номер строки, таким образом, мы могли быстро перейти к определенным строкам) в примерно, что процент (так, чтобы массив [7] был строкой, которая составляла примерно 7% в файл), и два свободных указателя для ведения бесплатного списка в каждом пуле (это было очень простым одним путем список где N или n в структуре указал на следующий свободный блок, и свободные блоки были выделены от и возвращались к, передняя сторона этих списков).

Не было никакой потребности провести подсчет символов в каждом линейном сегменте, так как 0 байтов не были допустимы в файлах. Каждому линейному сегменту позволили иметь 0 байтов в конце, которые были полностью проигнорированы. Строки были сжаты (т.е. линейные сегменты были объединены) каждый раз, когда они были изменены. Это поддержанное на низком уровне использование блока (без нечастой и долгой сборки "мусора") и также значительно ускорило операции поиска-и-замены.

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

Использование выборов (мы не реализовали это, поскольку это был редактор текстового режима, который использовал подобные vi команды такой как 3d удалить 3 строки или 6x удалить 6 символов), мог быть реализован при наличии a {line#/block, char-pos} кортеж, чтобы отметить положения в тексте и использовать два из тех кортежей для диапазона выбора.

Проверьте реализацию Блокнота ++, можно просмотреть источник на SourceForge

Обычная вещь состоит в том, чтобы иметь что-то как список или массив массивов символов. Было много материала, сделанного на этом за эти годы: Вы могли бы взглянуть на этот поиск Google.

Есть отличная статья о Цепях фигур , написанная Джеймсом Брауном, автором HexEdit .

В двух словах: Цепи фигур позволяют вам запишите изменения, внесенные в текст. После загрузки у вас есть цепочка элементов, охватывающая весь текст. Теперь вы вставляете где-то посередине.

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

Для отмены / повтора вы просто запоминаете, какие элементы вы добавили / удалили / изменили.

Наиболее сложной областью при использовании цепочек элементов является то, что больше не существует отображения 1: 1 между смещением в видимом тексте и структурой памяти. Вы должны либо искать в цепочке, либо поддерживать какую-то двоичную древовидную структуру.