Алгоритм рендеринга длинного текста в текстовом редакторе

Question

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

1. Мне кажется невозможным реализовать какую-либо разумную функцию прокрутки для такого редактора, если только я предварительно не прочитал весь файл один раз, вДля того, чтобы выяснить разрывы строк.Это правда?Или есть способ приблизить вещи, о которых я не думаю?

2. Из-за различных проблем с Unicode (например, он позволяет многим байтам представлять только один символ, а не только потому, чтоиз-за кодирования переменной длины, но также из-за акцентов и т. д.), почти невозможно определить точно, сколько текста поместится на экране - я должен был бы использовать TextOut () или что-то, чтобы нарисовать один символ, измерить, насколько большойэто было, а затем нарисуйте следующий символ.И даже тогда это еще не говорит о том, как я сопоставил бы клики пользователя с правильной текстовой позицией.

Могу ли я что-нибудь прочитать в Интернете относительно алгоритмов обработкиэти проблемы?Я искал, но ничего не нашел.

Спасибо!

Answer 1

Вы можете установить «грубую» позицию на основе размера данных вместо линий. «Хорошая» позиция вашего текстового окна может быть основана на локальном сканировании вокруг произвольной точки входа.

Это означает, что вам нужно будет написать функции, которые могут сканировать локально (назад и вперед), чтобы найти начало строки, считать символы Unicode и т. Д. Это не должно быть слишком сложно; UTF8 разработан таким образом, чтобы его было легко анализировать.

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

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

Answer 2

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

Для простого текста это можно сделать на архаичном процессоре достаточно быстро, чтобы перерисовывать отображаемое в памяти видео при каждом нажатии клавиши. [Я изобрел эту технологию 30 лет назад]. Правильный способ сделать это - установить курсор в средней строке экрана.

Для фактического изменения файлов вы можете посмотреть, используя веревки Gnu. Веревка - это в основном связанный список буферов. Идея состоит в том, что все локальные изменения могут быть сделаны в одном небольшом буфере, иногда добавляя новый буфер, и иногда объединяя смежные буферы.

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

Ключом к этому являются обратимые транзакции, т. Е. Та, которая содержит достаточно информации, чтобы применить ее в обратном направлении, чтобы отменить то, что она сделала при применении вперед. Основная транзакция редактора:

at pos p replace old with new

с обратным

at pos p replace new with old

Это обрабатывает вставку (старая пустая) и удаление (новая пустая), а также замена. Имея список транзакций, вы можете отменить внесенные изменения в строку, применив обратную сторону списка обратных транзакций.

Теперь вы используете старую концепцию контрольных точек: вы сохраняете довольно недавнее модифицированное изображение файла на месте вместе с некоторыми недавними транзакциями, которые еще не были применены. Для отображения вы применяете транзакции на лету. Чтобы отменить, вы просто выбрасываете некоторые транзакции. Время от времени вы фактически применяете транзакции, делая изображение «контрольной точки». Это ускоряет отображение за счет замедления отмены.

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