undo redo что это
Undo/Redo — Иллюзия простоты
Такая простая и привычная функция в любом текстовом и графическом редакторе. Казалось бы, какие могут быть сложности с её реализацией? Впервые столкнувшись с разработкой Undo/Redo для текстового редактора XtraRichEdit, мы задумались, а какой же подход нам избрать?
Было очевидно, что должен существовать некий объект, отвечающий за историю изменений. В этом объекте должен храниться список элементов, представляющих собой отдельные действия. Каждый такой элемент должен хранить достаточно информации чтобы откатить действие (Undo), а также повторить его (Redo).
Поскольку действия могут быть самыми разными (вставка текста, изменение шрифта, добавление красной строки в параграф), мы сразу решили, что элементы буфера Undo будут не только хранить все необходимые данные для отката/повтора операции, но и будут сами ответственны за выполнение отката и повтора:
Первый прототип класса для буфера Undo выглядел следующим образом:
Руки так и тянутся написать метод Undo:
Лаконично, изящно… но совершенно неправильно.
Для начала, при попытке вызвать метод Undo при пустом списке, вылетит исключение. Исправляем:
И вновь получаем неправильный код. Ведь если вызвать метод Undo несколько раз подряд, то будет раз за разом вызываться Undo для последнего элемента в списке, что неправильно. Вносим изменения:
Вот теперь всё хорошо. Что-ж, пора приниматься за Redo. Ничего сложного…
Oops! Приехали.
В нашей реализации Undo мы в процессе отката безвозвратно теряем откатанные элементы, поэтому делать Redo просто некому. Придется завести индекс, указывающий на текущий элемент в буфере обмена. Итак:
Уже лучше, по крайней мере похоже на что-то работоспособное. Обратите внимание, что в случае Undo индекс изменяется после отката, а в случае Redo — до наката. Мы также не забыли инкрементировать индекс при добавлении элемента в историю.
А теперь давайте посмотрим внимательно на метод Add и зададимся вопросом, как он будет себя вести в случае, если мы выполнили и записали в историю 5 действий, затем откатили 3 из них и собираемся выполнить новое действие? Поразмыслив и посмотрев как сделано у других (всё уже украдено до нас) приходим к выводу, что в таком случае та часть истории действий, что находится после текущего индекса, должна быть потеряна, а вместо неё начнут записываться новые действия:
Вот теперь, наконец, простейшая реализация Undo/Redo стала работоспособной.
Получилось элегантно и красиво. Первое выполнение действия — это Redo этого действия из текущего состояния. Откат — Undo из текущего состояния. Повтор — вновь выполнение операции из текущего на тот момент состояния.
В последних фразах мы несколько раз употребили слово состояние. Дело в том, что та информация, которая сохраняется в буфере undo, является вполне корректной в момент сохранения. Однако уже в следующий момент она может стать некорректной. Простейший пример. У нас есть текст «Hello World!».
Мы выполняем операцию вставки текста « DevExpress » перед словом «World». При этом в буфер undo мы поместим информацию о том, что в позицию с индексом 6 (считаем с 0) был вставлен текст « DevExpress».
Выполним следующее действие: вставим в начало текста строку «We say: ». Разумеется после этого действия информация о позиции, куда надо вставить строку « DevExpress» станет некорректной.
Если в этот момент вызвать Undo для первой операции, то содержимое документа будет испорчено. Чтобы информация стала корректной, необходимо произвести перерасчёт.
А можно ли в каком-то случае обойтись без перерасчёта? Безусловно, можно, если предположить, что откат каждой операции приводит документ ровно в то состояние, которое он имел на момент выполнения операции. Аналогичное требование следует наложить и на повтор операции.
В этом получается, что информация в буфере undo автоматически «становится» корректной, как только документ приходит в то исходное состояние, в котором эта информация была сохранена. Если же состояние отлично от исходного, то эта информация в общем случае некорректна и использовать её нельзя. А поскольку откат операций происходит в порядке, обратном их выполнению, то мы никогда не сможем воспользоваться информацией до того, как документ будет приведён в исходное состояние.
Вот примерно какими соображениями можно пользоваться при реализации простенького Undo/Redo менеджера для собственного текстового или графического редактора. Однако, в жизни всё бывает несколько иначе, о чём мы поведаем вам в следующей статье.
PS:
В процессе написания этой статьи мы заинтересовались, а когда же появилась такая полезная вещь как Undo?
Старательно погуглив, пришли к выводу, что это произошло где-то в период с 1971 по 1976 годы. Так, современные мануалы по редактору ed, утверждают, что в нём поддерживается undo. Однако, в мануале от первого юникса за 1971 год упоминания об Undo ещё нет. А вот в редакторе vi, первая версия которого вышла в 1976 году Undo похоже было изначально.
Tic Tac Toe, часть 2: Undo/Redo с хранением состояний
Продолжение статьи Tic Tac Toe, часть 1, в которой мы начали разработку этой игры на Svelte. В этой части мы доделаем игру до конца. Добавим команды Undo/Redo, произвольный доступ к любому шагу игры, попеременные ходы с противником, вывод статуса игры, определение победителя.
Команды Undo/Redo
На этом этапе в приложение были добавлены команды Undo/Redo. В хранилище history добавлены методы push и redo.
В класс History добавлены методы push, redo, canUndo, canRedo.
В метод push класса History добавлено удаление всех состояний от текущего до последнего. Если мы несколько раз выполним команду Undo и выполним клик в игровом поле, то все состояния справа от текущего до последнего будут удалены из хранилища и будет добавлено новое состояние.
В компоненте App добавлены кнопки Undo и Redo. Если выполнение команд не возможно, то они деактивируются.
Смена хода
Выполнено попеременное появление крестика или нолика после клика мышкой.
Метод clickCell() убран их хранилища history, весь код метода перенесен в обработчик handleClick() компонента Board.
Таким образом была устранена ранее допущенная ошибка, в хранилище была зависимость от логики этой конкретной игры. Сейчас эта ошибка устранена, и хранилище можно использовать повторно в других играх и приложениях без изменений.
Ранее состояние шага игры описывалось только массивом из 9 значений. Сейчас состояние игры определяется объектом содержащим массив и свойством xIsNext. Инициализация этого объекта в начале игры выглядит так:
И еще можно отметить, что хранилище history сейчас может воспринимать состояния описанные любым образом.
Произвольный доступ к истории ходов
В хранилище history добавили метод setCurrent(current), с помощью которого устанавливаем выбранное текущее состояние игры.
В компоненте App добавили вывод истории ходов в виде кнопок.
Определение победителя, вывод статуса игры
Добавлена функция определения победителя calculateWinner() в отдельном файле helpers.js:
Добавлено производное хранилище status для определения статуса игры, здесь определяется исход игры: победитель или ничья:
В компоненте App добавлен вывод статуса игры:
В компоненте Board в обработчик клика handleClick() добавлены ограничения: невозможно выполнить клик в заполненной клетке и по окончании игры.
Игра закончена! В следующей статье рассмотрим реализацию этой же игры с помощью паттерна Command, т.е. с хранением команд Undo/Redo вместо хранения отдельных состояний.
Undo и Redo — анализ и реализации
Интересно? Добро пожаловать!
Исследование
Красная или синяя? Примерно к такому вопросу нужно будет прийти, после того, как решили реализовать в приложении Undo/Redo. Объясняю: есть два основных способа реализовать пошаговую отмену, для которых я присвоил следующие наименования: operation-oriented и value-oriented. Первый способ основан на создании операций (или транзакций), у которых есть два метода — сделать и вернуть всё как было. Второй способ не хранит никаких операций — он лишь записывает значения, которые изменились в определённый момент времени. И у первого и у второго способа есть свои плюсы и минусы.
UPD: Чтобы в дальнейшем было меньше вопросов, напомню, что Undo/Redo предназначено больше для хранения информации предыдущих вариантов документа (к примеру) во время редактирования. Записывать данные в БД или на диск будет долго, и это уже мало относится к цели Undo/Redo. Впрочем, если сильно надо — делайте, но лучше не стоит.
Метод 1: operation-oriented
Реализуется на основе паттерна «Команда» (Command).
Этот метод заключается в том, чтобы хранить операции в специальном стеке. У стека есть позиция (можно сказать, итератор), которая указывает на последнюю операцию. При добавлении операции в стек — она выполнится (redo), позиция инкрементируется. Для отмены операции стек вызывает команду undo из последней операции, а потом сдвигает позицию последней операции ниже (сдвигает, но не удаляет). Если понадобится вернуть действие — сдвиг выше, выполнение redo. Если после отмены добавляется новая операция, то есть два решения: либо заменять операции выше позиции новыми (и тогда вернуться к прежним будет невозможно), либо начинать новую «ветку» в стеке, но отсюда возникает вопрос — к какой ветке потом идти? Впрочем, ответ на этот вопрос уже искать нужно не мне, так как это зависит от требований к программе.
И так, для самого просто Undo/Redo нам нужно: базовый класс (интерфейс) с чисто виртуальными (абстрактными) функциями undo() и redo(), также класс, который будет хранить указатели на объекты, произведённые от базового класса и, конечно же, сами классы, в которых будут переопределены функции undo() и redo(). Также можно (в некоторых случаях даже очень нужно) будет сделать функции совмещения операций в одну, для того, чтобы, допустим, отменять не каждую букву по отдельности, а слова и предложения, когда буквы станут таковыми, и тому подобное. Поэтому также желательно для каждой операции присваивать определённый тип, при различии которых нельзя будет склеить операции.
Метод 2: value-oriented
Реализуется на основе паттерна «Хранитель» (Memento).
Принцип метода — знать о всех возможных переменных, которые могут измениться, и в начале возможных изменений поставить стэк «на запись», а в конце — сделать коммит изменений.
Тем не менее, записываться должны все изменения. Если записывается только изменения, произведённые пользователем, но не записывались изменения зависимостей — то тогда при отмене/возврате зависимости останутся без изменений. Конечно, можно хитрым способом каждый раз вызывать пересчёт зависимостей, но это уже больше похоже на первый способ и удобнее тогда будет он. О способах реализации будет рассказано ниже, а пока посмотрим на достоинства и недостатки.
Плохой метод 3: full snapshot
Если что и говорить о требовательности к памяти, то этот метод будет есть очень много. Представьте ситуацию, когда при наборе лишь одного символа сохранялся весь документ. И так каждый раз. Представили? А теперь забудьте об этом методе и более не вспоминайте, ибо это уже не Undo/Redo, а бэкапы.
Способы реализации
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.
Value-oriented
Упс… Qt такого варианта не предоставил. Даже поиск по ключевым словам «Qt memento» не дал ничего. Ну и ладно, там и такого вполне достаточно, а если не достаточно, можно воспользоваться Native’ными методами.
C++: Native
Так как в Qt не посчитали нужным добавить value-oriented Undo/Redo, поэтому нужно будет искать либо готовые реализации (где можно встретить магическое для меня слово «Memento»), либо реализовывать придётся самим. В основном всё реализуется на основе шаблонов. Всё это можно без проблем найти. Я, например, нашёл вот этот проект на GitHub. Тут реализованы сразу две идеи, можете взять и посмотреть, потестировать.
Operation-oriented
Вскоре нашлась и такая вот старая статья.
Быть может, что-то сможете найти и вы, а возможно на основе этого взять и написать свой велосипед гениальный код. Дерзайте.
Value-oriented
Заключение
И так, что нужно знать, чтобы выбрать между двумя методами реализации только одну? Во-первых, реализацию вашего проекта, написан ли (будет?) он на основе команд, или просто изменение множества значений (если ни то, ни другое — думаю, лучше переписывать проект). Во-вторых, требования к памяти и производительности, ибо возможно именно из-за них придётся отказаться от одного варианта в пользу другого. В-третьих, нужно точно знать, что должно сохранятся и как, а что не должно вообще. Вот, в принципе и всё.
Реализация Undo/Redo модели для сложного документа
Привет Хабр! В данной статье я хочу показать, как можно организовать модель редактирование документа со сложной структурой с возможностью отмены/возврата действий.
Предыстория и проблематика
Все началось с того, что я писал узкоспециализированный outline-софт, где основная идея заключается в оперировании кучей виртуальных бумажных карточек на разных сценах в разных редакторах.
Получилось похоже на MS Visio с определенной степенью кастомизации и плагинизации. Никаких технических сложностей здесь нету, однако есть ряд особенностей.
Во-первых, сцен несколько. А значит и оконных редакторов нужно несколько, каждый из которых работает по своим правилам.
Во-вторых, т.к. набор карточек один, а одна и та же карточка может быть использована в разных местах, то это рождает определенные зависимости между разными частями документа. И, если карточка удаляется, то это влечет за собой устранение этой карточки из всех мест, где она задействована.
В-третьих, когда я сделал все, что хотел, и показал результаты другу (который даже не программист), то он потыкал и сказал, что неплохо бы сделать Ctrl+Z. Я загорелся идеей, но вот реализовать это оказалось не такой тривиальной задачей. В этой статье я опишу, к чему пришел в итоге.
Существующие решения
Конечно, прежде чем делать что-то свое, я надеялся найти что-то готовое. Достаточно подробный анализ проблематики приводится в Undo и Redo — анализ и реализации. Однако, как оказалось, кроме общих принципов и слов найти что-то типа библиотеки сложно.
Первое, и самое очевидное решение — это делать версию документа на каждое изменение. Конечно, это надежно, но занимает много места и лишних операций. Поэтому такой вариант был отброшен сразу же.
Более интересным кажется memento pattern. Здесь уже можно немного сэкономить ресурсы за счет использования состояния документа, а не самого документа. Но это опять же, зависит от конкретной ситуации. А т.к. писал я все на C++, то здесь я бы не получил никакого выигрыша. При этом, даже существует C++ template проект undoredo-cpp, реализующий данный паттерн.
Command patter в принципе то что нужно, но, к сожалению, можно найти только принципы, но не универсальные реализации. Поэтому он и был взят за основу. И, конечно же, хотелось достичь максимальной производительности, из чего вытекала минимизация хранения данных.
Таким образом, стало примерно понятно, как и что хочется получить на уровне реализации. И получилось выделить конкретные цели:
Также следует отметить, что все писалось на QT5/C++11.
Модель документа
Основной сущность, над которой совершаются действия — это документ. К документу могут применяться различные атомарные действия, назовем их примитивами. Атомарность предполагает, что до и после применения примитива документ находится в консистентном состоянии.
В моем документе я выделил следующие сущности (следует отметить, что мой софт предназначался для наброски плана сценария, отсюда и специфика): карточка, персонаж, сюжетная карточка (ссылается на карточку), карточка персонажа (ссылается на карточку), точка сюжетной линии (ссылается на карточку), сюжетная линия (содержит цепь сюжетных карточек) и др. Таким образом, сущности могут ссылаться друг на друга, и это может стать источником проблем в дальнейшем, если мы захотим вернуть действие по созданию сюжетной карточки, которая ссылается на карточку, создание которой мы уже откатили. Т.е. напрашивается некий механизм управления ссылками, но о нем позже.
При выделении примитивов получается примерно следующий набор: создать карточку, поменять текст карточки, удалить карточку, создать сюжетную карточку, создать сюжетную линию, поменять текст сюжетной линии, добавить карточку в сюжетную линию и др. Концептуально любой примитив явно относится по смыслу к какой-то сущности, значит есть смысл ввести типизацию примитивов по адресованной сущности (карточка, сюжетная линия, персонаж и т.д.).
Следует обратить внимание на атрибут dependencies — это как раз зависимости, на которые примитив ссылается, но его назначение будет рассмотрено чуть позже. Также, примитивы можно классифицировать по типу: создание; модификация; удаление.
При этом, модифицирующие примитивы могут порождать целое дерево, в зависимости от допустимых модификаций — например подвинуть карточку, добавить карточку в сюжетную линию и др.
Примитив может быть применен либо в прямом направлении, либо в обратном. Более того, для удаляющих примитивов и для assert-ов полезно хранить, в каком состоянии примитив — примененном или откатанном.
Далее, рассмотрим реализацию простейшего примитива — добавления карточки.
Реализация простейшего примитива
Примерно вот так выглядит реализация примитива создания карточки. Я не буду приводить очевидные рутинные операции, такие как инициализация pDoc и др.
В код специально добавлены несколько assert-ов, которые подтверждают консистентное состояние документа до и после применения примитива.
Ссылочная целостность
Теперь рассмотрим примитив создание сюжетной карточки. Фактически, это та же карточка, но находящаяся на сюжетном листе и имеющая координату. Т.е. она ссылается на сюжетную карточку и содержит дополнительные атрибуты (координаты).
Таким образом, предположим у нас есть последовательность примитивов — создать карточку, создать сюжетную карточку на ее основе. Тогда 2й примитив надо сослать на первый, при этом обеспечив возможность обновления ссылки, в случае если он будет отменен и восстановлен (с попутным удалением/пересозданием самой карточки).
Для этого и вводится специальная сущность referenced_entity, которую вы уже встречали раньше в списке зависимостей.
Здесь важным моментом является помещение себя в список зависимостей примитива. Таким образом, если на содержимое referenced_entity уже кто-то ссылается, то можно восстановить связь в момент помещения примитива в буфер, и потом на основе этой связи получать указатель на текущий адрес объекта с помощью метода get().
Обработка примитивов
Для обработки примитива вводится специальная сущность — command_buffer. В ее задачи входит:
В data хранятся примитивы в последовательности их создания пользователем. А в front — так называемый фронт ссылочных объектов. Когда новый примитив попадает в буфер, то он попадает в последний элемент цепи объекта, который хранится в baseEntity. И затем происходит проставление ссылок.
Все остальные методы буфера достаточно тривиальны, и они также содержат undo() и redo(). Таким образом, command_buffer обеспечивает консистентное состояние документа, и остается вопрос, как же поддерживать в корректном состоянии представления, формируемые соответствующими редакторами.
Модель взаимодействия
Для этого необходимо ввести новую сущность — событие, и каждый открытый редактор должен правильно реагировать на соответствующий тип событий. Событие связано с применением примитива — до применения, после применения, до отката, после отката. Например, после применения можно делать реакцию на примитивы создания (т.к. до применения объекта еще нету), перед откатом — на те же примитивы создания, т.к. после отката ссылка будет потеряна.
Вот такие события будут рассылаться после каждой из 4х операций над примитивом. Соответственно, в каждом редакторе нужно сделать обработчик, который на эти события будет реагировать, и, соответствнно, миниально перестраивать сцену.
Здесь нужно делать трехэтажный switch..case по сущности, операции и событию, и смотрится это ужасно. Для этого воспользуемся хитростью, основываясь на том, что каждый из элементов можно преобразовать к целому числу, и введем такой макрос.
Тогда тело данного метода примет вот такой вид, и его можно будет дописывать по мере появления новых примитивов без ущерба для удобства восприятия.
Правда стоит отметить, что если иерархия типов модифицирующего примитива для какой-то сущности разрастается, то внутри придется делать новые ветвления.
И это действительно работает
Описанный метод не ограничен моей моделью документа, и может быть использован в различных моделях документах. Если кому-то интересно посмотреть это в действии, то само скомпиленное приложение можно скачать на странице ultra_outliner.
Заключение
В рамках предложенного метода остался непроработанным один немаловажный вопрос. Большинство действий пользователя над документами действительно являются атомарными, однако часть из них производят сразу несколько примитивов. Например, если пользователь двигает карточку — это один примитив. А если он удаляет карточку, которая находится в 3х путях — то это 3 примитива по исключению карточки из цепи, исключение карточки с поля, и потом удаление самой карточки. Если такую цепь откатить, то за одно действие отката будет откачен только один примитив, в то время как логичным было бы откатить сразу все. Это требует определенной доработки метода, однако рассмотрим данную проблему в следующей статье.
Реализация функциональности многоуровневого undo/redo на примере прототипа электронной таблицы
Введение
Кнопки «Undo» и «Redo», позволяющие отменить и вернуть обратно любые пользовательские действия, а также посмотреть в списке перечень всех выполненных действий, являются стандартом де-факто для таких приложений, как текстовые процессоры и среды разработки, редакторы графики и САПР, системы редактирования и монтажа звука и видео. Они настолько привычны для пользователя, что последний воспринимает их наличие как данность, всего лишь одну функциональную возможность наряду с десятками других. Но с точки зрения разработчика требование к наличию undo является одним из факторов, влияющих на всю архитектуру проекта, определяемую на самых ранних стадиях проекта разработки.
В открытых источниках существует довольно мало информации о том, как практически реализовывать функциональность undo/redo. Классическая книга Э. Гаммы и др. «Приёмы объектно-ориентированного программирования. Паттерны проектирования» коротко упоминает о пригодности для этой цели паттерна «команда», в интернете на эту тему много общей информации, но нам не удалось найти достаточно полного, проработанного примера реализации. В нашей статье мы попытаемся восполнить этот пробел и, основываясь на опыте автора, продемонстрировать подробный пример архитектуры приложения, поддерживающей undo/redo, который может быть взят за основу других проектов.
Примеры кода в статье даны на языке Java, однако в них нет ничего Java-специфичного и все изложенные здесь идеи подходят для любого объектно-ориентированного языка (сам автор впервые реализовал их на Delphi).
Следует отметить, что для различных нужд и типов приложений существуют различные «модели undo»: линейные — с отменой операций строго в обратной последовательности, и нелинейные — с отменой произвольных операций из истории произведённых действий. Мы будем вести речь о реализации линейного Undo в системе с синхронизированными модификациями модели данных, т. е. такой, в которой не допускается одновременная модификация внутреннего состояния модели данных в разных потоках выполнения. Классификация возможных моделей undo приводится, например, в статье в Википедии.
Мы, естественно, предполагаем, что в приложении реализовано отделение модели данных (Model) от представления (View), и функциональность undo реализуется на уровне модели данных, в виде методов undo() и redo() одного из её классов.
Иллюстрирующий пример
В качестве иллюстрирующего примера в статье рассматривается модель данных приложения, прототипирующего электронную таблицу (в стиле MS Excel/ LibreOffice Calc). Имеется лист (для простоты — только один), состоящий из ячеек, значения и размеры которых можно изменять, строки и столбцы — менять местами, и все эти действия, соответственно, являются отменяемыми. Исходные коды и соответствующие модульные тесты доступны по адресу https://github.com/inponomarev/undoredo и могут быть скомпилированы и выполнены при помощи Maven.
Основными сущностями в нашем примере являются:
Решением является использование словарей на базе деревьев и хэш-таблиц для хранения одних лишь только изменённых значений, подставляя вместо отсутствующего в словаре значения некоторое значение по умолчанию.
Для хранения экземпляров Row и Column, используются словари TreeMap rows и TreeMap columns в классе Worksheet. Для хранения экземпляров Cell используется словарь HashMap cells в классе Row. Значениями этой хэш-таблицы являются ссылки на объекты Cell, а ключами — объекты-столбцы. Такой подход к хранению данных позволяет найти оптимальный баланс между быстродействием и объёмом используемой памяти для всех практически необходимых операций над содержимым Worksheet.
Корневой класс модели и отменяемые методы
Класс Worksheet в нашем примере является центральным: 1) работа со всеми другими объектами бизнес-логики начинается с получения экземпляра именно этого класса, 2) экземпляры других классов могут работать только в контексте объекта Worksheet, 3)через метод save(. ) и статический метод load(. ) он сохраняет в поток и восстанавливает из потока состояние всей системы. Этот класс мы назовём корневым классом модели. Как правило, при разработке приложений в архитектуре Model-View-Controller не возникает затруднений с определением того, что является корневым классом модели. Именно он и снабжается методами, специфичными для функциональности Undo/Redo.
Также не должно вызвать затруднений определение методов, изменяющих состояние модели. Это те методы, результат вызова которых необходимо отменять по undo. В нашем примере — следующие:
Undo- и Redo-стеки
В линейной модели Undo отмена операций производится таким образом, чтобы сохранять последовательность производимых над документом действий. Например, если в документ сначала был добавлен столбец, а затем изменена его ширина, то отмена этих операций возможна только в обратном порядке, а возврат — в прямом. Поэтому для хранения операций, подлежащих отмене и восстановлению, естественно использовать два стека на связных списках (linked lists), являющихся частью корневого класса модели. При вызове метода, изменяющего состояние модели, стек Redo сбрасывается, а стек Undo пополняется очередным значением. Выполнение команды Undo должно приводить к извлечению значения из стека Undo и переносу его в стек Redo. Выполнение команды Redo, если таковое случится, должно вновь возвращать значение в стек Undo (см. рис.).
Cодержимым этих стеков являются объекты-наследники класса Command, о котором речь пойдёт далее. Вот перечень публичных методов корневого класса бизнес-логики, дающих доступ к функциональности Undo/Redo:
Паттерн «команда»
Методы, изменяющие состояние модели, могут иметь разные параметры и вообще быть определены в разных классах модели. Полностью инкапсулировать информацию о параметрах и целевом объекте метода, «причесать всех под одну гребёнку», позволяет паттерн проектирования «команда». Нетривиальность этого паттерна заключается в том, что обычно классами в объектно-ориентированном коде описываются некоторые сущности. Здесь же класс описывает не сущность, а действие, производимое меняющим состояние модели методом, «отняв» эту прерогативу у самого метода.
Класс каждой из команд наследуется от базового абстрактного класса Command. Сам по себе Command имеет всего три абстрактных метода: execute, undo и getDescription, не имеющих (что важно!) никаких параметров. Это позволяет выполнять и отменять команды методами undo() и redo() корневого класса, «ничего не знающими» о тех операциях, которые выполняются или отменяются. Метод getDescription() должен возвращать текстовое описание действия: именно это описание будет доступно пользователю в списке отменяемых действий.
Наследники класса Command, помимо реализации его абстрактных методов, могут содержать сколько угодно дополнительных полей, содержащих информацию о параметрах запуска команды и информацию, необходимую для отмены уже выполненной команды и показа текстового описания выполненной команды. При этом метод execute() должен содержать код, который обычно содержится в методе, меняющем состояние модели, только вместо параметров метода этот код должен использовать поля класса команды. Отметим, что команда оперирует внутренним состоянием объекта модели так же, как раньше это делал его собственный метод. Поэтому команда должна иметь доступ к скрытым (private) полям объекта модели. В языке Java этого удобно добиться, если сделать класс-наследник Command вложенным в соответствующий класс модели. В нашем приложении, например, команда SetSize вложена в класс модели AxisElement, остальные команды вложены в Worksheet.
Метод undo(), в свою очередь, должен уметь отменять последствия вызова метода еxecute(). Вся необходимая для этого информация должна храниться в полях класса команды. Дело упрощается, если понимать, что на момент вызова метода undo() состояние объектов бизнес-логики будет всегда тождественно тому, каким оно было сразу же после выполнения соответствующего метода execute(). Если с тех пор пользователь выполнял другие операции, то, прежде чем он доберётся до undo() текущей команды, он должен будет выполнить undo() для всех команд, которые вызывались после неё. На практике понимание этого принципа сильно облегчает написание метода undo() и сокращает количество сохраняемой в команде информации.
Рассмотрим реализацию команды, устанавливающей значение ячейки:
Как видим, в классе имеются переменные для сохранения адреса ячейки и её значения. Причём в целях экономии памяти можно обойтись лишь одной переменной для сохранения значения: нового, если метод execute() ещё не выполнен, или старого, если метод execute() уже выполнен. Т. е. здесь как раз используется тот факт, что методы execute() и undo() выполняются поочерёдно. Метод getDescription() может использовать переменные класса для того, чтобы описание команды было более подробным.
Шаблон отменяемого метода
Как команды используются в отменяемых методах? Если обычно такие методы с учётом своих параметров просто выполняют какие-то действия над моделью, то в системе с undo все они строго должны производить следующие три операции:
Примерно так же выглядят все другие отменяемые методы.
Метод execute(Command cmd) корневого класса выполняет действие команды, сброс стека redo и укладывание команды в стек undo:
С этого момента команда становится частью цепочки отменяемых/повторяемых действий. Как было сказано выше, вызов метода undo() в корневом классе вызывает метод undo() команды, находящейся на вершине стека Undo, и переносит её в стек Redo. Вызов метода redo() корневого класса, в свою очередь, выполняет метод execute() команды, находящейся на вершине Redo-стека, и переносит её в стек Undo.
Повторное использование классов команд
Итак, для задач, которые в обычном случае требуют написания одного метода, в системах с undo требуется создавать целый класс, что приводит к справедливым опасениям относительно объёма кода и трудоёмкости его поддержки: в реальных проектах количество отменяемых методов исчисляется десятками.
На самом деле, классов-команд может быть существенно меньше за счёт их универсализации и использования одного класса-команды для нескольких отменяемых методов. К примеру, основной код класса SetCellValue, по сути, может быть использован для любых методов, в которых требуется поменять одно значение какой-либо переменной. Сделать класс команды более универсальным можно как путём добавления дополнительных полей, так и за счёт параметризации класса.
Для примера рассмотрим универсальную команду удаления, которая используется для удаления как строк, так и столбцов таблицы:
Её использование в методах deleteColumn и deleteRow выглядит следующим образом:
Макрокоманды
Иногда может оказаться, что вызов метода, меняющего состояние — слишком мелкая единица для хранения в стеке Undo. Рассмотрим процедуру insertValues(int top, int left, String[][] value) вставки значений из двумерного списка (например, из буфера обмена) в документ. Эта процедура в цикле одну за другой обновляет ячейки документа значениями ячеек из буфера. Таким образом, если мы вставляем кусок таблицы размером 4×4, то, с точки зрения механизма Undo, мы производим 16 изменений ячеек документа. Это означает, что если пользователь захочет отменить результат вставки, то 16 раз придётся нажать на кнопку Undo, при этом в таблице одна за другой 16 ячеек будут восстанавливать свои прежние значения.
Разумеется, это неправильно: результаты операций, подобных данной, должны отменяться и восстанавливаться как единое целое, и в списке отменяемых операций отображаться одной строкой. Для того, чтобы это стало возможно, применяются макрокоманды.
Идея реализации макрокоманды проста: это всего лишь специальный наследник класса Command, содержащий внутри себя цепочку других команд, как показано на рис.:
Метод execute() класса MacroCommand пробегает по собственному списку команд и выполняет их методы execute(). При вызове метода undo() той же макрокоманды, он пробегает по тому же списку команд уже в обратном порядке и вызывает их методы undo().
Макро-методы, подобные методу вставки из буфера обмена, в приложениях, построенных в архитектуре Model/View/Controller, как правило, не являются частью модели, а реализуются на уровне контроллера. Зачастую они представляют собой лишь автоматизацию некоторой рутинной работы, необходимость в которой в зависимости от вида пользовательского интерфейса может существовать, а может и отсутствовать. Кроме того, часто возникает необходимость в группировке нескольких пользовательских действий в одно: например, текстовые редакторы группируют в одно макро-действие ввод пользователем слов и предложений, вместо того, чтобы засорять undo-стек записями о вводе каждой отдельной буквы.
Поэтому поддержка макрокоманд может и должна быть реализована на абстрактном уровне, независимым от приложения образом. Это делается с помощью добавления в корневой класс модели публичных методов beginMacro(String description) и endMacro(). Методы вызываются перед началом и после завершения макро-действий. Вызывая beginMacro(. ) со строковым параметром, значение которого затем окажется доступным пользователю в списке отменяемых операций, мы порождаем объект типа MacroCommand и на время подменяем Undo-стек внутренним стеком макрокоманды. Таким образом, после вызова beginMacro всякая последующая передача команды в метод execute(. ) корневого класса приводит к её записи не непосредственно в Undo-стек, а во внутренний стек текущей макрокоманды (которая уже, в свою очередь, записана в Undo-стек). Вызов endMacro() возвращает всё на свои места. Допускается также многоуровневое вложение макрокоманд друг в друга.
Отслеживание наличия несохранённых изменений
Наличие функциональности undo предоставляет надёжный способ отслеживания несохранённых изменений в документе. Это необходимо для реализации корректного поведения кнопки «Сохранить» в приложении:
Заключение
Мы рассмотрели основные принципы реализации линейного многоуровневого Undo/Redo на примере, который, на наш взгляд, достаточно универсален, чтобы служить шаблоном для других проектов.
Неудивительно, что функциональность undo и redo предъявляет достаточно серьёзные требования к архитектуре приложения и профессионализму разработчиков. Но такие вещи, как строгое следование архитектуре Model/View/Controller и хорошо продуманная модель (написание каждого из методов, меняющих состояние модели, в системе с undo «обходится дороже»), несмотря на некоторую трудоёмкость, окупаются высоким качеством и надёжностью создаваемой программы, что в конечном итоге обернётся удовлетворённостью её пользователей.