Pull to refresh

Undo/Redo — Иллюзия простоты

Developer Soft corporate blog
Такая простая и привычная функция в любом текстовом и графическом редакторе. Казалось бы, какие могут быть сложности с её реализацией? Впервые столкнувшись с разработкой Undo/Redo для текстового редактора XtraRichEdit, мы задумались, а какой же подход нам избрать?



Было очевидно, что должен существовать некий объект, отвечающий за историю изменений. В этом объекте должен храниться список элементов, представляющих собой отдельные действия. Каждый такой элемент должен хранить достаточно информации чтобы откатить действие (Undo), а также повторить его (Redo).

Поскольку действия могут быть самыми разными (вставка текста, изменение шрифта, добавление красной строки в параграф), мы сразу решили, что элементы буфера Undo будут не только хранить все необходимые данные для отката/повтора операции, но и будут сами ответственны за выполнение отката и повтора:

public abstract class HistoryItem {
    public abstract void Undo(Document document);
    public abstract void Redo(Document document);
}

Первый прототип класса для буфера Undo выглядел следующим образом:

public class History {
    readonly List<HistoryItem> items = new List<HistoryItem>();

    public History(Document document) {
        this.document = document;
    }

    public void Undo() {
    }
    public void Redo() {
    }
    public void Add(HistoryItem item) {
        items.Add(item);
    }
}

Руки так и тянутся написать метод Undo:

public void Undo() {
    items[items.Count - 1].Undo(document);
}

Лаконично, изящно… но совершенно неправильно.

Для начала, при попытке вызвать метод Undo при пустом списке, вылетит исключение. Исправляем:

public bool CanUndo { get { return items.Count > 0; } }
public void Undo() {
    if (!CanUndo)
        return;
    items[items.Count - 1].Undo(document);
}

И вновь получаем неправильный код. Ведь если вызвать метод Undo несколько раз подряд, то будет раз за разом вызываться Undo для последнего элемента в списке, что неправильно. Вносим изменения:

public void Undo() {
    if (!CanUndo)
        return;
    items[items.Count - 1].Undo(document);
    items.RemoveAt(items.Count - 1);
}

Вот теперь всё хорошо. Что-ж, пора приниматься за Redo. Ничего сложного…

public void Redo() {
    if (!CanRedo)
        return;
    // ???
}

Oops! Приехали.
В нашей реализации Undo мы в процессе отката безвозвратно теряем откатанные элементы, поэтому делать Redo просто некому. Придется завести индекс, указывающий на текущий элемент в буфере обмена. Итак:

int currentIndex = -1;
public bool CanUndo { get { return currentIndex >= 0; } }
public bool CanRedo { get { return items.Count > 0 && currentIndex < items.Count - 1; } }

public void Undo() {
    if (!CanUndo)
        return;
    items[currentIndex].Undo(document);
    this.currentIndex--;
}

public void Redo() {
    if (!CanRedo)
        return;
    this.currentIndex++;
    items[currentIndex].Redo(document);
}

public void Add(HistoryItem item) {
    items.Add(item);
    this.currentIndex++;
}

Уже лучше, по крайней мере похоже на что-то работоспособное. Обратите внимание, что в случае Undo индекс изменяется после отката, а в случае Redo — до наката. Мы также не забыли инкрементировать индекс при добавлении элемента в историю.

А теперь давайте посмотрим внимательно на метод Add и зададимся вопросом, как он будет себя вести в случае, если мы выполнили и записали в историю 5 действий, затем откатили 3 из них и собираемся выполнить новое действие? Поразмыслив и посмотрев как сделано у других (всё уже украдено до нас) приходим к выводу, что в таком случае та часть истории действий, что находится после текущего индекса, должна быть потеряна, а вместо неё начнут записываться новые действия:

public void Add(HistoryItem item) {
    CutOffHistory();
    items.Add(item);
    this.currentIndex++;
}

void CutOffHistory() {
    int index = currentIndex + 1;
    if (index < Count)
        items.RemoveRange(index, Count - index);
}

Вот теперь, наконец, простейшая реализация Undo/Redo стала работоспособной.

Задумаемся, как мы будем её использовать. Первым делом в голову лезет такая последовательность действий:
  1. Выполняем действие;
  2. Заносим информацию об этом действии в буфер undo для дальнейшего отката/повтора.

Но ведь еще в самом начале мы решили, что элементы undo-буфера способны не только хранить необходимые данные, но и самостоятельно выполнять нужные операции по откату/повтору. А что такое повтор операции? Это и есть её прямое выполнение из текущего состояния. Т.е. чтобы выполнить любую операцию, можно делать так:
  1. Создаем элемент буфера undo, и заносим его в буфер undo для дальнейшего отката/повтора;
  2. Выполняем Redo для этого элемента:

void DoAction() {
    HistoryItem item = CreateActionHistoryItem();
    document.History.Add(item);
    item.Redo(document);
}

Получилось элегантно и красиво. Первое выполнение действия — это 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 похоже было изначально.

Сам термин undo был упомянут, возможно впервые, также в 1976 году: “It would be quite useful, to permit users to ‘take back’ at least the immediately preceding command (by issuing some special ‘undo’ command).” (Lance A. Miller and John C. Thomas of I.B.M., “Behavioral Issues in the Use of Interactive Systems.”) (см. статью в NY Times Magazine, 5-й абзац).
Tags:
Hubs:
Total votes 89: ↑75 and ↓14 +61
Views 36K
Comments Comments 87

Information

Founded
1998
Location
Россия
Website
www.developersoft.ru
Employees
201–500 employees
Registered