Реалізація функціональності багаторівневого undo/redo на прикладі прототипу електронної таблиці

Введення

Кнопки «Скасувати» і «Redo», що дозволяють скасувати і повернути назад будь користувальницькі дії, а також подивитися в списку перелік всіх виконаних дій, є стандартом де-факто для таких додатків, як текстові процесори і середовища розробки, редактори графіки і САПР, системи редагування і монтажу відео і звуку. Вони настільки звичні для користувача, що останній сприймає їх наявність як даність, лише одну функціональну можливість поряд з десятками інших. Але з точки зору розробника вимога до наявності undo є одним з факторів, що впливають на всю архітектуру проекту, яка визначається на ранніх стадіях розробки проекту.

Функції undo в додатках LibreOffice і GIMP

У відкритих джерелах існує досить мало інформації про те, як практично реалізовувати функціональність undo/redo. Класична книга Е. Гами та ін «Прийоми об'єктно-орієнтованого програмування. Патерни проектування» коротко згадує про придатність для цієї мети патерну «команда», в інтернеті на цю тему багато загальної інформації, але нам не вдалося знайти достатньо повного, опрацьованого приклад реалізації. У нашій статті ми спробуємо заповнити цю прогалину і, грунтуючись на досвіді автора, продемонструвати докладний приклад архітектури програми, що підтримує undo/redo, який може бути взятий за основу інших проектів.

Приклади коду в статті подано на мові Java, однак у них немає нічого Java-специфічного і всі викладені тут ідеї підходять для будь-якого об'єктно-орієнтованої мови (сам автор вперше реалізував їх на Delphi).

Слід зазначити, що для різних потреб і типів додатків існують різні «моделі undo»: лінійні — з відміною операцій строго в зворотній послідовності, і нелінійні — з відміною довільних операцій з історії вироблених дій. Ми будемо вести мову про реалізації лінійного Undo в системі синхронізованими з модифікаціями моделі даних, тобто такої, в якій не допускається одночасна модифікація внутрішнього стану моделі даних в різних потоках виконання. Класифікація можливих моделей undo наводиться, наприклад, в статті у Вікіпедії.

Ми, природно, припускаємо, що в додатку реалізовано відділення моделі даних (Model) від уявлення (View), і функціональність undo реалізується на рівні моделі даних, у вигляді методів undo() та redo() одного з класів.

Ілюструє приклад

Як ілюструє приклад у статті розглядається модель даних програми, прототипирующего електронну таблицю (в стилі MS Excel/ LibreOffice Calc). Є лист (для простоти — тільки один), що складається з клітинок, значення і розміри яких можна змінювати, рядки та стовпці — міняти місцями, і всі ці дії, відповідно, є отменяемыми. Вихідні коди і відповідні модульні тести доступні за адресою http://inponomarev.ru/programming/undoredo.zip і можуть бути скомпільовані і виконані за допомогою Maven.

Основними сутностями в нашому прикладі є:

  1. робочий аркуш — клас Worksheet,
  2. рядки і стовпці — класи Row та Column (спадкоємці класу AxisElement),
  3. осередку — клас Cell.
Що виходить в результаті нескладна модель даних представлена на діаграмі класів на малюнку нижче:

Класи моделі даних для ілюструє приклад

Не вдаючись у подробиці реалізації електронних таблиць, коротко відзначимо основні принципи пристрою вихідного коду. Хоча для користувача аркуш електронної таблиці представляється як двовимірний масив даних, кордони якої сягають далеко за межі екрана, використання двовимірного масиву для моделі даних не виправдано ні з точки зору витрат оперативної пам'яті, ні з точки зору швидкодії типових операцій. Приміром, якщо в ранніх версіях MS Excel допускалося існування стовпців і 65536 рядків, то виділення пам'яті під 655362, тобто 4 млрд. осередків, було б просто технічно неможливо в 32-бітної системі.

Рішенням є використання словників на базі дерев і хеш-таблиць для зберігання одних лише тільки змінених значень, підставляючи замість відсутнього в словнику значення деяке значення за замовчуванням.

Для зберігання примірників Row та Column, використовуються словники TreeMap<Integer, Row> rows та TreeMap<Integer, Column> columns в класі Worksheet. Для зберігання примірників Cell використовується словник HashMap<Column, Cell> cells в класі Row. Значеннями цієї хеш-таблиці є посилання на об'єкти Cell, а ключами — об'єкти-стовпці. Такий підхід до зберігання даних дозволяє знайти оптимальний баланс між швидкодією та обсягом пам'яті, що використовується для практично всіх необхідних операцій над вмістом Worksheet.

Кореневої клас моделі і скасовуються методи

Клас Worksheet у нашому прикладі є центральним: 1) робота з усіма іншими об'єктами бізнес-логіки починається з отримання примірника саме цього класу, 2) примірники інших класів можуть працювати тільки в контексті об'єкта Worksheet, 3)через метод save(...) і статичний метод load(...) він зберігає в потік і відновлює з потоку стан всієї системи. Цей клас ми назвемо кореневим класом моделі. Як правило, при розробці додатків в архітектурі Model-View-Controller не виникає труднощів з визначенням того, що є кореневим класом моделі. Саме він і забезпечується методами, специфічними для функціональності Undo/Redo.

Також не повинно викликати труднощів визначення методів, що змінюють стан моделі. Це ті методи, результат виклику яких необхідно скасовувати по undo. У нашому прикладі — наступні:

  • setCellValue(int row, int col, String value) — встановлює значення клітинки (для простоти прикладу ми вважаємо, що осередки можуть приймати тільки рядкові значення!),
  • insertValues(int top, int left, String[][] value) — вставляє в комірки значення двовимірного масиву (наприклад, отриманого з буфера обміну),
  • setRowHeight(int row, int height), setColWidth(int col, int width) — задають висоту рядків і ширину стовпців,
  • insertColumnLeft(int colNum), insertRowAbove(int rowNum) — вставляють стовпці і рядки,
  • deleteColumn(int colNum), deleteRow(int rowNum) — видаляють стовпці і рядки,
  • moveColumn(int from, int to), moveRow(int from, int to) переміщують стовпці і рядки разом з вмістом з заміною вмісту кінцевого стовпця / рядка.
В реальному додатку, звичайно, їх може бути набагато більше. Кожному з них потрібно зіставити відповідний клас команди (про що йтиметься далі), а методи необхідно переписати особливим чином.

Undo і Redo-стеки

У лінійній моделі Undo скасування операцій проводиться таким чином, щоб зберігати послідовність вироблених над документом дій. Наприклад, якщо документ спочатку був доданий стовпець, а потім змінена його ширина, то скасування цих операцій можлива тільки в зворотному порядку, а повернення — у прямому. Тому для зберігання операцій, що підлягають скасування та відновлення, природно використовувати два стека на зв'язних списків (linked lists), які є частиною базового класу моделі. При виклику методу, що змінює стан моделі, стек Redo скидається, а стек Undo поповнюється черговим значенням. Виконання команди Undo повинно призводити до отримання значення зі стека Undo і перенесення його в стек Redo. Виконання команди Redo, якщо таке трапиться, має знову повертати значення в стек Undo (див. рис.).

Undo і Redo стеки

Вмістом цих стеків є об'єкти-спадкоємці класу Command, про який мова піде далі. Ось перелік публічних методів базового класу бізнес-логіки, які дають доступ до функціональності Undo/Redo:

  • undo() — відміна дії, виробленого викликом будь-якого методу, що змінює стан моделі, і перекладання його в стек Redo:

    Command cmd = undoStack.pop();
    cmd.undo();
    redoStack.push(cmd);
    

    Кожен повторний виклик відкочує зміни по ланцюжку до тих пір, поки не вичерпається стек Undo, після вичерпання стека повторний виклик методу нічого не виробляє.
  • redo() — повернення дії, скасованого викликом undo, і перекладання його назад в стек undo. Повторний виклик накочує скасовані за Undo операції до тих пір, поки не вичерпається стек Redo, після чого виклик redo() ігнорується. Весь стек Redo скидається після виклику будь-якого методу, що змінює стан моделі.
  • getUndoStack(), getRedoStack() — повертають стеки цілком для того, щоб можна було сформувати список операцій, доступних до скасування або повтору.
  • isUndoActive(), setUndoActive(boolean value) — дозволяє вимкнути механізм Undo (за замовчуванням активоване). Необхідно для 1) підвищення швидкодії і зниження витрати пам'яті при проведенні дуже великих змін у стані документа 2) роботи з документом із зовнішніх додатків через інтерфейси, в яких функціональність Undo/Redo недоступна.

Патерн «команда»

Методи, що змінюють стан моделі, можуть мати різні параметри і взагалі бути визначені в різних класах моделі. Повністю инкапсулировать інформацію про параметри і цільовому об'єкті методу, «причесати всіх під одну гребінку», дозволяє шаблон проектування «команда». Нетривіальність цього патерну полягає в тому, що зазвичай класами в об'єктно-орієнтованому коді описуються деякі сутності. Тут же клас описує не сутність, а дія, вироблене змінюють стан моделі методом, «відібравши» цю прерогативу у самого методу.

Клас кожної з команд успадковується від базового абстрактного класу Command. Сам по собі Command має всього три абстрактних методу: execute, undo та getDescription, не мають (що важливо!) ніяких параметрів. Це дозволяє виконувати і скасовувати команди методами undo() та redo() кореневого класу, «нічого не знають» про тих операціях, які виконуються або скасовуються. Метод getDescription() повинен повертати текстовий опис дії: саме це опис буде доступно користувачеві у списку скасувань.

Клас Command та його спадкоємці

Спадкоємці класу Command, крім реалізації його абстрактних методів, можуть містити скільки завгодно додаткових полів, що містять інформацію про параметрах запуску команди та інформацію, необхідну для скасування вже виконаної команди і показу текстового опису виконаної команди. При цьому метод execute() " повинен містити код, який зазвичай міститься в методі, змінює стан моделі, тільки замість параметрів методу цей код повинен використовувати поля класу команди. Відзначимо, що команда оперує внутрішнім станом об'єкта моделі так само, як раніше це робив його власний метод. Тому команда повинна мати доступ до прихованих (private) полів об'єкта моделі. В мові Java цього зручно домогтися, якщо зробити клас-спадкоємець Command вкладеним у відповідний клас моделі. У нашому додатку, наприклад, команда SetSize вкладена в клас моделі AxisElement, інші команди вкладені у Worksheet.

Метод undo(), в свою чергу, повинен вміти скасовувати наслідки виклику методу еxecute(). Вся необхідна для цього інформація повинна зберігатися в полях класу команди. Справа спрощується, якщо розуміти, що на момент виклику методу undo() стан об'єктів бізнес-логіки буде завжди тотожне того, яким воно було відразу ж після виконання відповідного методу execute(). Якщо з тих пір користувач виконував інші операції, то, перш ніж він добереться до undo() поточної команди, він повинен буде виконати undo() для всіх команд, які викликалися після неї. На практиці розуміння цього принципу сильно полегшує написання методу undo() і скорочує кількість зберігається в команді інформації.

Розглянемо реалізацію команди, що встановлює значення комірки:

final class SetCellValue extends Command {
private final int row;
private final int col;
private String val;

public SetCellValue(int row, int col, String newValue) {
this.row = row;
this.col = col;
this.val = newValue;
}

@Override
public String getDescription() {
return ("Введення даних");
}

private void changeVal() {
String oldValue = getCellValue(row, col);
Row r = rows.get(row);
Column c = columns.get(col);
/ / .... отримання об'єкта cell за row і col...
cell.setValue(val);
//....
val = oldValue;
}

@Override
public void execute() {
changeVal();
}

@Override
public void undo() {
changeVal();
}
}

Як бачимо, в класі є змінні для збереження адреси комірки і її значення. Причому у цілях економії пам'яті можна обійтися лише однієї змінної для збереження значення: нового, якщо метод execute() ще не виконаний, або старого, якщо метод execute() вже виконаний. Тобто тут використовується той факт, що методи execute() та undo() виконуються по черзі. Метод getDescription() може використовувати змінні класу для того, щоб опис команди було більш докладним.

Шаблон отменяемого методу

Як команди використовуються в отменяемых методи? Якщо зазвичай такі методи з урахуванням своїх параметрів просто виконують якісь дії над моделлю, то в системі з undo всі вони строго повинні виконувати наступні три операції:

  1. створити примірник відповідної команди (класу-спадкоємця Command),
  2. ініціалізувати поля команди параметрами методу і, можливо, додатковою інформацією,
  3. виконати метод execute(Command cmd) кореневого об'єкта, передавши в якості параметра тільки що створену і инициализированную команду.
У нашому прикладі виглядає реалізація методу setCellValue виглядає так:

public void setCellValue(int row, int col, String value) {
Command cmd = new SetCellValue(row, col, value);
execute(cmd);
}

Приблизно так само виглядають всі інші скасовуються методи.

Метод execute(Command cmd) кореневого класу виконує дію команди, скидання стека redo укладання команди в стек undo:

undoStack.push(cmd);
redoStack.clear();
cmd.execute();

З цього моменту команда стає частиною ланцюжка отменяемых/повторюваних дій. Як було сказано вище, виклик методу undo() в кореневому класі викликає метод undo() команди, що знаходиться на вершині стека Undo, і переносить її в стек Redo. Виклик методу redo() кореневого класу, в свою чергу, виконує метод execute() команди, що знаходиться на вершині Redo-стека, і переносить її в стек Undo.

Повторне використання класів команд
Отже, для завдань, які в звичайному випадку вимагають написання одного методу, в системах з undo потрібно створювати цілий клас, що призводить до справедливих побоювань щодо обсягу коду і трудомісткості його підтримки: у реальних проектах кількість отменяемых методів обчислюється десятками.

Насправді, класів-команд може бути істотно менше за рахунок їх універсалізації та використання одного класу-команди для декількох отменяемых методів. Приміром, основний код класу SetCellValue, по суті, може бути використаний для будь-яких методів, у яких потрібно поміняти одне значення будь-якої змінної. Зробити клас команди більш універсальним можна як шляхом додавання додаткових полів, так і за рахунок параметризації класу.

Для прикладу розглянемо універсальну команду видалення, яка використовується для видалення як рядків, так і стовпців таблиці:

final class Delete<T extends AxisElement> extends Command {
private final int num;
private final T deleted;
private final TreeMap<Integer, T> map;

Delete(TreeMap<Integer, T> map, int num) {
this.num = num;
this.map = map;
deleted = map.get(num);
}

@Override
public String getDescription() {
return String.format("Видалення %s %d", map == columns ? "стовпця" : "рядки", num);
}

@Override
public void execute() {
internalDelete(map, num);
}

@Override
public void undo() {
internalInsert(map, num);
map.put(num, deleted);
}
}

private static <T extends AxisElement> void 
internalDelete(TreeMap<Integer, T> map, int num) {
//...
//видалення зі словника запис з ключем num
//і зсув всіх записів з ключем > num на мінус одну позицію 
//...
}

private static <T extends AxisElement> void 
internalInsert(TreeMap<Integer, T> map, int num) {
//...
//зсув всіх записів з ключем >= num на плюс одну позицію 
//...
}

}

Її використання в методах deleteColumn та deleteRow виглядає наступним чином:

public void deleteColumn(int colNum) {
Command cmd = new Delete<Column>(columns, colNum);
execute(cmd);
}

public void deleteRow(int rowNum) {
Command cmd = new Delete<Row>(rows, rowNum);
execute(cmd);
}

Дії

Іноді може виявитися, що виклик методу, що змінює стан — занадто дрібна одиниця для зберігання в стеку Undo. Розглянемо процедуру insertValues(int top, int left, String[][] value) вставки значень з двовимірного списку (наприклад, з буфера обміну) документ. Ця процедура в циклі одну за одною оновлює комірки документа значеннями комірок з буфера. Таким чином, якщо ми вставляємо шматок таблиці розміром 4×4, то, з точки зору механізму Undo, ми проводимо 16 змін осередків документа. Це означає, що якщо користувач захоче скасувати результат вставки, 16 раз доведеться натиснути на кнопку Undo, при цьому в таблиці одна за одною 16 осередків будуть відновлювати свої колишні значення.

Зрозуміло, це неправильно: результати операцій, подібних до цієї, повинні скасовуватися і відновлюватися як єдине ціле, і в списку отменяемых операцій відображатися одним рядком. Для того, щоб це стало можливо, застосовуються дії.

Ідея реалізації дії проста: це всього лише спеціальний спадкоємець класу Command, що містить всередині себе ланцюжок інших команд, як показано на рис.:

Стек Undo з дією

Метод execute() класу MacroCommand пробігає за власним списком команд і виконує їх методи execute(). При виклику методу undo() тієї ж дії, він пробігає по тому ж списку команд вже в зворотному порядку, і викликає їх методи undo().

Макро-методи, подібні методом вставки з буфера обміну, в додатках, побудованих в архітектурі Model/View/Controller, як правило, не є частиною моделі, а реалізуються на рівні контролера. Найчастіше вони являють собою лише автоматизацію деякої рутинної роботи, необхідність в якій в залежності від виду інтерфейсу може існувати, а може бути відсутньою. Крім того, часто виникає необхідність у групуванні декількох користувальницьких дій в одне: наприклад, текстові редактори групують в одне макро-дія введення користувачем слів і пропозицій, замість того, щоб засмічувати undo-стек записами про введення кожної окремої літери.

Тому підтримка дій може і повинна бути реалізована на абстрактному рівні, незалежним від програми чином. Це робиться з допомогою додавання в кореневій клас моделі публічних методів beginMacro(String description) та endMacro(). Методи викликаються перед початком і після завершення макро-дій. Викликаючи beginMacro(...) з рядковим параметром, значення якого потім виявиться доступним користувачеві у списку отменяемых операцій, ми породжуємо об'єкт типу MacroCommand і на сплутуємо Undo-стек внутрішнім стеком дії. Таким чином, після виклику beginMacro всяка подальша передача команди метод execute(...) кореневого класу призводить до її запису не безпосередньо в Undo-стек, а у внутрішній стек поточної дії (яка вже, в свою чергу, записана в Undo-стек). Виклик endMacro() повертає все на свої місця. Допускається також багаторівневе вкладення дій один в одного.

Відстеження наявності незбережених змін

Наявність функціональності undo надає надійний спосіб відстеження незбережених змін в документі. Це необхідно для реалізації коректного поведінки кнопки «Зберегти» в додатку:

  1. кнопка «Зберегти» повинна бути активна тоді і тільки тоді, коли незбережені зміни присутні (в іншому випадку зберігатися нема чого: документ не змінювався),
  2. при закритті документа має сенс запитувати користувача про те, чи він хоче зберегти зміни, тільки у випадку, якщо незбережені зміни присутні.
У нашому прикладі наявність незбережених змін повертається методом isModified(). Реалізується він наступним чином: при кожному виклику методу save(...) поточна вершина стека Undo зберігається в змінну lastSavedPoint. При виклику методу isModified поточна вершина стека Undo порівнюється зі значенням lastSavedPoint: якщо вони рівні, то незбережені зміни відсутні. При деактивированном механізмі undo метод isModified() завжди повертає true.

Висновок

Ми розглянули основні принципи реалізації лінійного багаторівневого Undo/Redo на прикладі, який, на наш погляд, досить універсальний, щоб служити шаблоном для інших проектів.

Не дивно, що функціональність undo і redo пред'являє досить серйозні вимоги до архітектури програми та професіоналізму розробників. Але такі речі, як суворе дотримання архітектурі Model/View/Controller і добре продумана модель (написання кожного з методів, що змінюють стан моделі, в системі з undo «обходиться дорожче»), незважаючи на деяку трудомісткість, окупаються високою якістю і надійністю створюваної програми, що в кінцевому підсумку обернеться задоволеністю її користувачів.

* * *

Повні вихідні коди і відповідні модульні тести прикладу, розглянутого в розділі, доступні за адресою http://inponomarev.ru/programming/undoredo.zip і можуть бути скомпільовані і виконані за допомогою Maven.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.