5,530
社区成员
发帖
与我相关
我的任务
分享UNDO/REDO实现感想[指正有分]
GOOGLE了一把UNDO/REDO实现，发现很多只谈到COMMAND，不是很满意，自己写个实现感想，就放在这里吧。
实际上一个完整UNDO/REDO系统除了COMMAND，还有很多复杂的地方：
1 在每一个COMMAND里面必须保存一个MEMENTO，用来保存COMMAND执行前的状态
1.1 该MEMENTO是用什么方式保存？参数还是内存块？
如是内存块的话？UNDO步数一多，内存是否成为问题？如果是参数的话？如何解析？
1.2 MEMENTO什么时候获取，是自动获取还是用户填入？
1.3 如果是不同类型的COMMAND混合使用，MEMENTO类型是否相同？不同的话，混合使用是否会有问题？
2 COMMANDHISTORY中UI的支持
2.1 如果只支持UNDO/REDO，只需要关心UNDO步数和PRESENTLINE就可以了；
2.2 如果还要支持RESET，必须保存原始状态；
2.3 如果需要支持SLIDER（LIKE PHOTOSHOP），还要考虑UNDO/REDO跳跃及其效率优化问题
3 如何支持无限UNDO/REDO的话
3.1 虚拟内存就成为必须，这部分的管理放在什么地方？
3.2 效率没问题吗？
4 如何方便的替换
4.1 如何可以方便的替换MEMENTO/MEMENTO保存方式/参数及其解析方法？
4.2 如何可以方便的替换UNDO跳跃处理策略？
4.3 如何可以方便的替换虚拟内存管理策略？
关键词：UNDO/REDO， COMMAND， MEMENTO， 设计模式
实际上一个完整UNDO/REDO系统除了COMMAND，还有很多复杂的地方：
1 在每一个COMMAND里面必须保存一个MEMENTO，用来保存COMMAND执行前的状态
1.1 该MEMENTO是用什么方式保存？参数还是内存块？
如是内存块的话？UNDO步数一多，内存是否成为问题？如果是参数的话？如何解析？
1.2 MEMENTO什么时候获取，是自动获取还是用户填入？
1.3 如果是不同类型的COMMAND混合使用，MEMENTO类型是否相同？不同的话，混合使用是否会有问题？
2 COMMANDHISTORY中UI的支持
2.1 如果只支持UNDO/REDO，只需要关心UNDO步数和PRESENTLINE就可以了；
2.2 如果还要支持RESET，必须保存原始状态；
2.3 如果需要支持SLIDER（LIKE PHOTOSHOP），还要考虑UNDO/REDO跳跃及其效率优化问题
3 如何支持无限UNDO/REDO的话
3.1 虚拟内存就成为必须，这部分的管理放在什么地方？
3.2 效率没问题吗？
4 如何方便的替换
4.1 如何可以方便的替换MEMENTO/MEMENTO保存方式/参数及其解析方法？
4.2 如何可以方便的替换UNDO跳跃处理策略？
4.3 如何可以方便的替换虚拟内存管理策略？
关键词：UNDO/REDO， COMMAND， MEMENTO， 设计模式
...全文
请发表友善的回复…
发表回复
woyaowenzi 2012-03-08
- 打赏
- 举报
很精彩的讨论。收藏。
hjj8848 2008-09-11
- 打赏
- 举报
感谢ouyh12345和sandrowjw的参与。
ouyh12345：
现在都不用3个vector，而都是用1个来处理了——称之为COMMANDHISTORY。
sandrowjw：
1 嵌套触发绝对是要避免的，否则说明定义不彻底。
2 定义彻底后，故意嵌套——称之为宏命令。
就是多个COMMAND合为一个，在很多地方都有广泛应用。
我以前做过，用Composite模式来处理COMMAND就可以了。
ouyh12345：
现在都不用3个vector，而都是用1个来处理了——称之为COMMANDHISTORY。
sandrowjw：
1 嵌套触发绝对是要避免的，否则说明定义不彻底。
2 定义彻底后，故意嵌套——称之为宏命令。
就是多个COMMAND合为一个，在很多地方都有广泛应用。
我以前做过，用Composite模式来处理COMMAND就可以了。
hjj8848 2008-09-11
- 打赏
- 举报
感谢tomwindcloud和shelok，你们的回答对我很有启发。谢谢！
tomwindcloud：
1 感谢你的开发经验的分享。
2 下次再开发同样的undo/redo，强烈推荐你用一下设计模式。毕竟没吃过螃蟹的人，永远也不知道螃蟹有多好吃。是不？
shelok：
1 你比我聪明多了。“所有元素的可序列化”——真是高人，其实这意味着所有元素都是都可以存在于历史之中，并且是可恢复的。
2 “对OOP只剩下最简单的理解:设计好类,设计好对象之间的交互”——这不正是OO的终极目标吗？
3 强烈推荐你一本书—— 《UML和模式应用》（原书第3版）
个人感觉其中的OO设计及原则比GOF的《设计模式》，马丁叔叔的《敏捷软件开发》还要精彩。
再次感谢你们。
tomwindcloud：
1 感谢你的开发经验的分享。
2 下次再开发同样的undo/redo，强烈推荐你用一下设计模式。毕竟没吃过螃蟹的人，永远也不知道螃蟹有多好吃。是不？
shelok：
1 你比我聪明多了。“所有元素的可序列化”——真是高人，其实这意味着所有元素都是都可以存在于历史之中，并且是可恢复的。
2 “对OOP只剩下最简单的理解:设计好类,设计好对象之间的交互”——这不正是OO的终极目标吗？
3 强烈推荐你一本书—— 《UML和模式应用》（原书第3版）
个人感觉其中的OO设计及原则比GOF的《设计模式》，马丁叔叔的《敏捷软件开发》还要精彩。
再次感谢你们。
shelok 2008-09-07
- 打赏
- 举报
我想补充的是用command只是实现undo/redo的一种方式;(命令容器加上动作的信息,前段时间做一个类似MS的workflow用command实现的)
去年在做一个GUI库的时候,因为仅仅只是个GUI库,没有设计到MVC,界面元素只负责保存自己,我采用的是所有界面元素都是可序列化的(支持文件流和内存流),工程的保存和恢复保存到文件里;每一步改变界面的操作保存到内存里(和保存到文件流的格式一样),undo/redo的时候从内存恢复(相当于恢复工程,所以不保存到内存流而保存到文件流就支持无限次undo/redo);这种方式需要把每一步改变后整个工程都保存再恢复;由于所有界面元素都是可序列化的,这样实现起来也比较方便.
我工作时间不长,才2年多一点,没什么很深刻的经验,就楼主说设计模式,个人的理解是,设计模式只是浮云,设计原则才是王道.从头到尾的看过几本比较经典的设计模式的书了 heard first Design pattern英文版是我的设计模式入门书,后来陆续看了GOF的经典设计模式,看道法自然,后来看敏捷软件开发,再看C++设计新思维泛型编程与设计模式的应用(这本书让我无敌惊叹泛型编程的美妙),可能有些囫囵吞枣,现在基本遇见设计模式能够解决的问题能够立即想到相应的模式...可是这,远远不够,我去年参与的一个GUI库,用不了很多模式,用得更多的是设计原则里的指导思想,现在对OOP只剩下最简单的理解:设计好类,设计好对象之间的交互;
去年在做一个GUI库的时候,因为仅仅只是个GUI库,没有设计到MVC,界面元素只负责保存自己,我采用的是所有界面元素都是可序列化的(支持文件流和内存流),工程的保存和恢复保存到文件里;每一步改变界面的操作保存到内存里(和保存到文件流的格式一样),undo/redo的时候从内存恢复(相当于恢复工程,所以不保存到内存流而保存到文件流就支持无限次undo/redo);这种方式需要把每一步改变后整个工程都保存再恢复;由于所有界面元素都是可序列化的,这样实现起来也比较方便.
我工作时间不长,才2年多一点,没什么很深刻的经验,就楼主说设计模式,个人的理解是,设计模式只是浮云,设计原则才是王道.从头到尾的看过几本比较经典的设计模式的书了 heard first Design pattern英文版是我的设计模式入门书,后来陆续看了GOF的经典设计模式,看道法自然,后来看敏捷软件开发,再看C++设计新思维泛型编程与设计模式的应用(这本书让我无敌惊叹泛型编程的美妙),可能有些囫囵吞枣,现在基本遇见设计模式能够解决的问题能够立即想到相应的模式...可是这,远远不够,我去年参与的一个GUI库,用不了很多模式,用得更多的是设计原则里的指导思想,现在对OOP只剩下最简单的理解:设计好类,设计好对象之间的交互;
sandrowjw 2008-07-16
- 打赏
- 举报
以前做过一些尝试，个人感觉无限UNDO是可能的，但是有几个问题：
1、如何正规化状态机，这个就是麻烦点而已，关键是避免出现嵌套触发（楼主有没有解决嵌套触发的经验？比如A COMMAND会触发B COMMAND，我一般感觉这是状态机没有定义好所以尽量避开）。
2、状态如何存储，这个最难，如果状态元组很占内存就要用非正常手段了，还要考虑I/O的问题。上面也都提到了，我觉得一些免加锁的手段可以在这里用，但是没时间尝试。
1、如何正规化状态机，这个就是麻烦点而已，关键是避免出现嵌套触发（楼主有没有解决嵌套触发的经验？比如A COMMAND会触发B COMMAND，我一般感觉这是状态机没有定义好所以尽量避开）。
2、状态如何存储，这个最难，如果状态元组很占内存就要用非正常手段了，还要考虑I/O的问题。上面也都提到了，我觉得一些免加锁的手段可以在这里用，但是没时间尝试。
tomwindcloud 2008-07-12
- 打赏
- 举报
UNDO以前我只做过一个简单的UNDO，现在正在做一个比较大型软件的UNDO/REDO，所以最近特别关注这方面的知识。以前搂主做过5个了，敬佩中。这里只是把我的感觉说出来，所谓言者无罪，有些肯定也属于无知者无畏了：）
1 关于无限UNDO。如果条件允许，无限UNDO肯定是最好的选择。只是有些项目比如我现在做的这个3D项目，需要保存的数据量很大，如果做成无限UNDO，可能对内存的要求比较大，出于现实考虑我还是做成缺省20步的UNDO。SVN我没有用过，就PHOTOSHOP VS2005 来说，感觉他们需要保存的数据量相对还是小。而3D项目，对数据量的要求是很大的，比如一个10万个点组成的网格，包括：顶点位置 顶点法矢 多层纹理坐标 面索引 网格属性 多层纹理信息等，数据量就有6M左右，用户删除后实际上还是需要保存的，这样的网格对一个大型项目可能有很多，比如10个这样的网格做成的一个组，如果反复的修改删除等，对项目的缓冲区要求是比较大的。我做的时候参考了3DSMAX，缺省20步，用户可以调整，一般满足了用户的要求。
2 关于设计模式的作用我同意你的看法。这种设计模式只能是在实践中做过一定项目的时候才能更好的理解，像我这种做项目少的，即使理解也不会深刻。
3 关于跳跃UNDO。项目不同，是否能够允许不要（或者部分不要）中间节点可能也会不同。我做的时候都是连续UNDO的，这样处理简洁，可能相对可靠一点。
1 关于无限UNDO。如果条件允许，无限UNDO肯定是最好的选择。只是有些项目比如我现在做的这个3D项目，需要保存的数据量很大，如果做成无限UNDO，可能对内存的要求比较大，出于现实考虑我还是做成缺省20步的UNDO。SVN我没有用过，就PHOTOSHOP VS2005 来说，感觉他们需要保存的数据量相对还是小。而3D项目，对数据量的要求是很大的，比如一个10万个点组成的网格，包括：顶点位置 顶点法矢 多层纹理坐标 面索引 网格属性 多层纹理信息等，数据量就有6M左右，用户删除后实际上还是需要保存的，这样的网格对一个大型项目可能有很多，比如10个这样的网格做成的一个组，如果反复的修改删除等，对项目的缓冲区要求是比较大的。我做的时候参考了3DSMAX，缺省20步，用户可以调整，一般满足了用户的要求。
2 关于设计模式的作用我同意你的看法。这种设计模式只能是在实践中做过一定项目的时候才能更好的理解，像我这种做项目少的，即使理解也不会深刻。
3 关于跳跃UNDO。项目不同，是否能够允许不要（或者部分不要）中间节点可能也会不同。我做的时候都是连续UNDO的，这样处理简洁，可能相对可靠一点。
hjj8848 2008-07-11
- 打赏
- 举报
做UNDO/REDO部分已经有些时间了，先后在5个大小不一的项目中提供UNDO/REDO。在这个过程中，越来越坚定这么一个想法：
做UNDO/REDO的终极目标——是做一台可以无限回溯的时间机器（当然只是对需要保存的操作而言），而且这台机器要方便维修，易于替换零件，易于扩充功能。
目前可以效仿的榜样有：
1 PHOTOSHOP
2 SVN
3 VS2005
如果以此为目标的话，个人感觉上面的5个方面就成为必须。
6 关于设计模式的作用
6.1 模式最重要的作用之一是封装变化，隔离变化的多米诺效应，换个机器零件不会影响其他部分。
6.2 如果是第一次实现UNDO/REDO，大可不必关心设计模式。
当初笔者第一次做，就只关心功能，没有模式。做好之后还自鸣得意——称之为“无招胜有招”。
6.3 第二次做，要优化一下性能，添加一个FEATURE，做着做着傻眼了。花的时间比第一次还多。
后来读了一下《设计模式》，彻底重构了一把，搞定。从此膜拜《设计模式》，视为圣经，每年都逐字逐字读一遍，生怕漏过一字。
7 关于无限UNDO
7.1 如果MEMENTO只记参数，无限UNDO就很容易实现，不需要虚拟内存的帮助，毕竟不会真的有人去做1百万步的。
7.2 如果MEMENTO中记录状态比较大，记内存或者参数内存混合使用（象PHOTOSHOP），就需要考虑内存管理与效率问题。难，但可以做。
7.3 在这个问题上，你做成，其他人做不成。你比其他人多走一步，你的价值就会无比闪耀。
8 关于跳跃UNDO
8.1 这里跳跃UNDO指起点终点不相邻，不是可以完全不要当中的节点。
8.2 跳跃UNDO其实比无限UNDO容易（可以做的话），但有些情况会无解（个人认为，必竟笔者才疏学浅）。
8.3 如果MEMENTO中参数完整记录了MODEL状态，跳跃UNDO就很容易，只要实现好MVC就行。
这样的参数有物体的平动、转动、缩放，歪斜，镜像，透明度等等。
8.4 如果MEMENTO中参数纪录的是MODEL状态的变化，那么跳跃UNDO就必须满足——MODEL状态变化的传递率。
这样才可能一次计算出，起点跳向终点的MODEL状态变化（所有节点的累积效果），并只VIEW一次。
8.5 如果MEMENTO中纪录的是内存（或状态量很大），那么在跳跃时（遍历经过的节点），可以忽略其中的一些会被后来节点覆盖掉的节点，提高效率。
但跳过去可以忽略，往往跳回来就不能忽略。
8.6 其实单步UNDO是跳跃UNDO的特殊情况，可以用同一个函数来实现。
8.7 以上可以做的部分，笔者称之为“跳跃UNDO策略”，如果不能做，就一步步UNDO回去，但VIEW只能一次。
做UNDO/REDO的终极目标——是做一台可以无限回溯的时间机器（当然只是对需要保存的操作而言），而且这台机器要方便维修，易于替换零件，易于扩充功能。
目前可以效仿的榜样有：
1 PHOTOSHOP
2 SVN
3 VS2005
如果以此为目标的话，个人感觉上面的5个方面就成为必须。
6 关于设计模式的作用
6.1 模式最重要的作用之一是封装变化，隔离变化的多米诺效应，换个机器零件不会影响其他部分。
6.2 如果是第一次实现UNDO/REDO，大可不必关心设计模式。
当初笔者第一次做，就只关心功能，没有模式。做好之后还自鸣得意——称之为“无招胜有招”。
6.3 第二次做，要优化一下性能，添加一个FEATURE，做着做着傻眼了。花的时间比第一次还多。
后来读了一下《设计模式》，彻底重构了一把，搞定。从此膜拜《设计模式》，视为圣经，每年都逐字逐字读一遍，生怕漏过一字。
7 关于无限UNDO
7.1 如果MEMENTO只记参数，无限UNDO就很容易实现，不需要虚拟内存的帮助，毕竟不会真的有人去做1百万步的。
7.2 如果MEMENTO中记录状态比较大，记内存或者参数内存混合使用（象PHOTOSHOP），就需要考虑内存管理与效率问题。难，但可以做。
7.3 在这个问题上，你做成，其他人做不成。你比其他人多走一步，你的价值就会无比闪耀。
8 关于跳跃UNDO
8.1 这里跳跃UNDO指起点终点不相邻，不是可以完全不要当中的节点。
8.2 跳跃UNDO其实比无限UNDO容易（可以做的话），但有些情况会无解（个人认为，必竟笔者才疏学浅）。
8.3 如果MEMENTO中参数完整记录了MODEL状态，跳跃UNDO就很容易，只要实现好MVC就行。
这样的参数有物体的平动、转动、缩放，歪斜，镜像，透明度等等。
8.4 如果MEMENTO中参数纪录的是MODEL状态的变化，那么跳跃UNDO就必须满足——MODEL状态变化的传递率。
这样才可能一次计算出，起点跳向终点的MODEL状态变化（所有节点的累积效果），并只VIEW一次。
8.5 如果MEMENTO中纪录的是内存（或状态量很大），那么在跳跃时（遍历经过的节点），可以忽略其中的一些会被后来节点覆盖掉的节点，提高效率。
但跳过去可以忽略，往往跳回来就不能忽略。
8.6 其实单步UNDO是跳跃UNDO的特殊情况，可以用同一个函数来实现。
8.7 以上可以做的部分，笔者称之为“跳跃UNDO策略”，如果不能做，就一步步UNDO回去，但VIEW只能一次。
xuguomin1982 2008-07-10
- 打赏
- 举报
这个问题值得讨论,我也很想知道
tomwindcloud 2008-07-10
- 打赏
- 举报
"何可以方便的替换UNDO跳跃处理策略？ "
建议不允许跳跃处理,只能连续处理, 允许连续多步处理, 不允许跳跃隔着步数处理.隔着步数处理个人感觉是无解的, 也是不符合逻辑的.
建议不允许跳跃处理,只能连续处理, 允许连续多步处理, 不允许跳跃隔着步数处理.隔着步数处理个人感觉是无解的, 也是不符合逻辑的.
tomwindcloud 2008-07-10
- 打赏
- 举报
关于无限的UNDO的一点看法.
项目目的不一样,那么需要UNDO时保存的状态参数的数据量也不一样,类似我现在开发的项目,需要保存的状态量很大,最后采用3DSMAX软件的作法,可以让用户选择一个可以UNDO的步数.个人认为这是一个切实可行的方法,如此尽管不够完美,但是至少让用户是可控的. 3DSMAX缺省的可UNDO数目是20.
项目目的不一样,那么需要UNDO时保存的状态参数的数据量也不一样,类似我现在开发的项目,需要保存的状态量很大,最后采用3DSMAX软件的作法,可以让用户选择一个可以UNDO的步数.个人认为这是一个切实可行的方法,如此尽管不够完美,但是至少让用户是可控的. 3DSMAX缺省的可UNDO数目是20.
tomwindcloud 2008-07-10
- 打赏
- 举报
我是做图形3D软件开发的,正要做这个部分,一直也在思考.一点想法大家交流.
其实设计模式什么的都不是关键,无非就是用一个栈或者链表表示这个过程,重要的是必须符合项目的实际.
整个UNDO/REDO过程必须保存2部分: 操作命令(COMMAND)和状态(可能就是搂主所说的MEMENTO吧). 命令的保存相对比较容易,
而状态的记录的确相当麻烦.个人感觉,应该是数据和参数混合的形式比较好,不需要教条,只要能正确记录状态的信息就可以.
至于保存在内存还是文件,个人感觉应该在内存开一个缓冲区,记录的数据超过缓冲区的时候再记录到文件中,我仔细思考过,只能如此.当然,还有一个解决方案就是有限次的UNDO/REDO.
状态的记录一定是个难点,例如:像我现在开发的项目,节点都有ID,删除后可能又有新的节点产生,那么UNDO后如何处理这个ID才能合理也是比较头疼的事情.
最后说一下对软件设计模式之类书的看法.这种书不看是不行的,理论的东西必须要有一些,但是千万别教条.而且个人感觉类似软件设计模式的作者很多都没有实际工程的经验,大多是纸上谈兵,如果一切照搬只能自食其果.
其实设计模式什么的都不是关键,无非就是用一个栈或者链表表示这个过程,重要的是必须符合项目的实际.
整个UNDO/REDO过程必须保存2部分: 操作命令(COMMAND)和状态(可能就是搂主所说的MEMENTO吧). 命令的保存相对比较容易,
而状态的记录的确相当麻烦.个人感觉,应该是数据和参数混合的形式比较好,不需要教条,只要能正确记录状态的信息就可以.
至于保存在内存还是文件,个人感觉应该在内存开一个缓冲区,记录的数据超过缓冲区的时候再记录到文件中,我仔细思考过,只能如此.当然,还有一个解决方案就是有限次的UNDO/REDO.
状态的记录一定是个难点,例如:像我现在开发的项目,节点都有ID,删除后可能又有新的节点产生,那么UNDO后如何处理这个ID才能合理也是比较头疼的事情.
最后说一下对软件设计模式之类书的看法.这种书不看是不行的,理论的东西必须要有一些,但是千万别教条.而且个人感觉类似软件设计模式的作者很多都没有实际工程的经验,大多是纸上谈兵,如果一切照搬只能自食其果.
ouyh12345 2008-07-09
- 打赏
- 举报
首先要关注UNDO/REDO的操作类型
然后，用3个vector记录正常操作、undo、redo
然后，用3个vector记录正常操作、undo、redo
hjj8848 2008-07-09
- 打赏
- 举报
5 MVC的实现
5.1 MVC的实现程度如何？
5.2 UNDO/REDO部分是否只对MVC中的M部分，从而V的修改不会导致UNDO/REDO的任何改变
5.1 MVC的实现程度如何？
5.2 UNDO/REDO部分是否只对MVC中的M部分，从而V的修改不会导致UNDO/REDO的任何改变
