use*_*352 64 algorithm design-patterns
给我一些想法如何实现撤消/重做功能 - 就像我们在文本编辑器中一样.我应该使用哪些算法以及我可能阅读的内容.谢谢.
Laz*_*zer 76
我知道撤消类型的两个主要部分

对于文本编辑器,以这种方式生成状态并不是计算密集型,但对于像Adobe Photoshop这样的程序,它可能过于计算密集或者根本不可能.例如 - 对于模糊操作,您将指定一个去模糊操作,但由于数据已经丢失,因此永远无法使您进入原始状态.因此,根据情况 - 逻辑逆向操作的可能性及其可行性,您需要在这两大类中进行选择,然后以您希望的方式实现它们.当然,有可能采用适合您的混合策略.
此外,有时候,就像在Gmail中一样,时间限制撤消是可能的,因为动作(发送邮件)从未在第一时间完成.所以,你不是在那里"撤消",你只是"不做"行动本身.
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".在非常大的文件中,每个更改与文件大小相比较小,这将大大降低撤消数据的内存使用量,但实现起来比较棘手,并且可能更容易出错.
实现基本撤消/重做功能的一种方法是使用备忘录和命令设计模式。
例如, 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 等人)。
有点晚了,但是这里有:你特意指的是文本编辑器,下面解释了一个算法,可以适应你正在编辑的任何东西.所涉及的原则是保留可以自动化的动作/指令列表,以重新创建您所做的每个更改.不要对原始文件进行更改(如果不是空的),请将其保留为备份.
保留对原始文件所做更改的前向 - 后向链接列表.此列表会间歇性地保存到临时文件中,直到用户实际保存更改:发生这种情况时,您将更改应用于新文件,复制旧文件并同时应用更改; 然后将原始文件重命名为备份,并将新文件的名称更改为正确的名称.(您可以保留已保存的更改列表,也可以将其删除并替换为后续的更改列表.)
链表中的每个节点都包含以下信息:
delete后跟一个insertinsert是插入的数据; 如果delete,删除的数据.要实现Undo,您可以使用"当前节点"指针或索引从链接列表的尾部向后工作:在更改的位置insert,您执行删除但不更新链接列表; 如果是delete,则从数据中插入链表缓冲区中的数据.为用户的每个"撤消"命令执行此操作.Redo向前移动'current-node'指针并根据节点执行更改.如果用户在撤消后对代码进行更改,请将"当前节点"指示符后的所有节点删除到尾部,并将尾部设置为等于"当前节点"指示符.然后在尾部之后插入用户的新更改.这就是它.
该备忘录模式为这个做。
在自己实现之前,请注意这是很常见的,并且代码已经存在 - 例如,如果您在 .Net 中编码,则可以使用IEditableObject,而在 javascript 世界中,您可以使用不可变库,如immer.js。
小智 5
我仅有的两分钱是,您需要使用两个堆栈来跟踪操作。每次用户执行某些操作时,您的程序都应将这些操作放在“执行的”堆栈上。当用户想要撤消那些操作时,只需将操作从“执行”堆栈弹出到“调用”堆栈即可。当用户想要重做这些操作时,请从“调用”堆栈中弹出项目并将其推回到“执行”堆栈中。
希望能帮助到你。