Undo и Redo — анализ и реализации

в 8:33, , рубрики: .net, C#, c++, qt, redo, undo, UndoRedo, Анализ и проектирование систем

Привет! В связи со своей реальной задачей проанализировать возможности Qt и .NET для реализации так называемых «Назад» (Undo) и «Вперёд» (Redo), цель которых отменить действие и отменить отмену соответственно, я решил все свои мысли, идеи и задумки развернуть в этой статье, даже если они будут частично или совсем неверными (поэтому по возможности и интересу пишите в комментарии свои замечания). Хоть и на просторах Интернета спокойно можно найти хорошие (и не очень) библиотеки и примеры реализаций, более общего представления на эти вещи я нашёл не так скоро, да и то, только в ответе на StackOverflow, а этого было мне не достаточно. Во всём найденном есть моменты, которые меня порадовали, есть и которые огорчили. Пожалуй, стоит отменить все печали и радости… чтобы к ним снова вернуться… «Назад… в будущее»!

Undo и Redo — анализ и реализации - 1

Интересно? Добро пожаловать!

Исследование

Красная или синяя? Примерно к такому вопросу нужно будет прийти, после того, как решили реализовать в приложении Undo/Redo. Объясняю: есть два основных способа реализовать пошаговую отмену, для которых я присвоил следующие наименования: operation-oriented и value-oriented. Первый способ основан на создании операций (или транзакций), у которых есть два метода — сделать и вернуть всё как было. Второй способ не хранит никаких операций — он лишь записывает значения, которые изменились в определённый момент времени. И у первого и у второго способа есть свои плюсы и минусы.

UPD: Чтобы в дальнейшем было меньше вопросов, напомню, что Undo/Redo предназначено больше для хранения информации предыдущих вариантов документа (к примеру) во время редактирования. Записывать данные в БД или на диск будет долго, и это уже мало относится к цели Undo/Redo. Впрочем, если сильно надо — делайте, но лучше не стоит.

Метод 1: operation-oriented

Реализуется на основе паттерна «Команда» (Command).
Этот метод заключается в том, чтобы хранить операции в специальном стеке. У стека есть позиция (можно сказать, итератор), которая указывает на последнюю операцию. При добавлении операции в стек — она выполниться (redo), позиция инкрементируется. Для отмены операции стек вызывает команду undo из последней операции, а потом сдвигает позицию последней операции ниже (сдвигает, но не удаляет). Если понадобится вернуть действие — сдвиг выше, выполнение redo. Если после отмены добавляется новая операция, то есть два решения: либо заменять операции выше позиции новыми (и тогда вернуться к прежним будет невозможно), либо начинать новую «ветку» в стеке, но отсюда возникает вопрос — к какой ветке потом идти? Впрочем, ответ на этот вопрос уже искать нужно не мне, так как это зависит от требований к программе.

И так, для самого просто Undo/Redo нам нужно: базовый класс (интерфейс) с чисто виртуальными (абстрактными) функциями undo() и redo(), также класс, который будет хранить указатели на объекты, произведённые от базового класса и, конечно же, сами классы, в которых будут переопределены функции undo() и redo(). Также можно (в некоторых случаях даже очень нужно) будет сделать функции совмещения операций в одну, для того, чтобы, допустим, отменять не каждую букву по отдельности, а слова и предложения, когда буквы станут таковыми, и тому подобное. Поэтому также желательно для каждой операции присваивать определённый тип, при различии которых нельзя будет склеить операции.

И так, плюсы:

  • При правильном построении операций шансы пострадать бизнес-логике низки, так как выполняются именно операции, в которых также может быть задействована магия БЛ, только для undo нужно выполнять действия в обратном порядке, а сами действия должны быть обратными (исключая моменты, когда один объект меняется, и другие зависят от первого, тогда в таком случае в конце и undo и redo нужен будет пересчёт).
  • Менее требователен к памяти — записываются только операции, но не значения переменных. Если при операции вызывается механизм пересчёта чуть ли не всего и вся — в память эти изменения не попадают, а при отмене снова нужен будет пересчёт.
  • Более гибкий способ Undo/Redo.

Минусы:

  • При неправильном построении… у бизнес-логики нет и шанса на правильную работу с Undo/Redo.
  • Если операции вызывают пересчёт зависимостей и тому подобное, то такой подход будет требователен к производительности.

Также можно прочитать вот эту статью на Wiki про паттерн команд (Command), который и используется для реализации такого способа Undo/Redo, а также эту статью на Хабрахабре.

Метод 2: value-oriented

Реализуется на основе паттерна «Хранитель» (Memento).
Принцип метода — знать о всех возможных переменных, которые могут измениться, и в начале возможных изменений поставить стэк «на запись», а в конце — сделать коммит изменений.

Тем не менее, записываться должны все изменения. Если записывается только изменения, произведённые пользователем, но не записывались изменения зависимостей — то тогда при отмене/возврате зависимости останутся без изменений. Конечно, можно хитрым способом каждый раз вызывать пересчёт зависимостей, но это уже больше похоже на первый способ и удобнее тогда будет он. О способах реализации будет рассказано ниже, а пока посмотрим на достоинства и недостатки.

Плюсы:

  • Не нуждается в пересчётах — не требователен к производительности.
  • Бизнес-логика не страдает — всё подсчитанное просто снова встаёт на свои места.
  • Более простой способ Undo/Redo.

Минусы:

  • Более требователен к памяти, так как сохраняются все зависимые объекты (в противном случае либо страдает производительность, либо бизнес-логика).
  • Не способен на вызов определённых операций, так как идёт только «восстановление памяти».

Также можно прочитать вот эту статью на Wiki про паттерн Хранителя (Memento).

Плохой метод 3: full snapshot

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

UPD: И нет, здесь я не имел в виду паттерн Memento, который также может сохранять кроме частичного ещё полный снимок изменений/значений. Имеется в виду, что не желательно сохранять снимок всего документа, когда изменилось лишь пару значений. Если всё-таки этого не избежать, то это скорее vl-or, а в некоторых ситуациях, когда очень редко и по сложной схеме изменяется весь документ, вы можете отказаться от записи таких изменений (сказать пользователю, что откат изменений после этой операции будет недоступен).


Способы реализации

C++: Qt

Operation-oriented

Здесь разработчики на славу постарались. С помощью Qt можно легко и просто реализовать Undo/Redo. Записывайте рецепт. Нам понадобиться: QUndoStack, QUndoCommand, а также QUndoView и QUndoGroup по вкусу. Сначала от QUndoCommand наследуем собственные классы, в которых должны быть переопределены undo() и redo(), также желательно переопределить id() для определения типа операции, чтобы потом в переопределённой mergeWith(const QUndoCommand *command) можно было проверить обе операции на совместимость. После этого создаём объект класса QUndoStack, и помещаем в него все новые операции. Для удобства, можно взять QAction *undo и QAction *redo из функций стека, которые потом можно добавить в меню, или прикрепить к кнопке. А если нужно использовать несколько стеков, тогда в этом поможет QUndoGroup, если нужно отобразить список операций: QUndoView.

Также, в QUndoStack можно отмечать clear state (чистое состояние), которые, например, может означать сохранён ли документ на диск и т.д. Вполне удобная реализация op-or undo/redo.

Я реализовал самый простой пример на Qt.

Хочу посмотреть!

Вот схема классов, к которой я пришёл (скорее всего, я сильно ошибаюсь на счёт направления стрелок...):
Undo и Redo — анализ и реализации - 2
Здесь также упоминается некий «сервер», это на случай, если он тоже будет присутствовать и взаимодействовать с вашим приложением-клиентом. А вот и исходники (считайте, что всё писал «на коленке»).

Value-oriented

Упс… Qt такого варианта не предоставил. Даже поиск по ключевым словам «Qt memento» не дал ничего. Ну и ладно, там и такого вполне достаточно, а если не достаточно, можно воспользоваться Native'ными методами.

C++: Native

Так как в Qt не посчитали нужным добавить value-oriented Undo/Redo, поэтому нужно будет искать либо готовые реализации (где можно встретить магическое для меня слово «Memento»), либо реализовывать придётся самим. В основном всё реализуется на основе шаблонов. Всё это можно без проблем найти. Я, например, нашёл вот этот проект на GitHub. Тут реализованы сразу две идеи, можете взять и посмотреть, потестировать.

C#: .NET

Для меня C# и .NET пока что тёмные леса далёкой Сибири, но тем не менее, он мне очень и очень нужен. Поэтому стоит рассказать хотя бы о том, что мне удалось нагуглить.

Operation-oriented

Самыми хорошими примерами для меня были:

  • Хорошая статья на Хабрахабре.
  • Интересный пост про паттерн команд на .NET.
  • И просто хороший пример Undo/Redo с использованием Generics.

Вскоре нашлась и такая вот старая статья.

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

Value-oriented

Вообще, для такого рода задач в .NET есть интерфейс IEditableObject, но придётся много чего реализовывать с нуля, хотя пример реализации есть прямо на MSDN. Тем не менее, мне очень понравилась библиотека DejaVu, ради которой даже написана целая статья на Хабрахабре. Читайте, влюбляйтесь, пишите.

Есть ещё два примера, но они мне совсем не понравились:


Заключение

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

Удачи в будущем!

Автор: faserg1

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js