nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Граф Андуку

Два года назад я написал свой первый прототип древовидного Undo, где при возвращении назад и "изменении прошлого" вся дальнейшая история не стирается, а просто "уходит вбок" - мы создаём параллельную реальность, но при желании можем вернуться в исходную.

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

У этого подхода есть положительные моменты - закончится, наконец, путаница, что означает выделенное действие в History - что оно уже сделано, или сделано все, что было до него? А проблема вся в том, что у нас всё время смешивалось два совершенно различных понятия - "состояние документа", вершина графа, и "действие", которое переводит одно состояние в другое, т.е ребро графа. Когда мы жмем undo/redo или жмем на одно из действий в History, мы хотим вернуть определенное состояние документа, но нам упорно показывают действия. Из этой же оперы - неизбежный фиктивный элемент в History, как правило, первая запись "новый документ" - он нужен, потому что в линейном Undo состояний на одно больше, чем действий, а мы должны уметь переходить на каждое из состояний!

Но проблем тоже хватает: в линейном undo определено и прошлое, и будущее, так что кнопок undo/redo вполне достаточно. В древовидном undo определено по крайней мере прошлое, так что действие кнопки undo определяется однозначно, а redo можно заставить работать по "текущей альтернативной вселенной". В графовом же undo уже и прошлое становится неопределенным, поскольку в один узел мы могли попасть разными путями, и какой из них выбрать при нажатии undo - уже неясно. Скорее всего, на этот граф все-таки придется наложить "нашу мировую линию" - линейный список пройденных нами узлов, и при нажатии на undo/redo путешествовать по этому списку, иногда даже по кругу.

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

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

Сейчас занялся рефакторингом всего этого бреда, и по мере выхода более-менее юзабельного кода собираюсь выкладывать его в ЖЖ, вдруг кому будет интересно. Вещь специфическая - код написан на Delphi, меня многие после этой фразы перестают воспринимать всерьез, но привести мне пример другого языка, который компилировался бы в нормальный машинный код, а не промежуточный, как java/dotnet/ruby/python, и при этом поддерживал бы интроспекцию (метаклассы, просмотр свойств и методов объектов, автоматическая сериализация/десериализация без тьмы кода), и еще и обходился бы без зверских Фреймворков на сотни мегабайт, они не могут. Хорошо, что я не программист, а то мог бы и обидеться.

Из-за специфичности я подумываю описывать всё это не здесь, а от имени ЖЖ-юзера undooku, созданного с этой целью.
Tags: древовидный undo
Subscribe

Recent Posts from This Journal

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 35 comments

Recent Posts from This Journal

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…