一種可用于開發(fā)平臺的撤銷/恢復(fù)通用算法

吳亞非　臧義華　王凱等

摘要：針對具有編輯功能軟件的撤銷/恢復(fù)功能無法做到操作與歷史記錄統(tǒng)一，二次開發(fā)中自有功能無法實現(xiàn)一體化設(shè)計的問題，設(shè)計了一種撤銷/恢復(fù)通用算法。采用雙向鏈表法記錄撤銷/恢復(fù)數(shù)據(jù)，將用戶操作分為基本操作和復(fù)合操作，通過復(fù)合操作的方式保證操作與歷史記錄一致。同時，向二次開發(fā)用戶提供數(shù)據(jù)代管功能，以回調(diào)函數(shù)的方式實現(xiàn)應(yīng)用軟件自有功能與平臺提供功能的一體化撤銷/恢復(fù)，以提高軟件用戶體驗。

關(guān)鍵詞：撤銷/恢復(fù)；雙向鏈表；數(shù)據(jù)代管

DOIDOI：10.11907/rjdk.151553

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2015）008008903

0 引言

在具備編輯功能的應(yīng)用軟件中，用戶常常需要針對編輯對象進行創(chuàng)建、刪除、復(fù)制、剪切、調(diào)整等多種操作，工作過程中誤操作不可避免。因此，提供撤銷/恢復(fù)（Undo/Redo）功能是提高應(yīng)用系統(tǒng)易用性的必要手段之一。目前，幾乎所有的編輯類軟件都提供該項功能，而一些開發(fā)平臺類軟件卻不提供，特別是沿用以往技術(shù)成果的開發(fā)支撐軟件，需要二次開發(fā)用戶根據(jù)需要自行設(shè)計；另外一些提供撤銷/恢復(fù)功能的平臺類軟件開發(fā)函數(shù)往往存在諸多問題，例如無法支持所有操作、只支持基本動作的撤銷/恢復(fù)等，而二次開發(fā)后基于多個底層基本動作完成一項功能后，撤銷/恢復(fù)歷史記錄與操作不一致，令用戶體驗較差。

傳統(tǒng)的撤銷/恢復(fù)有兩種方法，即鏈表法和命令模式法，這兩種基本的實現(xiàn)方式在很多資料中都有詳細介紹，這里不再詳細說明。本文編寫的背景是，需要在一種嵌入式圖形開發(fā)平臺中增加撤銷/恢復(fù)功能，并且盡可能減少對原有功能的影響，保持軟件穩(wěn)定運行。如果采用命令模式法，勢必要對原有程序作大規(guī)模修改，而無論是鏈表法還是命令模式法，都難以滿足實現(xiàn)二次開發(fā)的撤銷恢復(fù)一體化的需要。本文設(shè)計了一種基于雙向鏈表的通用撤銷/恢復(fù)算法，一次性撤銷/恢復(fù)二次開發(fā)中使用的多個基本動作，實現(xiàn)二次開發(fā)后撤銷/恢復(fù)歷史記錄與用戶操作一致；同時可向二次開發(fā)用戶提供數(shù)據(jù)代管，以回調(diào)函數(shù)的方式實現(xiàn)應(yīng)用軟件自有功能與平臺提供功能的一體化撤銷/恢復(fù)，提高用戶體驗。

1 設(shè)計思想

撤銷/恢復(fù)基本思想：開始執(zhí)行某一種操作命令后，撤銷命令生效，至少執(zhí)行了一條撤銷命令后，恢復(fù)命令生效；再執(zhí)行一次新的操作命令后，恢復(fù)命令全部清空。

一個設(shè)計良好的撤銷/恢復(fù)算法應(yīng)該滿足下列條件：①能夠支持任意操作，盡可能減少誤操作帶來的損失；②能夠定義撤銷/恢復(fù)的最大步數(shù)，防止內(nèi)存無限制增加帶來的系統(tǒng)健壯性問題；③能夠提供給用戶撤銷/恢復(fù)命令的名稱。

用于開發(fā)平臺的撤銷/恢復(fù)功能需要提供撤銷/恢復(fù)函數(shù)供二次開發(fā)用戶使用，這些函數(shù)除了滿足上述設(shè)計規(guī)則外，面臨的最大問題是，一次撤銷/恢復(fù)的命令可能來自創(chuàng)建、刪除等基本動作，也可能來自二次開發(fā)用戶利用多個編輯函數(shù)組合形成的復(fù)合動作，但這種復(fù)合動作對最終用戶來說是一個動作[1]。如圖1所示，在應(yīng)用程序中有繪制矩形這種操作，根據(jù)需求繪制一個范圍矩形，然后修改為指定顏色、線寬、填充屬性等，由于用戶操作時是1次操作而非4次操作，撤銷時同樣要求1次撤銷而非4次撤銷。

圖1 基本操作與復(fù)合操作

2 算法設(shè)計

2.1 撤銷/恢復(fù)行為設(shè)計

具有撤銷/恢復(fù)功能的軟件中，需要把編輯對象保存到內(nèi)存中，以便在對象的整個生命周期實施增、刪、改、查等操作。這種操作是針對內(nèi)存中的對象，不考慮撤銷/恢復(fù)操作時，這些操作無需記錄，反之必須將這些操作過程記錄下來，形成操作歷史命令鏈表，為執(zhí)行撤銷/恢復(fù)作準備，并且為了快速遍歷，操作歷史命令鏈表應(yīng)為雙向鏈表。圖2為執(zhí)行了4次操作的撤銷/恢復(fù)命令鏈表。

圖2 執(zhí)行了4次操作的撤銷/恢復(fù)命令鏈表

只要有操作發(fā)生，歷史鏈表就有對象加入鏈表尾部，撤銷由后向前執(zhí)行，恢復(fù)由前向后執(zhí)行。當(dāng)Undo/Redo指針的前序節(jié)點為NULL時，不能執(zhí)行撤銷；后續(xù)節(jié)點為空時，不能執(zhí)行恢復(fù)。另外，在執(zhí)行撤銷/恢復(fù)過程中（Undo/Redo指針不在最后一個節(jié)點），有任意新操作發(fā)生時，Undo/Redo節(jié)點跳轉(zhuǎn)到最后一個節(jié)點，同時清空中間節(jié)點的數(shù)據(jù)。圖3示意了撤銷發(fā)生兩次后，有“操作5”發(fā)生，這時Undo/Redo鏈表跳轉(zhuǎn)到“操作5”，“操作3”和“操作4”的指針從內(nèi)存中清空，不再允許被撤銷與恢復(fù)[24]。

支持一次性撤銷多個操作組成的復(fù)合操作需要解決兩個問題，即標識基本動作為復(fù)合動作的組成部分（參見2.2的有關(guān)描述），Undo/Redo指針在判斷為復(fù)合動作時能一次性跳轉(zhuǎn)多個位置，如圖4所示。

圖3 執(zhí)行兩次撤銷后有新操作發(fā)生

圖4 撤銷復(fù)合動作（多個基本動作組成）

2.2 撤銷/恢復(fù)節(jié)點設(shè)計

撤銷/恢復(fù)鏈表的節(jié)點應(yīng)記錄操作對象，但為了節(jié)省內(nèi)存空間，只需記錄一個指向?qū)ο蟮闹羔樇纯?。其中?yīng)當(dāng)注意的是，系統(tǒng)中增加撤銷/恢復(fù)功能后，只要對象被創(chuàng)建，內(nèi)存中就會有對應(yīng)的數(shù)據(jù)存在，即使被刪除，內(nèi)存也不會被清空，否則會導(dǎo)致撤銷/恢復(fù)節(jié)點找不到正確對象。

一個撤銷/恢復(fù)動作應(yīng)當(dāng)有具體名稱，這樣在設(shè)計UI界面時，能夠幫助最終用戶了解能夠撤銷/恢復(fù)的歷史動作。圖5演示了圖形編輯系統(tǒng)中撤銷命令的歷史列表。

為了能夠撤銷/恢復(fù)到歷史狀態(tài)，必須記錄操作前后對象的狀態(tài)（屬性）。這個狀態(tài)視操作類型的不同而有所區(qū)別，需要記錄的狀態(tài)值和類型各不相同，所以操作前和操作后狀態(tài)值設(shè)計為void*類型。

節(jié)點的狀態(tài)非常關(guān)鍵，由于要同時支持一次性撤銷一個基本工作或復(fù)合動作，每一次基本操作發(fā)生時都要增加到撤銷/恢復(fù)歷史鏈表中，但復(fù)合動作與基本動作要有所區(qū)分，必須以狀態(tài)位加以控制。定義GS_UndoRedoStatus枚舉類型用于標識動作狀態(tài)，GS_UNDOSELF為基本動作，GS_UNDOBEGIN、GS_UNDOCENTER、GS_UNDOEND標識一個完整的復(fù)合動作，撤銷/恢復(fù)時將多個基本動作依次執(zhí)行。

2.3 撤銷/恢復(fù)一體化設(shè)計

使用復(fù)合操作類型可以將二次開發(fā)中的動作整合管理，但二次開發(fā)中并不是所有功能都利用底層平臺功能，有一些二次開發(fā)自有功能，應(yīng)用系統(tǒng)則無法實現(xiàn)整體的撤銷/恢復(fù)。無論是自定義功能不支持撤銷/恢復(fù)，還是分開實現(xiàn)，都會降低用戶體驗。利用上節(jié)撤銷恢復(fù)節(jié)點設(shè)計中的UndoRedoType類型，為二次開發(fā)用戶定義擴展類型GS_EXTEND，將二次開發(fā)中的自有功能添加到撤銷/恢復(fù)鏈表中。為了實現(xiàn)在撤銷/恢復(fù)中調(diào)用二次開發(fā)中的函數(shù)，需要定義兩個回調(diào)函數(shù)：

（1）撤銷操作回調(diào)函數(shù)。

typedef void （*GS_UndoOperation）（void *pValue，intiType）。

（2）恢復(fù)操作回調(diào)函數(shù)。

typedef void （*GS_RedoOperation）（void *pValue，intiType）。

系統(tǒng)執(zhí)行撤銷/恢復(fù)操作時，根據(jù)UndoRedoType類型判斷是否是用戶自定義動作，如果是用戶自定義動作，調(diào)用上述回調(diào)函數(shù)，用戶根據(jù)iType值判斷具體執(zhí)行動作類型完成操作。

2.4 撤銷/恢復(fù)二次開發(fā)接口設(shè)計

撤銷/恢復(fù)主要開發(fā)接口如下：①復(fù)合動作開始函數(shù)，需要設(shè)置復(fù)合動作在撤銷/恢復(fù)歷史中的名稱intGsBeginCommand（char* szCmdName）；② 復(fù)合動作結(jié)束函數(shù)intGsEndCommand（）；③撤銷void Undo（）；④ 恢復(fù)void Redo（）；⑤判斷是否可以執(zhí)行撤銷命令boolifUndo（）；⑥判斷是否可以執(zhí)行恢復(fù)命令boolifRedo（）；⑦獲取撤銷命令名稱intGetUndoName（iIndex，char *szName）；⑧ 獲取恢復(fù)命令名稱

intGetRedoName（intiIndex，char* szName）；⑨設(shè)置撤銷/恢復(fù)最大步長IntSetUndoRedoMaxLength（intiLen）

需要說明的是，二次開發(fā)用戶需要成對使用BeginCommand（）和EndCommand（），將復(fù)合動作代碼包裹起來，這樣才能保證一次撤銷/恢復(fù)能夠執(zhí)行多個基本動作。

3 結(jié)語

本文詳細介紹了基于雙向循環(huán)鏈表法、以復(fù)合動作的方式實現(xiàn)一次撤銷/恢復(fù)多步操作的算法設(shè)計，解決了二次開發(fā)后撤銷/恢復(fù)歷史記錄與用戶操作不一致的問題。同時通過代管用戶數(shù)據(jù)，以回調(diào)函數(shù)的方式實現(xiàn)整個系統(tǒng)撤銷/恢復(fù)操作一體化。設(shè)計簡單有效，對原有程序影響小，特別適用于對已有成熟軟件的改造。該設(shè)計不僅能夠用于實現(xiàn)傳統(tǒng)的撤銷/恢復(fù)功能，而且能夠滿足二次開發(fā)的應(yīng)用需要。

利用本文提出的設(shè)計思想，筆者在一個國內(nèi)廣為使用的嵌入式圖形平臺上增加了撤銷/恢復(fù)二次開發(fā)功能。在改造過程中，經(jīng)過對比分析，這種方法相對文獻[2]提出的命令模式方法，對原有代碼改動量減少30%以上；改造完成后，新提供的版本經(jīng)過各類二次開發(fā)用戶在多種應(yīng)用場景下的使用驗證，證明這種方法是合理可行的。

參考文獻：

[1] 趙高長.多步無限撤消及恢復(fù)算法與實現(xiàn)[J].西安科技大學(xué)學(xué)報，2009（4）：500504.

[2] 聶穎.圖形應(yīng)用系統(tǒng)下Undo/Redo操作的設(shè)計與實現(xiàn)[J].計算機應(yīng)用研究，2005（3）：181182.

[3] 韓小俊，王珂.矢量圖軟件中Undo/Redo操作[J].圖形圖像處理與游戲編程，2007（3）：6365.

[4] 朱靖飛，謝虎.圖形編輯系統(tǒng)下Undo/Redo操作的設(shè)計與實現(xiàn)[J].科學(xué)技術(shù)與工程，2009（6）：15971599.

（責(zé)任編輯：黃 ?。?