| 标题 | 一种可用于开发平台的撤销/恢复通用算法 |
| 范文 | 吴亚非 臧义华 王凯等 摘要：针对具有编辑功能软件的撤销/恢复功能无法做到操作与历史记录统一，二次开发中自有功能无法实现一体化设计的问题，设计了一种撤销/恢复通用算法。采用双向链表法记录撤销/恢复数据，将用户操作分为基本操作和复合操作，通过复合操作的方式保证操作与历史记录一致。同时，向二次开发用户提供数据代管功能，以回调函数的方式实现应用软件自有功能与平台提供功能的一体化撤销/恢复，以提高软件用户体验。 关键词：撤销/恢复；双向链表；数据代管 DOIDOI：10.11907/rjdk.151553 中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2015）008008903 0 引言 在具备编辑功能的应用软件中，用户常常需要针对编辑对象进行创建、删除、复制、剪切、调整等多种操作，工作过程中误操作不可避免。因此，提供撤销/恢复（Undo/Redo）功能是提高应用系统易用性的必要手段之一。目前，几乎所有的编辑类软件都提供该项功能，而一些开发平台类软件却不提供，特别是沿用以往技术成果的开发支撑软件，需要二次开发用户根据需要自行设计；另外一些提供撤销/恢复功能的平台类软件开发函数往往存在诸多问题，例如无法支持所有操作、只支持基本动作的撤销/恢复等，而二次开发后基于多个底层基本动作完成一项功能后，撤销/恢复历史记录与操作不一致，令用户体验较差。 传统的撤销/恢复有两种方法，即链表法和命令模式法，这两种基本的实现方式在很多资料中都有详细介绍，这里不再详细说明。本文编写的背景是，需要在一种嵌入式图形开发平台中增加撤销/恢复功能，并且尽可能减少对原有功能的影响，保持软件稳定运行。如果采用命令模式法，势必要对原有程序作大规模修改，而无论是链表法还是命令模式法，都难以满足实现二次开发的撤销恢复一体化的需要。本文设计了一种基于双向链表的通用撤销/恢复算法，一次性撤销/恢复二次开发中使用的多个基本动作，实现二次开发后撤销/恢复历史记录与用户操作一致；同时可向二次开发用户提供数据代管，以回调函数的方式实现应用软件自有功能与平台提供功能的一体化撤销/恢复，提高用户体验。 1 设计思想 撤销/恢复基本思想：开始执行某一种操作命令后，撤销命令生效，至少执行了一条撤销命令后，恢复命令生效；再执行一次新的操作命令后，恢复命令全部清空。 一个设计良好的撤销/恢复算法应该满足下列条件：①能够支持任意操作，尽可能减少误操作带来的损失；②能够定义撤销/恢复的最大步数，防止内存无限制增加带来的系统健壮性问题；③能够提供给用户撤销/恢复命令的名称。 用于开发平台的撤销/恢复功能需要提供撤销/恢复函数供二次开发用户使用，这些函数除了满足上述设计规则外，面临的最大问题是，一次撤销/恢复的命令可能来自创建、删除等基本动作，也可能来自二次开发用户利用多个编辑函数组合形成的复合动作，但这种复合动作对最终用户来说是一个动作[1]。如图1所示，在应用程序中有绘制矩形这种操作，根据需求绘制一个范围矩形，然后修改为指定颜色、线宽、填充属性等，由于用户操作时是1次操作而非4次操作，撤销时同样要求1次撤销而非4次撤销。 图1 基本操作与复合操作 2 算法设计 2.1 撤销/恢复行为设计 具有撤销/恢复功能的软件中，需要把编辑对象保存到内存中，以便在对象的整个生命周期实施增、删、改、查等操作。这种操作是针对内存中的对象，不考虑撤销/恢复操作时，这些操作无需记录，反之必须将这些操作过程记录下来，形成操作历史命令链表，为执行撤销/恢复作准备，并且为了快速遍历，操作历史命令链表应为双向链表。图2为执行了4次操作的撤销/恢复命令链表。 图2 执行了4次操作的撤销/恢复命令链表 只要有操作发生，历史链表就有对象加入链表尾部，撤销由后向前执行，恢复由前向后执行。当Undo/Redo指针的前序节点为NULL时，不能执行撤销；后续节点为空时，不能执行恢复。另外，在执行撤销/恢复过程中（Undo/Redo指针不在最后一个节点），有任意新操作发生时，Undo/Redo节点跳转到最后一个节点，同时清空中间节点的数据。图3示意了撤销发生两次后，有“操作5”发生，这时Undo/Redo链表跳转到“操作5”，“操作3”和“操作4”的指针从内存中清空，不再允许被撤销与恢复[24]。 支持一次性撤销多个操作组成的复合操作需要解决两个问题，即标识基本动作为复合动作的组成部分（参见2.2的有关描述），Undo/Redo指针在判断为复合动作时能一次性跳转多个位置，如图4所示。 图3 执行两次撤销后有新操作发生 图4 撤销复合动作（多个基本动作组成） 2.2 撤销/恢复节点设计 撤销/恢复链表的节点应记录操作对象，但为了节省内存空间，只需记录一个指向对象的指针即可。其中应当注意的是，系统中增加撤销/恢复功能后，只要对象被创建，内存中就会有对应的数据存在，即使被删除，内存也不会被清空，否则会导致撤销/恢复节点找不到正确对象。 一个撤销/恢复动作应当有具体名称，这样在设计UI界面时，能够帮助最终用户了解能够撤销/恢复的历史动作。图5演示了图形编辑系统中撤销命令的历史列表。 为了能够撤销/恢复到历史状态，必须记录操作前后对象的状态（属性）。这个状态视操作类型的不同而有所区别，需要记录的状态值和类型各不相同，所以操作前和操作后状态值设计为void*类型。 节点的状态非常关键，由于要同时支持一次性撤销一个基本工作或复合动作，每一次基本操作发生时都要增加到撤销/恢复历史链表中，但复合动作与基本动作要有所区分，必须以状态位加以控制。定义GS_UndoRedoStatus枚举类型用于标识动作状态，GS_UNDOSELF为基本动作，GS_UNDOBEGIN、GS_UNDOCENTER、GS_UNDOEND标识一个完整的复合动作，撤销/恢复时将多个基本动作依次执行。 2.3 撤销/恢复一体化设计 使用复合操作类型可以将二次开发中的动作整合管理，但二次开发中并不是所有功能都利用底层平台功能，有一些二次开发自有功能，应用系统则无法实现整体的撤销/恢复。无论是自定义功能不支持撤销/恢复，还是分开实现，都会降低用户体验。利用上节撤销恢复节点设计中的UndoRedoType类型，为二次开发用户定义扩展类型GS_EXTEND，将二次开发中的自有功能添加到撤销/恢复链表中。为了实现在撤销/恢复中调用二次开发中的函数，需要定义两个回调函数： （1）撤销操作回调函数。 typedef void （*GS_UndoOperation）（void *pValue，intiType）。 （2）恢复操作回调函数。 typedef void （*GS_RedoOperation）（void *pValue，intiType）。 系统执行撤销/恢复操作时，根据UndoRedoType类型判断是否是用户自定义动作，如果是用户自定义动作，调用上述回调函数，用户根据iType值判断具体执行动作类型完成操作。 2.4 撤销/恢复二次开发接口设计 撤销/恢复主要开发接口如下：①复合动作开始函数，需要设置复合动作在撤销/恢复历史中的名称intGsBeginCommand（char* szCmdName）；② 复合动作结束函数intGsEndCommand（）；③撤销void Undo（）；④ 恢复void Redo（）；⑤判断是否可以执行撤销命令boolifUndo（）；⑥判断是否可以执行恢复命令boolifRedo（）；⑦获取撤销命令名称intGetUndoName（iIndex，char *szName）；⑧ 获取恢复命令名称 intGetRedoName（intiIndex，char* szName）；⑨设置撤销/恢复最大步长IntSetUndoRedoMaxLength（intiLen） 需要说明的是，二次开发用户需要成对使用BeginCommand（）和EndCommand（），将复合动作代码包裹起来，这样才能保证一次撤销/恢复能够执行多个基本动作。 3 结语 本文详细介绍了基于双向循环链表法、以复合动作的方式实现一次撤销/恢复多步操作的算法设计，解决了二次开发后撤销/恢复历史记录与用户操作不一致的问题。同时通过代管用户数据，以回调函数的方式实现整个系统撤销/恢复操作一体化。设计简单有效，对原有程序影响小，特别适用于对已有成熟软件的改造。该设计不仅能够用于实现传统的撤销/恢复功能，而且能够满足二次开发的应用需要。 利用本文提出的设计思想，笔者在一个国内广为使用的嵌入式图形平台上增加了撤销/恢复二次开发功能。在改造过程中，经过对比分析，这种方法相对文献[2]提出的命令模式方法，对原有代码改动量减少30%以上；改造完成后，新提供的版本经过各类二次开发用户在多种应用场景下的使用验证，证明这种方法是合理可行的。 参考文献： [1] 赵高长.多步无限撤消及恢复算法与实现[J].西安科技大学学报，2009（4）：500504. [2] 聂颖.图形应用系统下Undo/Redo操作的设计与实现[J].计算机应用研究，2005（3）：181182. [3] 韩小俊，王珂.矢量图软件中Undo/Redo操作[J].图形图像处理与游戏编程，2007（3）：6365. [4] 朱靖飞，谢虎.图形编辑系统下Undo/Redo操作的设计与实现[J].科学技术与工程，2009（6）：15971599. （责任编辑：黄 健） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。