標籤：

請問編輯器中的undo和redo操作是如何實現的？

01-04

這篇文章列了一系列編輯器的內部數據結構值得一看，從簡單到複雜，不過有點小老： https://www.cs.unm.edu/~crowley/papers/sds.pdf 。大致上，文本編輯器的內部數據結構用來管理編輯中的文本序列，需要支持隨機插入、刪除，也需要實時地檢索出當前的文本內容交付 UI 渲染，最好也考慮進來 undo/redo。

文章最後的 piece table 演算法已經屬於 immutable 數據結構了，只用一張 piece 表來管理變更，而文件正文可以不讀到內存里，省內存，對 undo 操作也很友好。現在應該用 Rope 這個數據結構比較多： Rope (data structure) 。

Rope 是個 immutable 的數據結構，每次操作後記下樹的根，undo 時切一個根就好。

1，定義好command的正反操作

2，用一個雙向隊列記錄下所有command

像 Redux 這種狀態管理方式，用 immutable 數據結構 + 可序列化的 action，很容易就可以實現 undo。不過不清楚傳統的非 Web 編輯器是不是這麼做的。見 omnidan/redux-undo。

---

額額額再看了一下，似乎對於長文本就不能這麼暴力了，不然分分鐘變成內存殺手。 @fleuria 提到的 Rope 似乎才是處理這個的。

我猜測是用一個雙端隊列來維護操作....雙端隊列的長度是允許undo的最大次數，每次執行一個鍵入/刪除等操作時，就push_back一個操作進去，記錄操作的坐標以及操作的對象.如果隊列長度達到最大次數就把最久遠的那個操作pop_front掉...

undo就是用一個指針從隊尾開始往前掃，原來是刪除的就變成鍵入，原來是鍵入的就變成刪除，直到有新的操作或者到了隊頭...如果有新的操作，就把指針後面的都pop_back掉

redo就是這個指針往後掃，執行原來的操作。。。。

僅僅是猜測，沒有研究過這方面的知識_(:з」∠)_，打臉請輕點....

command模式，每個操作抽象成command，它們各自有一個反操作，負責復原這一步的操作。簡單來說就這樣

簡單點的就直接在每個操作的時候把整個界面序列化到內存，不過這種做法一來耗內存，二來不靈活，萬一有什麼特殊的需求就很難控制了

我之前的做法是，每個操作都實現基類的Undo、Redo方法，然後專門搞個類來管理操作，每次執行操作時將操作及操作需要的一系列元素及業務對象保存到棧中，Undo的時候再根據這些信息還原回來，Redo則在Undo的時候保存撤消的操作

貼部分代碼出來僅供參考

public abstract class ActionBase
{
private int _step;
/// & /// 操作編號，因為有時一次會撤消多個操作，所以編號可能會相同
/// & public int Step
{
get { return _step; }
set { _step = value; }
}

private ActionType _actionType;
/// & /// 操作類型
/// & public ActionType ActionType
{
get { return _actionType; }
set { _actionType = value; }
}

private FrameworkElement _actionObject;
/// & /// 操作對象，主要是UI對象
/// & public FrameworkElement ActionObject
{
get { return _actionObject; }
set { _actionObject = value; }
}

private Panel _container;
/// & /// 操作元素的父級
/// & public Panel Container
{
get { return _container; }
set { _container = value; }
}

private Object _businessObject;
/// & /// 業務對象
/// & public Object BusinessObject
{
get { return _businessObject; }
set { _businessObject = value; }
}

public virtual void Undo()
{
}

public virtual event EventHandler UndoCompleted;
public virtual void OnUndoComplete()
{
if (UndoCompleted != null)
UndoCompleted(this, EventArgs.Empty);
}

public virtual void Redo()
{ }

public virtual event EventHandler RedoCompleted;
public virtual void OnRedoComplete()
{
if (RedoCompleted != null)
RedoCompleted(this, EventArgs.Empty);
}

}

/// & /// 管理撤消、反撤消操作
/// & public static class UndoManager
{
static UndoManager()
{
}

private static Stack& _undoActions;
/// & /// 操作棧，用於撤消
/// & public static Stack& UndoActions
{
get { return _undoActions ?? (_undoActions = new Stack&()); }
set { _undoActions = value; }
}

private static DelegateCommand _undoCommand;
public static DelegateCommand UndoCommand
{
get { return _undoCommand ?? (_undoCommand = new DelegateCommand(ExecUndo, CanExecUndo)); }
}
public static void ExecUndo()
{
int step = GetLastStepCount();
if (step &> 0)
{
while (UndoActions.Count &> 0 UndoActions.Peek().Step == step)
{
ActionBase useraction = UndoActions.Pop();
if (useraction != null)
{
useraction.Undo();
RedoActions.Push(useraction);
RedoCommand.RaiseCanExecute();
}
}
}
}
public static bool CanExecUndo()
{
return UndoActions.Count &> 0;
}

public static void RaiseCanExecUndo()
{
UndoCommand.RaiseCanExecute();
}

/// & /// 獲取操作棧中的操作步驟（Step會有相同的，表示屬於同一次操作）
/// & /// &&
public static int GetLastStepCount()
{
if (UndoActions.Count == 0) return 0;
return UndoActions.Peek().Step;
}

private static Stack& _redoActions;
/// & /// 反撤消棧
/// & public static Stack& RedoActions
{
get { return _redoActions ?? (_redoActions = new Stack&()); }
set { _redoActions = value; }
}

private static DelegateCommand _redoCommand;
public static DelegateCommand RedoCommand
{
get { return _redoCommand ?? (_redoCommand = new DelegateCommand(ExecRedo, CanExecRedo)); }
}
public static void ExecRedo()
{
int step = 0;
if (RedoActions.Count &> 0) step = RedoActions.Peek().Step;
if (step &> 0)
{
while (RedoActions.Count &> 0 RedoActions.Peek().Step == step)
{
ActionBase useraction = RedoActions.Pop();
if (useraction != null)
{
useraction.Redo();
RedoCommand.RaiseCanExecute();
UndoActions.Push(useraction);
UndoCommand.RaiseCanExecute();
}
}
}
}
public static bool CanExecRedo()
{
return RedoActions.Count &> 0;
}

public static void RaiseCanExecRedo()
{
RedoCommand.RaiseCanExecute();
}

}

GoyaPixel 一個開源的線上的像素編輯器。

clojurescript+om,next寫的

其中 history + redo + undo功能在這裡

jackschaedler/goya

沒幾行代碼。

就是 @bhuztez 的說的實現

首先，要求編輯器中的每一種編輯操作都有逆操作，比如刪除的逆操作是插入，其次，每個操作都要把之前的狀態記錄下來，比如插入的位置，插入文本的長度，修改前的字體等。這樣就可以生成對應的逆操作及其參數。

然後，用一個棧保存編輯操作的逆操作，以及響應的狀態。棧是先進後出，也就是最先彈出來的是最近的操作，

當上面的逆操作執行完後，就恢復到了下面一個逆操作可以執行的狀態。當棧為空時就沒有undo可以執行了，undo菜單灰化。

再用一個棧保存執行的undo操作的逆操作，每執行一個undo，就壓一個逆操作到uredo棧中，就可以實現redo了。當用戶有新的編輯操作時，就清空redo棧

當遇到沒有逆操作的操作，或者要記錄的狀態太大，就可以在操作時提醒無法undo，執行後清空undo的棧。

有時候一個操作對內容的修改的操作很複雜，要實現一次undo就能夠完全撤銷操作，就需要引入原子操作和複合操作的概念，一個符合操作包含一系列操作（原子或複合），一個複合操作的逆操作就是逆序組織的每個子操作的逆操作。

這樣一次替換全部操作就可以由一系列替換操作組成，一次就可以undo。

擼Rope覺得複雜的話，可以看看Gap Buffer。

跟版本庫管理很像，每個修改產生一個patch，可以應用補丁，可以回退。

比較高級和直觀的是樹狀結構，類似於版本庫的分支，emacs的undo-tree插件非常直觀好用

我做的圖片編輯器是在每次操作後將操作結果保存到一個隊列。

因為不是所有的操作都是可逆的。

比如高斯模糊後，圖片信息會丟失，找不回來的。

帶版本的紅黑樹

類似於資料庫的redo /undo日誌

可持久化數據結構...

推薦閱讀：

※怎樣學好數據結構和編程？
※鏈表是一種數據結構還是數據類型？
※初學數據結構，怎麼理解書上的這句話？
※問一個關於寄存器與棧的問題?
※剛入門編程的人有必要學習數據結構嗎？

TAG:文本編輯器 | 演算法 | 程序 | 數據結構 |