algorithm - revertir - Deshacer/Rehacer la implementación

teclas para rehacer

Question

Dame algunas ideas sobre cómo implementar la funcionalidad deshacer / rehacer, como en los editores de texto. ¿Qué algoritmos debería usar y qué puedo leer? Gracias.

Answer 1

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 ocurre es que en cada punto se guarda el estado en alguna ubicación de la memoria. Cuando desee deshacer, simplemente cambie el estado actual e intercambie el estado que ya estaba allí 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 ellos mismos, simplemente recuerdas cuáles fueron las acciones. cuando necesite deshacer, debe hacer un reverso lógico de esa acción en particular. Para un ejemplo simple, cuando haces Ctrl + B en algún editor de texto que admite deshacer, se lo recuerda como una acción en negrita . Ahora con cada acción hay un mapeo de sus reversos lógicos. Entonces, cuando haces Ctrl + Z , mira hacia arriba desde una tabla de acciones inversas y encuentra que la acción de deshacer nuevamente es Ctrl + B. Eso se realiza y obtienes tu estado anterior. Por lo tanto, aquí su estado anterior no se almacenó en la memoria sino que se generó cuando lo necesitó.

Para los editores de texto, generar el estado de esta manera no es demasiado intensivo en cómputo, pero para programas como Adobe Photoshop, podría ser demasiado intensivo computacionalmente o simplemente imposible. Por ejemplo, para una acción Blur , especificará una acción de desenfoque , pero eso nunca podrá llevarlo al estado original porque los datos ya están perdidos. Entonces, dependiendo de la situación, la posibilidad de una acción inversa lógica y la viabilidad de la misma, debe elegir entre estas dos amplias categorías 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. Entonces, no estás "deshaciendo" allí, simplemente estás "no haciendo" la acción misma.

Answer 2

El patrón de Memento fue hecho para esto.

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

Answer 3

Hay varias formas de hacerlo, pero podría comenzar a observar el patrón de Comando . Use una lista de comandos para retroceder (Deshacer) o reenviar (rehacer) a través de sus acciones. Un ejemplo en C # se puede encontrar here .

Answer 4

He escrito dos editores de texto desde cero, y ambos emplean una forma muy primitiva de funcionalidad de deshacer / rehacer. Por "primitivo", quiero decir que la funcionalidad fue muy fácil de implementar, pero que no es rentable 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 caracteres hacia abajo, retroceso hacia abajo, eliminar tecla hacia abajo, cortar / pegar, selección movida por el mouse, etc.), inicio (reinicie) un temporizador de (digamos) un segundo. Cuando se activa, el temporizador guarda el estado actual como un nuevo miembro de la matriz UndoData .

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

En un tipo diferente de programa, por ejemplo, un editor de imágenes, se puede aplicar la misma técnica, pero, por supuesto, con una estructura UndoDataItem 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 "alfa / nbeta / gamma" y "alfa / nbeta / ngamma / ndelta", podría guarda "alpha / nbeta / ngamma" y "ADD / 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 la memoria de los datos de deshacer, pero es más complicado de implementar, y posiblemente más propenso a errores.

Answer 5

Mi único punto es que le gustaría usar dos pilas para hacer 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 desea deshacer esas operaciones, simplemente abre operaciones de la pila "realizada" a una pila de "recuperación". Cuando el usuario quiera volver a hacer esas operaciones, extraiga los elementos de la pila de "recuperación" y vuelva a colocarlos en la pila "realizada".

Espero eso ayude.

Answer 6

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

Si su objetivo es tener funcionalidad de deshacer / rehacer en su aplicación, también puede elegir un marco existente que se adecúe a su tipo de aplicación.
Si quieres aprender a construir tu propio deshacer / rehacer, puedes descargar el código fuente y echar un vistazo a ambos patrones y a los detalles de cómo configurarlo.

Answer 7

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

De lo contrario, use Saved State como se explica en @Lazer.

Answer 8

Un poco tarde, pero aquí va: específicamente se refiere 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 puedan automatizarse para recrear cada cambio que haya realizado. No realice cambios en el archivo original (si no está vacío), guárdelo como una copia de seguridad.

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

Cada nodo en la lista enlazada contiene la siguiente información:

• tipo de cambio: inserta datos o elimina datos: para "cambiar" los datos significa una delete seguida de un insert
• posición en el archivo: puede ser un desplazamiento o un par de línea / columna
• búfer de datos: esta es la información involucrada con la acción; si insert , son los datos que se insertaron; si delete , los datos que se eliminaron.

Para implementar Undo , trabaje hacia atrás desde la cola de la lista enlazada, usando un puntero o índice ''nodo actual'': donde el cambio fue insert , usted realiza una eliminación pero sin actualizar la lista enlazada; y donde era un delete , insertas los datos de los datos en el buffer de la lista enlazada. Haga esto para cada comando ''Deshacer'' del usuario. Redo mueve el puntero ''actual-node'' hacia adelante y ejecuta el cambio según el nodo. Si el usuario realiza un cambio en el código después de deshacer, elimine todos los nodos después del indicador ''current-node'' hasta la cola, y configure la cola igual al indicador ''current-node''. Los nuevos cambios del usuario se insertan después de la cola. Y eso es todo.