Шаблон проектирования для отмены движка
Я пишу инструмент структурного моделирования для применения в гражданском строительстве. У меня есть один огромный класс модели, представляющий все здание, которое включает в себя наборы узлов, линейных элементов, нагрузок и т. Д., Которые также являются пользовательскими классами.
Я уже кодировал движок отмены, который сохраняет глубокую копию после каждой модификации модели. Теперь я начал думать, мог бы я по-другому кодировать. Вместо сохранения глубоких копий, я мог бы сохранить список каждого действия модификатора с соответствующим обратным модификатором. Чтобы я мог применить обратные модификаторы к текущей модели, чтобы отменить, или модификаторы, чтобы повторить.
Я могу представить, как вы выполняете простые команды, которые изменяют свойства объекта и т. Д. Но как насчет сложных команд? Как вставка новых объектов узлов в модель и добавление некоторых линейных объектов, которые сохраняют ссылки на новые узлы.
Как можно было бы реализовать это?
22 ответа
Большинство примеров, которые я видел, используют для этого вариант Command-Pattern. Каждое отменяемое действие пользователя получает свой собственный экземпляр команды со всей информацией, чтобы выполнить действие и откатить его. Затем вы можете сохранить список всех команд, которые были выполнены, и вы можете откатить их одну за другой.
Я думаю, что и memento, и команда не практичны, когда вы имеете дело с моделью размера и объема, которую подразумевает OP. Они будут работать, но это будет много работы для поддержания и расширения.
Для такой проблемы, я думаю, вам нужно встроить поддержку вашей модели данных для поддержки дифференциальных контрольных точек для каждого объекта, участвующего в модели. Я сделал это один раз, и он работал очень гладко. Самое важное, что вам нужно сделать, - это избегать прямого использования указателей или ссылок в модели.
Каждая ссылка на другой объект использует некоторый идентификатор (например, целое число). Всякий раз, когда объект нужен, вы ищите текущее определение объекта из таблицы. Таблица содержит связанный список для каждого объекта, который содержит все предыдущие версии, а также информацию о том, для какой контрольной точки они были активны.
Реализация отмены / повтора проста: выполните свое действие и установите новую контрольную точку; откатить все версии объекта до предыдущей контрольной точки.
Это требует некоторой дисциплины в коде, но имеет много преимуществ: вам не нужны глубокие копии, поскольку вы выполняете дифференциальное хранение состояния модели; вы можете ограничить объем памяти, который вы хотите использовать (чтоочень важно для таких вещей, как модели САПР), либо количеством повторов, либо объемом используемой памяти; очень масштабируемый и не требующий обслуживания для функций, которые работают в модели, так как им не нужно ничего делать для реализации отмены / повтора.
Как уже говорили другие, шаблон команд является очень мощным методом реализации Undo/Redo. Но есть важное преимущество, которое я хотел бы упомянуть в шаблоне команд.
При реализации отмены / повтора с использованием шаблона команды вы можете избежать большого количества дублированного кода, абстрагируя (до некоторой степени) операции, выполняемые с данными, и используя эти операции в системе отмены / повтора. Например, в текстовом редакторе вырезать и вставить являются дополнительными командами (кроме управления буфером обмена). Другими словами, операция отмены для вырезки - это вставка, а операция отмены для вставки - вырезание. Это относится к гораздо более простым операциям, таким как ввод и удаление текста.
Ключевым моментом здесь является то, что вы можете использовать вашу систему отмены / возврата в качестве основной системы команд для вашего редактора. Вместо написания системы, такой как "создать объект отмены, изменить документ", вы можете "создать объект отмены, выполнить операцию возврата для объекта отмены, чтобы изменить документ".
Теперь, по общему признанию, многие люди думают про себя: "Ну, да, разве это не часть концепции командования?" Да, но я видел слишком много командных систем, которые имеют два набора команд, один для немедленных операций, а другой для отмены / повтора. Я не говорю, что не будет команд, относящихся к немедленным операциям и отмене / повтору, но уменьшение дублирования сделает код более понятным.
Если вы говорите о GoF, шаблон Memento определенно обращается к отмене.
Возможно, вы захотите обратиться к коду Paint.NET для их отмены - у них действительно хорошая система отмены. Это, вероятно, немного проще, чем вам нужно, но это может дать вам некоторые идеи и рекомендации.
-Адам
Это может быть случай, когда CSLA применимо. Он был разработан для обеспечения сложной поддержки отмены объектов в приложениях Windows Forms.
Я успешно реализовал сложные системы отмены, используя шаблон Memento - очень легко, и имеет преимущество, естественно, также предоставляя среду Redo. Более тонкое преимущество заключается в том, что совокупные действия могут содержаться и в одной отмене.
В двух словах, у вас есть две стопки объектов сувениров. Один для отмены, другой для повторения. Каждая операция создает новый сувенир, который в идеале будет вызывать изменение состояния вашей модели, документа (или чего-либо еще). Это добавляется в стек отмены. Когда вы выполняете операцию отмены, в дополнение к выполнению действия "Отменить" для объекта Memento для повторного изменения модели, вы также извлекаете объект из стека отмены и помещаете его прямо в стек повторного выполнения.
Каким образом реализуется метод изменения состояния вашего документа, полностью зависит от вашей реализации. Если вы можете просто выполнить вызов API (например, ChangeColour(r,g,b)), то перед ним следует запрос, чтобы получить и сохранить соответствующее состояние. Но шаблон также будет поддерживать создание глубоких копий, снимков памяти, создание временных файлов и т. Д. - все зависит от вас, поскольку это просто реализация виртуального метода.
Для выполнения совокупных действий (например, пользователь Shift-выбирает загрузку объектов для выполнения операции, такой как удаление, переименование, изменение атрибута), ваш код создает новый стек отмены в виде отдельного сувенира и передает его фактической операции в добавить отдельные операции в. Таким образом, ваши методы действий не должны (а) иметь глобальный стек, о котором нужно беспокоиться, и (б) могут быть закодированы одинаково, независимо от того, выполняются ли они изолированно или как часть одной агрегатной операции.
Многие системы отмены находятся только в памяти, но, я думаю, вы можете сохранить стек отмены, если хотите.
Просто читал о шаблоне команд в моей книге по гибкой разработке - может быть, у этого есть потенциал?
Вы можете заставить каждую команду реализовывать командный интерфейс (который имеет метод Execute()). Если вы хотите отменить, вы можете добавить метод Undo.
больше информации здесь
Я с Мендельтом Зибенгой о том, что вы должны использовать командный паттерн. Образцом, который вы использовали, был Образец Мементо, который может и станет очень расточительным со временем.
Поскольку вы работаете с приложением, интенсивно использующим память, вы должны иметь возможность указать, какой объем памяти может занимать механизм отмены, сколько уровней отмены сохранено или какое-то хранилище, в котором они будут сохранены. Если вы этого не сделаете, вы скоро столкнетесь с ошибками, вызванными нехваткой памяти машины.
Я бы посоветовал вам проверить, есть ли фреймворк, который уже создал модель для отмен на выбранном вами языке программирования / фреймворке. Приятно изобретать новые вещи, но лучше взять что-то уже написанное, отлаженное и протестированное в реальных сценариях. Было бы полезно, если бы вы добавили то, что вы пишете, чтобы люди могли рекомендовать рамки, которые они знают.
Большинство примеров, которые я прочитал, делают это, используя либо команду, либо шаблон памяти. Но вы можете сделать это и без шаблонов проектирования с помощью простой структуры deque.
Это простая структура для добавления функциональности Undo/Redo в ваши приложения на основе классического шаблона проектирования Command. Он поддерживает действия слияния, вложенные транзакции, отложенное выполнение (выполнение при фиксации транзакции верхнего уровня) и возможную нелинейную историю отмен (где вы можете выбрать несколько действий для повторения).
Умный способ справиться с отменой, который сделает ваше программное обеспечение также пригодным для многопользовательской совместной работы, - это оперативное преобразование структуры данных.
Эта концепция не очень популярна, но четко определена и полезна. Если определение выглядит слишком абстрактным для вас, этот проект является успешным примером того, как операционное преобразование для объектов JSON определено и реализовано в Javascript
Для справки, вот простая реализация шаблона Command для Undo/Redo в C#: Простая система Undo/Redo для C#.
Мы повторно использовали файл загрузки и сохранения кода сериализации для "объектов" для удобной формы, чтобы сохранить и восстановить все состояние объекта. Мы помещаем эти сериализованные объекты в стек отмены - вместе с некоторой информацией о том, какая операция была выполнена, и намекаем на отмену этой операции, если недостаточно данных, извлеченных из сериализованных данных. Отмена и повторение часто просто заменяют один объект другим (теоретически).
Было много МНОГИХ ошибок из-за указателей (C++) на объекты, которые никогда не были исправлены, когда вы выполняете некоторые нечетные последовательности повторов отмены (те места, которые не обновлены, чтобы более безопасные отменяющие "идентификаторы"). Ошибки в этой области часто... ммм... интересные.
Некоторые операции могут быть особыми случаями для скорости / использования ресурсов - например, определение размеров, перемещение объектов.
Мульти-выбор также предоставляет некоторые интересные сложности. К счастью, у нас уже была концепция группировки в коде. Комментарий Кристофера Джонсона о подпунктах довольно близок к тому, что мы делаем.
Я должен был сделать это, когда писал решатель для игры в пег-джамп. Я делал каждое перемещение объекта Command, который содержал достаточно информации, чтобы его можно было либо сделать, либо отменить. В моем случае это было так же просто, как сохранить начальную позицию и направление каждого движения. Затем я сохранил все эти объекты в стеке, чтобы программа могла легко отменить столько ходов, сколько необходимо при возврате.
Вы можете попробовать готовую реализацию шаблона Undo/Redo в PostSharp. https://www.postsharp.net/model/undo-redo
Это позволяет добавлять функции отмены / повтора в ваше приложение без самостоятельной реализации шаблона. Он использует шаблон Recordable для отслеживания изменений в вашей модели и работает с шаблоном INotifyPropertyChanged, который также реализован в PostSharp.
Вам предоставляются элементы управления пользовательским интерфейсом, и вы можете решить, каким будет название и степень детализации каждой операции.
Вы можете сделать свою первоначальную идею совершенной.
Используйте постоянные структуры данных и следите за сохранением списка ссылок на старое состояние. (Но это действительно работает, только если операции, все данные в вашем классе состояний неизменны, и все операции над ним возвращают новую версию --- но новая версия не должна быть глубокой копией, просто замените копию измененных частей -он-запись".)
В первом разделе "Шаблоны проектирования" (GoF, 1994) приведен пример использования отмены / повтора в качестве шаблона проектирования.
Однажды я работал над приложением, в котором все изменения, внесенные командой в модель приложения (т. Е. CDocument... мы использовали MFC), были сохранены в конце команды путем обновления полей во внутренней базе данных, поддерживаемой в модели. Поэтому нам не нужно было писать отдельный код отмены / повтора для каждого действия. Стек отмены просто запоминал первичные ключи, имена полей и старые значения каждый раз, когда запись изменялась (в конце каждой команды).
Я нашел шаблон Command очень полезным здесь. Вместо того, чтобы реализовывать несколько обратных команд, я использую откат с отложенным выполнением для второго экземпляра моего API.
Этот подход кажется разумным, если вам нужны небольшие усилия по реализации и простота обслуживания (и вы можете позволить себе дополнительную память для второго экземпляра).
Смотрите здесь для примера: https://github.com/thilo20/Undo/
По моему мнению, UNDO/REDO может быть реализовано двумя способами в широком смысле. 1. Уровень команд (называемый командным уровнем Undo/Redo) 2. Уровень документа (называемый глобальным Undo / Redo)
Командный уровень: как указывают многие ответы, это эффективно достигается с помощью шаблона Memento. Если команда также поддерживает журналирование действия, повторное выполнение легко поддерживается.
Ограничение: Как только область действия команды вышла, отмена / повтор невозможна, что приводит к уровню документа (глобальному) отменить / повторить
Я полагаю, что ваш случай вписался бы в глобальную отмену / повтор, поскольку он подходит для модели, которая занимает много места в памяти. Кроме того, это подходит также для выборочного отмены / повторного выполнения. Есть два примитивных типа
- Вся память отменить / повторить
- Уровень объекта Отменить Повторить
В "Отмена / восстановление всей памяти" вся память обрабатывается как связанные данные (например, дерево, или список, или график), а память управляется приложением, а не ОС. Таким образом, операторы new и delete в C++ перегружены, чтобы содержать более конкретные структуры для эффективной реализации таких операций, как a. Если какой-либо узел изменен, б. хранение и очистка данных и т. д. В основе своей работы лежит копирование всей памяти (при условии, что распределение памяти уже оптимизировано и управляется приложением с использованием расширенных алгоритмов) и сохранение ее в стеке. Если запрашивается копия памяти, древовидная структура копируется на основе необходимости иметь неглубокую или глубокую копию. Глубокая копия сделана только для той переменной, которая изменена. Поскольку каждая переменная выделяется с помощью пользовательского выделения, приложение имеет последнее слово, когда нужно удалить ее, если это необходимо. Вещи становятся очень интересными, если мы должны разделить Undo / Redo, когда это происходит, когда нам нужно программно-избирательно отменить / Redo набор операций. В этом случае только этим новым переменным, или удаленным переменным, или измененным переменным присваивается флаг, так что Undo / Redo только отменяет / восстанавливает эти воспоминания. Вещи становятся еще более интересными, если нам нужно выполнить частичное Undo / Redo внутри объекта. Когда это так, используется более новая идея "Шаблон посетителя". Он называется "Отменить / повторить уровень объекта"
- Уровень объекта Отменить / Повторить: когда вызывается уведомление об отмене / повторе, каждый объект реализует потоковую операцию, в которой стример получает от объекта старые данные / новые данные, которые запрограммированы. Данные, которые не подлежат нарушению, остаются без изменений. Каждый объект получает в качестве аргумента стример, и внутри вызова UNDo/Redo он направляет / выводит данные объекта.
И 1, и 2 могут иметь такие методы, как 1. BeforeUndo() 2. AfterUndo() 3. BeforeRedo() 4. AfterRedo(). Эти методы должны быть опубликованы в базовой команде Undo/redo (не в контекстной команде), чтобы все объекты реализовали эти методы, чтобы получить определенное действие.
Хорошая стратегия - создать гибрид из 1 и 2. Прелесть в том, что эти методы (1 и 2) сами используют шаблоны команд
Я не знаю, будет ли это вам полезно, но когда мне пришлось сделать что-то похожее в одном из моих проектов, я закончил тем, что скачал UndoEngine с http://www.undomadeeasy.com/ - замечательный движок и я действительно не слишком заботился о том, что было под капотом - это просто работало.