Здравствуйте, Klapaucius, Вы писали:

K>Есть текст (не разделен на строки одинаковой длины), который можно редактировать. Т.е. вставлять, удалять, добавлать в начало, в конец символ/блок символов. Должен поддерживаться "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий. Также, желательно, иметь возможность сравнивать версии. Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст.

Убедительная просьба — дочитать до конца, прежде чем комментировать.

Начнем с требования "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий.

Пройдем по виртуальному пространству (как — описано у Рихтера), найдем максимальный блок (обычно это 1.7-1.8 Гб). Захватим его с помощью VirtualAlloc. Это и будет наша свободная память. Все нижеописанные структуры будут храниться там. Назовем эту область буфером (Б).

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

Примечание. Если ты готов придраться к тому, что при этом не будут использованы остальные маленькие блоки, то захватим все блоки и сделаем Б как список из этих блоков. Это усложнит реализацию, но на идею не повлияет.

Заведем дерево версий (ДВ). Это дерево произвольной арности. Элемент дерева содержит

указатель на родителя
список указателей на чайлдов
указатель на список фрагментов текста ( о нем ниже)
порядковый номер версии (о нем ниже).

Заведем список фрагментов (СФ). Элемент списка содержит указатель на начало фрагмента, на конец фрагмента, и указатель на следующий фрагмент.

Создадим корень ДВ и поместим его в Б. После него разместим в Б исходный текст. СФ в корневом элементе имеет один элемент , показывающий на начало и конец текста. Текущий узел — корень.

Подготовка закончена.

Начнем с удаления символов или подстроки.

Строим нового чайлда от текущего узла. Копируем его список и производим в нем изменения.

Например

Исходный текст abcdefg, исходный список — (a,g). Требуется удалить cd. Новый список (a,b)-(e,g)

Естественно, под a,b,e,g здесь понимаются указатели на соответствующие места в Б.

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

Добавление.

Мне вообще-то все равно, в начало, в конец или куда-то еще.
Добавляемый фрагмент — в Б. Без длины и разделителей.
Строим нового чайлда от текущего узла. Копируем его список и производим в нем изменения.

Например, пусть после предыдущего удаления нужно добавить "xyz" после a. "xyz" записываем в Б.

Получим

(a,a)-(x,z)-(b,b)-(e,g).

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

Замена. Кстати, в задаче отсутствует. Решается элементарно — удаление и последующая вставка в одной операции.

Можно после получения нового списка попробовать "сжать" его. Пусть у нас образовался в нем кусок из 5 элементов, а каждый элемент показывает на однобуквенный фрагмент. Ясно, что 5 элементов списка занимают больше места, чем один элемент списка + 5. Объединим эти 5 букв в новый фрагмент и добавим его в Б. 5 элементов ликвидируем, заведем один и пусть он показывает на этот новый фрагмент

Все новые фрагменты текста, узлы ДВ, СФ хранятся в Б. До его исчерпания.

Undo — перейти к родителю в ДВ
Redo — перейти к младшему чайлду в ДВ.
Сравнение версий — получить указатели на два узла ДВ и сравнить тексты.

//////////////////////////////////////////////////////////////////////////////

На этом можно бы и закончить. Но вот такое вот место в условии несколько двусмысленно и может дать повод для придирок

>Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст

Весь текст я не храню. Более того, по объему хранимых байтов текста тут явный минимум. Но вот насчет "объем, сопоставимый с объемом изменений сделанных в этой версии" — как сказать. Список-то я копирую каждый раз. Так что с одной стороны я вроде этому требованию удовлетворяю, а с другой — нет

(Написал это и подумал — нет, не минимум. Можно еще уменьшить. При добавлении текста ищем его среди всех текстовых фрагментов Б (как подстроку). Если найдем, то в Б его не добавляем, оформляем СФ с указателями на найденный кусок

Ликвидируем СФ. Вместо него заведем ориентированный граф фрагментов (ГФ) В начальной ситуации этот граф содержит тот же список, что и выше. Назовем этот список путем в графе (ПГ). Итак, узел ДВ имеет указатель на путь в графе (который есть СФ де-факто)

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

Например

У родителя ПГ состоит из 10 фрагментов. Выясняем, что изменение касается только фрагментов 6 и 7 (замечу, что любое изменение касается только последовательных фрагментов и только один раз) и вместо них нужно добавить 1 новый фрагмент
Новый ПГ будет — 5 элементов из старого ПГ. В 5 элементе устраиваем развилку на новый элемент, а от него — на старый 8-й.

Для того, чтобы в дальнейшем найти нужный путь, помечаем все ребра в этом ПГ номером версии. В "развилке" берем то направление, которое соответствует текущей версии. Если текущей версии нет, то максимальной из версий, не большей текущей. Номер версии храним в элементе ДВ, это просто автоинкрементное значение. Впрочем, здесь надо продумать еще раз. Может, имеет смысл timestamp использовать.

Примечание 1. Если везде, где говорится об указателе, использовать смещение от начала Б, то весь Б можно выгрузить в файл, а потом загрузить заново и продолжить редактирование. Лишь бы нашелся свободный блок не меньшего чем Б размера. Естественно, замена указателя на смещение слегка замедлит работу.
Примечание 2. Для удаления всей этой конструкции необходим один вызов VirtualFree.