吳亞非　臧義華　王凱等

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

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

DOIDOI：10.11907/rjdk.151553

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）008008903

0 引言

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

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

1 設(shè)計(jì)思想

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

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

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

2.2 撤銷/恢復(fù)節(jié)點(diǎn)設(shè)計(jì)

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

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

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

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

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

使用復(fù)合操作類型可以將二次開發(fā)中的動(dòng)作整合管理，但二次開發(fā)中并不是所有功能都利用底層平臺(tái)功能，有一些二次開發(fā)自有功能，應(yīng)用系統(tǒng)則無(wú)法實(shí)現(xiàn)整體的撤銷/恢復(fù)。無(wú)論是自定義功能不支持撤銷/恢復(fù)，還是分開實(shí)現(xiàn)，都會(huì)降低用戶體驗(yàn)。利用上節(jié)撤銷恢復(fù)節(jié)點(diǎn)設(shè)計(jì)中的UndoRedoType類型，為二次開發(fā)用戶定義擴(kuò)展類型GS_EXTEND，將二次開發(fā)中的自有功能添加到撤銷/恢復(fù)鏈表中。為了實(shí)現(xiàn)在撤銷/恢復(fù)中調(diào)用二次開發(fā)中的函數(shù)，需要定義兩個(gè)回調(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ù)操作時(shí)，根據(jù)UndoRedoType類型判斷是否是用戶自定義動(dòng)作，如果是用戶自定義動(dòng)作，調(diào)用上述回調(diào)函數(shù)，用戶根據(jù)iType值判斷具體執(zhí)行動(dòng)作類型完成操作。

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

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

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

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

3 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

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