撤消/重做实施

use*_*352 64 algorithm design-patterns

给我一些想法如何实现撤消/重做功能 - 就像我们在文本编辑器中一样.我应该使用哪些算法以及我可能阅读的内容.谢谢.

Laz*_*zer 76

我知道撤消类型的两个主要部分

  • 保存状态: 一类撤消是实际保存历史状态的地方.在这种情况下,发生的是在每个点上你继续将状态保存在某个内存位置.当你想要撤销时,你只需要换掉当前状态并交换已经存在于内存中的状态.例如,这是在Adobe Photoshop中使用History或在Google Chrome中重新打开已关闭的标签的方式.

替代文字

  • 生成状态: 另一类是在不改变状态的情况下,您只需记住操作是什么.当您需要撤消时,您需要对该特定操作进行逻辑反转.举一个简单的例子,当你在一些支持undo的文本编辑器中执行Ctrl+ B时,会记住它是一个粗体动作.现在,每个动作都是其逻辑反转的映射.因此,当您执行Ctrl+时Z,它会从反向操作表中查找并发现撤消操作再次为Ctrl+ B.这是执行,你得到你以前的状态.因此,此处您之前的状态未存储在内存中,而是在您需要时生成.

对于文本编辑器,以这种方式生成状态并不是计算密集型,但对于像Adobe Photoshop这样的程序,它可能过于计算密集或者根本不可能.例如 - 对于模糊操作,您将指定一个去模糊操作,但由于数据已经丢失,因此永远无法使您进入原始状态.因此,根据情况 - 逻辑逆向操作的可能性及其可行性,您需要在这两大类中进行选择,然后以您希望的方式实现它们.当然,有可能采用适合您的混合策略.

此外,有时候,就像在Gmail中一样,时间限制撤消是可能的,因为动作(发送邮件)从未在第一时间完成.所以,你不是在那里"撤消",你只是"不做"行动本身.

  • 有时保持状态和"前进"动作的混合可能会有所帮助.作为一个简单的方法,如果一个人保持着"重大保存状态"每隔5个行动,而最后的"大保存状态"后,还不停地保存状态,一个可以做第几个通过恢复保存状态撤消操作,以及一个可以做通过重复上一次主要保存中的4个动作来进行下一步 一种更通用的方法是对不同级别的保存状态使用二次幂级数,因此需要使用O(1)前向迭代来存储用于N级撤消的lg(N)保存状态. (6认同)

And*_*and 15

我从头开始编写了两个文本编辑器,它们都采用了非常原始的撤消/重做功能.通过"原始",我的意思是功能非常容易实现,但在非常大的文件中(例如>> 10 MB)它是不经济的.但是,该系统非常灵活; 例如,它支持无限级别的撤消.

基本上,我定义了一个类似的结构

type
  TUndoDataItem = record
    text: /array of/ string;
    selBegin: integer;
    selEnd: integer;
    scrollPos: TPoint;
  end;
Run Code Online (Sandbox Code Playgroud)

然后定义一个数组

var
  UndoData: array of TUndoDataItem;
Run Code Online (Sandbox Code Playgroud)

然后,此数组的每个成员都指定文本的已保存状态.现在,在每次编辑文本时(字符键向下,退格键,删除键,剪切/粘贴,鼠标移动选择等),我(重新)启动一个(比如说)一秒的计时器.触发时,计时器将当前状态保存为UndoData阵列的新成员.

在撤消(Ctrl + Z)时,我将编辑器恢复到状态UndoData[UndoLevel - 1]并减少UndoLevel一个.默认情况下,UndoLevel等于UndoData数组的最后一个成员的索引.在重做(Ctrl + Y或Shift + Ctrl + Z)时,我将编辑器恢复到状态UndoData[UndoLevel + 1]并增加UndoLevel1.当然,如果在UndoLevel不等于UndoData数组的长度(减去1)时触发编辑计时器,我会清除此数组中的所有项目,这UndoLevel在Microsoft Windows中很常见(但如果我没记错的话,Emacs会更好 - - Microsoft Windows方法的缺点是,如果您撤消了大量更改,然后意外地编辑了缓冲区,那么前置内容(即未删除的内容)将永久丢失.您可能希望跳过此数组的减少.

在不同类型的程序中,例如,图像编辑器,可以应用相同的技术,但是当然,具有完全不同的UndoDataItem结构.更高级的方法,不需要太多的内存,只保存撤消级别之间的更改(即,而不是保存"alpha \nbeta\gamma"和"alpha \nbeta \ngamma \ndelta",你可以如果你明白我的意思,保存"alpha \nbeta \ngamma"和"ADD \ndelta".在非常大的文件中,每个更改与文件大小相比较小,这将大大降低撤消数据的内存使用量,但实现起来比较棘手,并且可能更容易出错.


Mau*_*ijk 13

有几种方法可以做到这一点,但您可以开始查看Command模式.使用命令列表通过您的操作返回(撤消)或转发(重做).可以在此处找到C#中的示例.


ARn*_*Rno 9

实现基本撤消/重做功能的一种方法是使用备忘录和命令设计模式。

例如, Memento旨在保留对象的状态以便稍后恢复。出于优化目的,该备忘录应该尽可能小。

命令模式将一些指令封装在一个对象命令)中,以便在需要时执行。

基于这两个概念,您可以编写基本的撤消/重做历史记录,如以下用 TypeScript 编码的历史记录(从前端库Interacto中提取和改编)。

这样的历史依赖于两个堆栈:

  • 可以撤消的对象的堆栈
  • 可以重做的对象的堆栈

算法中提供了注释。请注意,在撤消操作中,必须清除重做堆栈!原因是让应用程序处于稳定状态:如果你回到过去重做你所做的某些操作,那么当你改变未来时,你以前的操作将不再存在。

    export class UndoHistory {
        /** The undoable objects. */
        private readonly undos: Array<Undoable>;
    
        /** The redoable objects. */
        private readonly redos: Array<Undoable>;
    
        /** The maximal number of undo. */
        private sizeMax: number;
    
        public constructor() {
            this.sizeMax = 0;
            this.undos = [];
            this.redos = [];
            this.sizeMax = 30;
        }
    
        /** Adds an undoable object to the collector. */
        public add(undoable: Undoable): void {
            if (this.sizeMax > 0) {
                // Cleaning the oldest undoable object
                if (this.undos.length === this.sizeMax) {
                    this.undos.shift();
                }
    
                this.undos.push(undoable);
                // You must clear the redo stack!
                this.clearRedo();
            }
        }
    
        private clearRedo(): void {
            if (this.redos.length > 0) {
                this.redos.length = 0;
            }
        }
    
        /** Undoes the last undoable object. */
        public undo(): void {
            const undoable = this.undos.pop();
            if (undoable !== undefined) {
                undoable.undo();
                this.redos.push(undoable);
            }
        }
    
        /** Redoes the last undoable object. */
        public redo(): void {
            const undoable = this.redos.pop();
            if (undoable !== undefined) {
                undoable.redo();
                this.undos.push(undoable);
            }
        }
    }

Run Code Online (Sandbox Code Playgroud)

界面Undoable非常简单:

    export interface Undoable {
        /** Undoes the command */
        undo(): void;
        /** Redoes the undone command */
        redo(): void;
    }
Run Code Online (Sandbox Code Playgroud)

您现在可以编写在您的应用程序上运行的可撤消命令。

例如(仍然基于 Interacto 示例),您可以编写如下命令:

    export class ClearTextCmd implements Undoable {
       // The memento that saves the previous state of the text data
       private memento: string;
    
       public constructor(private text: TextData) {}
       
       // Executes the command
       public execute() void {
         // Creating the memento
         this.memento = this.text.text;
         // Applying the changes (in many 
         // cases do and redo are similar, but the memento creation)
         redo();
       }
    
       public undo(): void {
         this.text.text = this.memento;
       }
    
       public redo(): void {
         this.text.text = '';
       }
    }
Run Code Online (Sandbox Code Playgroud)

您现在可以执行命令并将其添加到 UndoHistory 实例中:

    const cmd = new ClearTextCmd(...);
    //...
    undoHistory.add(cmd);
Run Code Online (Sandbox Code Playgroud)

最后,您可以将撤消按钮(或快捷方式)绑定到此历史记录(重做也是如此)。

Interacto 文档页面上详细介绍了此类示例。

编辑:

请注意,存在多种撤消/重做算法。我详细介绍了经典的线性模型。对于代码编辑器,研究人员提出了“选择性撤消算法” (研究文章)(“Supporting Selective Undo in a Code Editor”,Yoon 等人)。用于协作编辑的撤消/重做算法也是特定的(研究文章)(“协作系统中撤消操作的框架”,Prakash 等人)。


sla*_*ais 7

有点晚了,但是这里有:你特意指的是文本编辑器,下面解释了一个算法,可以适应你正在编辑的任何东西.所涉及的原则是保留可以自动化的动作/指令列表,以重新创建您所做的每个更改.不要对原始文件进行更改(如果不是空的),请将其保留为备份.

保留对原始文件所做更改的前向 - 后向链接列表.此列表会间歇性地保存到临时文件中,直到用户实际保存更改:发生这种情况时,您将更改应用于新文件,复制旧文件并同时应用更改; 然后将原始文件重命名为备份,并将新文件的名称更改为正确的名称.(您可以保留已保存的更改列表,也可以将其删除并替换为后续的更改列表.)

链表中的每个节点都包含以下信息:

  • 更改类型:您要么插入数据,要么删除数据:"更改"数据意味着a delete后跟一个insert
  • 文件中的位置:可以是偏移量或行/列对
  • 数据缓冲区:这是与动作有关的数据; 如果insert是插入的数据; 如果delete,删除的数据.

要实现Undo,您可以使用"当前节点"指针或索引从链接列表的尾部向后工作:在更改的位置insert,您执行删除但不更新链接列表; 如果是delete,则从数据中插入链表缓冲区中的数据.为用户的每个"撤消"命令执行此操作.Redo向前移动'current-node'指针并根据节点执行更改.如果用户在撤消后对代码进行更改,请将"当前节点"指示符后的所有节点删除到尾部,并将尾部设置为等于"当前节点"指示符.然后在尾部之后插入用户的新更改.这就是它.


Viv*_*ajh 5

备忘录模式为这个做。

在自己实现之前,请注意这是很常见的,并且代码已经存在 - 例如,如果您在 .Net 中编码,则可以使用IEditableObject,而在 javascript 世界中,您可以使用不可变库,如immer.js


小智 5

我仅有的两分钱是,您需要使用两个堆栈来跟踪操作。每次用户执行某些操作时,您的程序都应将这些操作放在“执行的”堆栈上。当用户想要撤消那些操作时,只需将操作从“执行”堆栈弹出到“调用”堆栈即可。当用户想要重做这些操作时,请从“调用”堆栈中弹出项目并将其推回到“执行”堆栈中。

希望能帮助到你。