Implementación de deshacer / rehacer

Déme algunas ideas sobre cómo implementar la funcionalidad de deshacer / rehacer, como lo tenemos en los editores de texto. ¿Qué algoritmos debo usar y qué puedo leer? Gracias.

Conozco dos divisiones principales de los tipos de deshacer

• GUARDAR ESTADO: Una categoría de deshacer es donde realmente guarda los estados del historial. En este caso lo que sucede es que en cada punto sigues guardando el estado en alguna ubicación de la memoria. Cuando desee deshacer, simplemente cambie el estado actual y cambie el estado que ya estaba en la memoria. Así es como se hace con Historial en Adobe Photoshop o reabriendo pestañas cerradas en Google Chrome, por ejemplo.

• GENERAR ESTADO: La otra categoría es donde en lugar de mantener los estados en sí, simplemente recuerdas cuáles fueron las acciones. cuando necesita deshacer, necesita hacer un reverso lógico de esa acción en particular. Por ejemplo, cuando hace un Ctrl+ Ben algún editor de texto que admita deshacer, se recuerda como una acción en negrita . Ahora con cada acción hay un mapeo de sus reveses lógicos. Entonces, cuando haces un Ctrl+ Z, busca en una tabla de acciones inversas y encuentra que la acción de deshacer es un Ctrl+ Bnuevamente. Eso se realiza y obtienes tu estado anterior. Entonces, aquí su estado anterior no se almacenó en la memoria, sino que se generó cuando lo necesitaba.

Para los editores de texto, generar el estado de esta manera no requiere demasiada computación, pero para programas como Adobe Photoshop, puede ser demasiado computacionalmente intensivo o simplemente imposible. Por ejemplo, para una acción de Desenfocar , especificará una acción de Desenfocar , pero eso nunca puede llevarlo al estado original porque los datos ya se han perdido. Entonces, dependiendo de la situación, la posibilidad de una acción lógica inversa y la viabilidad de la misma, debe elegir entre estas dos categorías amplias y luego implementarlas de la manera que desee. Por supuesto, es posible tener una estrategia híbrida que funcione para usted.

Además, a veces, como en Gmail, es posible deshacer un tiempo limitado porque la acción (enviar el correo) nunca se realiza en primer lugar. Por lo tanto, no está "deshaciendo" allí, simplemente "no está haciendo" la acción en sí.

He escrito dos editores de texto desde cero, y ambos emplean una forma muy primitiva de funcionalidad de deshacer / rehacer. Por "primitivo", me refiero a que la funcionalidad fue muy fácil de implementar, pero que no es económica en archivos muy grandes (digamos >> 10 MB). Sin embargo, el sistema es muy flexible; por ejemplo, admite niveles ilimitados de deshacer.

Básicamente, defino una estructura como

type
  TUndoDataItem = record
    text: /array of/ string;
    selBegin: integer;
    selEnd: integer;
    scrollPos: TPoint;
  end;

y luego definir una matriz

var
  UndoData: array of TUndoDataItem;

Luego, cada miembro de esta matriz especifica un estado guardado del texto. Ahora, en cada edición del texto (tecla de carácter hacia abajo, retroceso hacia abajo, tecla de eliminación hacia abajo, cortar / pegar, selección movida con el mouse, etc.), (re) inicio un temporizador de (digamos) un segundo. Cuando se activa, el temporizador guarda el estado actual como un nuevo miembro de la UndoDatamatriz.

Al deshacer (Ctrl + Z), restauro el editor al estado UndoData[UndoLevel - 1]y lo reduzco UndoLevelen uno. De forma predeterminada, UndoLeveles igual al índice del último miembro de la UndoDatamatriz. Al rehacer (Ctrl + Y o Shift + Ctrl + Z), restauro el editor al estado UndoData[UndoLevel + 1]y lo aumento UndoLevelen uno. Por supuesto, si el temporizador de edición se activa cuando UndoLevelno es igual a la longitud (menos uno) de la UndoDatamatriz, borro todos los elementos de esta matriz después UndoLevel, como es común en la plataforma Microsoft Windows (pero Emacs es mejor, si mal no recuerdo correctamente: la desventaja del enfoque de Microsoft Windows es que, si deshace muchos cambios y luego edita accidentalmente el búfer, el contenido anterior (que se deshizo) se pierde permanentemente). Es posible que desee omitir esta reducción de la matriz.

En un tipo de programa diferente, por ejemplo, un editor de imágenes, se puede aplicar la misma técnica, pero, por supuesto, con una UndoDataItemestructura completamente diferente . Un enfoque más avanzado, que no requiere tanta memoria, es guardar solo los cambios entre los niveles de deshacer (es decir, en lugar de guardar "alpha \ nbeta \ gamma" y "alpha \ nbeta \ ngamma \ ndelta", podrías guarda "alpha \ nbeta \ ngamma" y "AGREGAR \ ndelta", si ves lo que quiero decir). En archivos muy grandes donde cada cambio es pequeño en comparación con el tamaño del archivo, esto disminuirá en gran medida el uso de memoria de los datos de deshacer, pero es más complicado de implementar y posiblemente más propenso a errores.

Hay varias formas de hacer esto, pero puede comenzar a mirar el patrón Command . Utilice una lista de comandos para retroceder (deshacer) o avanzar (rehacer) a través de sus acciones. Puede encontrar un ejemplo en C # aquí .

Un poco tarde, pero aquí va: se refiere específicamente a los editores de texto, lo que sigue explica un algoritmo que se puede adaptar a lo que sea que esté editando. El principio involucrado es mantener una lista de acciones / instrucciones que se pueden automatizar para recrear cada cambio realizado. No realice cambios en el archivo original (si no está vacío), consérvelo como copia de seguridad.

Mantenga una lista vinculada hacia adelante y hacia atrás de los cambios que realice en el archivo original. Esta lista se guarda intermitentemente en un archivo temporal, hasta que el usuario realmente guarda los cambios: cuando esto sucede, aplica los cambios a un nuevo archivo, copia el antiguo y aplica simultáneamente los cambios; luego cambie el nombre del archivo original a una copia de seguridad y cambie el nombre del nuevo archivo por el nombre correcto. (Puede conservar la lista de cambios guardada o eliminarla y reemplazarla con una lista posterior de cambios).

Cada nodo de la lista vinculada contiene la siguiente información:

• tipo de cambio: o inserta datos o borra datos: "cambiar" datos significa un deleteseguido de uninsert
• posición en el archivo: puede ser un desplazamiento o un par de línea / columna
• búfer de datos: estos son los datos involucrados con la acción; si insertson los datos que se insertaron; si delete, los datos que se eliminaron.

Para implementarlo Undo, trabaje hacia atrás desde la cola de la lista vinculada, usando un puntero o índice de 'nodo actual': donde estaba el cambio insert, realiza una eliminación pero sin actualizar la lista vinculada; y donde estaba delete, inserta los datos de los datos en el búfer de lista vinculada. Haga esto para cada comando 'Deshacer' del usuario. Redomueve el puntero 'current-node' hacia adelante y ejecuta el cambio según el nodo. Si el usuario realiza un cambio en el código después de deshacerlo, elimine todos los nodos después del indicador 'actual-nodo' en la cola, y establezca la cola igual al indicador 'actual-nodo'. Los nuevos cambios del usuario se insertan después de la cola. Y eso es todo.

Mi único dos centavos es que querría usar dos pilas para realizar un seguimiento de las operaciones. Cada vez que el usuario realiza algunas operaciones, su programa debe poner esas operaciones en una pila "realizada". Cuando el usuario quiera deshacer esas operaciones, simplemente extraiga las operaciones de la pila "realizada" a una pila de "recuperación". Cuando el usuario quiera rehacer esas operaciones, saque elementos de la pila de "recuperación" y devuélvalos a la pila "realizada".

Espero eso ayude.

Si las acciones son reversibles. por ejemplo, agregando 1, hacer que un jugador se mueva, etc., vea cómo usar el patrón de comando para implementar deshacer / rehacer . Siga el enlace y encontrará ejemplos detallados sobre cómo hacerlo.

De lo contrario, use el estado guardado como lo explica @Lazer.

Puede estudiar un ejemplo de un marco de deshacer / rehacer existente, el primer éxito de Google está en codeplex (para .NET) . No sé si eso es mejor o peor que cualquier otro marco, hay muchos.

Si su objetivo es tener la funcionalidad de deshacer / rehacer en su aplicación, también puede elegir un marco existente que parezca adecuado para su tipo de aplicación.
Si desea aprender cómo crear su propio deshacer / rehacer, puede descargar el código fuente y echar un vistazo a ambos patrones y los detalles de cómo conectar las cosas.

El patrón Memento se hizo para esto.

Antes de implementar esto usted mismo, tenga en cuenta que esto es bastante común y que el código ya existe. Por ejemplo, si está codificando en .Net, puede usar IEditableObject .

Además de la discusión, escribí una publicación de blog sobre cómo implementar UNDO y REDO basado en pensar en lo que es intuitivo: http://adamkulidjian.com/undo-and-redo.html

Una forma de implementar una función básica de deshacer / rehacer es utilizar los patrones de diseño de comandos y de recuerdo.

Memento tiene como objetivo mantener el estado de un objeto para restaurarlo más tarde, por ejemplo. Este recuerdo debe ser lo más pequeño posible con fines de optimización.

El patrón de comando encapsula en un objeto (un comando) algunas instrucciones para ejecutar cuando sea necesario.

Con base en estos dos conceptos, puede escribir un historial básico de deshacer / rehacer, como el siguiente codificado en TypeScript ( extraído y adaptado de la biblioteca front-end Interacto ).

Tal historia se basa en dos pilas:

• la pila de objetos que se pueden deshacer
• la pila de objetos que se pueden rehacer

Los comentarios se proporcionan dentro del algoritmo. ¡Solo tenga en cuenta que en una operación de deshacer, la pila de rehacer debe borrarse! La razón es dejar la aplicación en un estado estable: si regresa al pasado para rehacer algunas acciones que realizó, sus acciones anteriores no existirán más a medida que cambie el futuro.

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.pop();
            }

            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);
        }
    }
}

La Undoableinterfaz es bastante simple:

export interface Undoable {
    /** Undoes the command */
    undo(): void;
    /** Redoes the undone command */
    redo(): void;
}

Ahora puede escribir comandos que se pueden deshacer que operan en su aplicación.

Por ejemplo (todavía basado en ejemplos de Interacto), puede escribir un comando como este:

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 = '';
   }
}

Ahora puede ejecutar y agregar el comando a la instancia de UndoHistory:

const cmd = new ClearTextCmd(...);
//...
undoHistory.add(cmd);

Finalmente, puede vincular un botón de deshacer (o un atajo) a este historial (lo mismo para rehacer).

Estos ejemplos se detallan en la página de documentación de Interacto .