Undo/Redo Manager - как лучше сделать ?

[AlexLucas]

Доброго времени суток.
Пишу визуальный редактор.
Есть задача дать пользователю возможность откатывать свои действия.
По сути на сцене будут геометрические фигуры (Shape) и текстовые контейнеры, над которыми и будут производиться эти действия.
И появился вопрос - какой концепт вот такого Undo Manager'a лучше :

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

2) Регистрировать только текущие изменения, и объект(ы) который(е) изменился(ись) при выполнении определённых функций (действий).
Плюс - не нужно будет изменять все объекты, не нужно будет хранить инфу о всех объектах на сцене. Кроме того, в будущем надо будет внедрить возможность создания макросов, который по идее будет работать по такому принципу - регистрировать изменения одного объекта и воспроизводить их.
Минус - регистрация изменений будет сложнее, мне кажется. Кроме того, в s:TextArea (которую я использую) уже есть UndoManager, надо будет как-то с ним сотрудничать.

Что посоветуете вы ?

[Zebestov]

3) По сути — в точности п.1, только храним состояние лишь тех объектов, которые изменились. Таким образом имеем абсолютную схему хранения состояний (а не относительную, как в п.3), но при этом такую же экономную (почти такую же).

[expl]

2-й подход однозначно
Т.к. с сохранением состояний мороки тоже не мало,
а производительность и количество возможных отмен - просто сводит его применимость на нет.

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

Это кажется сложно - на самом деле при переходе на комманды код даже прозрачнее станет.

3) По сути — в точности п.1, только храним состояние лишь тех объектов, которые изменились. Таким образом имеем абсолютную схему хранения состояний (а не относительную, как в п.3), но при этом такую же экономную (почти такую же).

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

[AlexLucas]

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

Или я что-то не так понял из сообщения Zebestova?

[Zebestov]

Хранить нужно только те состояния, которые произвел пользователь. Остальные изменения вычисляются/восстанавливаются.

[expl]

Чем тогда это отличается от 2-го варианта?

Всмысле при сохранении изменений (например, вместе с коммандами) получаем состояния:
1:добавить круг в 0, 0 ->
2:добавить прямоугольник в 0, 0 ->
3:повернуть прямоугольник на 90º->
4:Удалить прямоугольник

Вариант с состояниями:
1:круг(0,0) ->
2:[ссылка на 1:], прямоугольник(0, 0, 0º) ->
3:[ссылка на 1:], прямоугольник(0, 0, 90º) ->
4:[ссылка на 1:]
Как бы получение структуры [3:[ссылка на 1:], прямоугольник(0, 0, 90º)] по предыдущей [2:[ссылка на 1:], прямоугольник(0, 0, 0º)] и действиям пользователя уже выглядит нетривиально

- Как компактно сохранить состояния не сохраняя изменений?
- Как это сделать просто на _нефункциональном_ языке?
- А если таки сохранять изменения, а не данные, то в чём разница?

- Зачем это всё, если можно просто сохранить изменение вместо сохранения состояния? - И вычислять ничего не надо будет - никаких дифов между старым и новым снимать не надо

[Zebestov]

Для меня сохранить изменения, скажем, позиции — это команда MOVE с относительными данными, а сохранить состояние — это команда POSITION с абсолютными данными. Возможно, я неверно понял автора и, стало быть, мое предложение — это и есть вариант два.

[expl]

Ну часть состояния может сохраняться для нужд отмены (оно будет частью "данных изменения")
но это не то же самое, что сохранять вообще всё состояние кусками для экономии.

Добавлено через 51 минуту
Да, таки есть 3-й _узкоспециализированный_ подход, работает, когда:
- нельзя исправлять нарисованное
- много графики
Суть:
- при рисовании новой линии запоминаем её параметры (координаты точек) и ложим в список
- добавляем новый спрайт, рисуем там линию
- при добавлении 100-го спрайта удаляем первый из списка и отрисовываем его содержимое в _растровую_ подложку - для повышения производительности отрисовки
- при откате просто удаляем спрайты
- только когда дойдем до 1-го спрайта - берём стираем все из растровой подложки и рисуем всё сначала по сохранённым данным
- получается, что тормоза наступают только после 100-й отмены и вцелом редактор не тормозит при добавлении графики.
Но это работает, только при запрете правок уже нарисованного.

[AlexLucas]

То есть мне полюбому в каждой функции которая будет производить какие-то перемены, нужно будет создавать новую команду и добавлять её в стак ?
А если я эту функцию буду вызывать из Undo/Redo, у меня создастся автоматом другая redo/undo комманда, да и как отличить когда вызывается комманда из undo или из redo? Добавить дополнительные параметры в функцию ?
Или для каждого типа операций создавать свой класс комманды ? Как тут ?
Я так понял именно так делается в паттерне Command?

[expl]

То есть мне полюбому в каждой функции которая будет производить какие-то перемены, нужно будет создавать новую команду и добавлять её в стак ?

Угу, ничего страшного в этом нет - передаем комманде контекст (со всем необходимым) при создании, чтобы она там ковырялась - чтобы не передавать параметры каждый раз - и всё не так сложно становится

А если я эту функцию буду вызывать из Undo/Redo, у меня создастся автоматом другая redo/undo комманда, да и как отличить когда вызывается комманда из undo или из redo? Добавить дополнительные параметры в функцию ?

- Не надо делать вызовы других комманд внутри комманд. И сами функции Undo и Redo коммандами делать смысла тоже нет.
(На самом деле можно создавать комманду и вызывать execute внути другой комманды, но _не_ добавлять при этом её в список отмены - самому вызывать undo этих вложенных комманд внутри своего undo. Т.е. вложенные комманды не палятся в общем списке)
- Не надо внутри Command::execute добавлять себя в список отмены - лучше сделать другую функцию в контроллере или UndoManager'е:

public function executeCommand(command:Command):void
{
    // Если надо поддерживать redo - то сюда ещё добавляется код по отбрасыванию отменённого
    // (Раз мы сделали действие - всё что отменили стирается и повторить обратно его должно быть нельзя,
    // этож не система контроля версий - чтобы ветки городить)
    // Но здесь без redo
    _undoList.push(command);
    command.init(_context);
    command.execute();
}
 
public function undo():void
{
   var command:Command = _undoList.pop();
   if (command != null)
   {
       command.undo();
   }
}

И всё станет просто и понятно.
А специфичные параметры комманды передаём в конструктор:

_undoManager.execute(new RotateCommand(object, rotateAngle));