Implementierung rückgängig machen / wiederholen

Geben Sie mir einige Gedanken darüber, wie Sie die Rückgängig- / Wiederherstellungsfunktion implementieren können - wie wir es in Texteditoren getan haben. Welche Algorithmen soll ich verwenden und was darf ich lesen? Vielen Dank.

Ich kenne zwei Hauptabteilungen der Arten von Rückgängigmachungen

• STATE SPEICHERN: In einer Kategorie des Rückgängigmachens speichern Sie tatsächlich Verlaufszustände. In diesem Fall speichern Sie den Status an jedem Punkt an einem bestimmten Speicherort. Wenn Sie ein Rückgängigmachen durchführen möchten, tauschen Sie einfach den aktuellen Status aus und tauschen den Status aus, der bereits im Speicher vorhanden war. So wird es beispielsweise mit dem Verlauf in Adobe Photoshop oder dem erneuten Öffnen geschlossener Registerkarten in Google Chrome gemacht.

• GENERATE STATE: In der anderen Kategorie erinnern Sie sich, anstatt die Zustände selbst beizubehalten, nur an die Aktionen. Wenn Sie rückgängig machen müssen, müssen Sie diese bestimmte Aktion logisch umkehren. Wenn Sie beispielsweise in einem Texteditor, der Rückgängigmachungen unterstützt, ein Ctrl+ Bausführen, wird dies als fett gedruckte Aktion gespeichert . Jetzt ist mit jeder Aktion eine Zuordnung ihrer logischen Umkehrungen. Wenn Sie also ein Ctrl+ Zausführen, wird von einer Tabelle mit inversen Aktionen nachgeschlagen und festgestellt, dass die Rückgängig-Aktion wieder ein Ctrl+ ist B. Das wird durchgeführt und Sie erhalten Ihren vorherigen Zustand. Hier wurde Ihr vorheriger Status also nicht im Speicher gespeichert, sondern bei Bedarf generiert.

Für Texteditoren ist das Generieren des Status auf diese Weise nicht zu rechenintensiv, für Programme wie Adobe Photoshop jedoch möglicherweise zu rechenintensiv oder einfach unmöglich. Beispiel: Für eine Unschärfeaktion geben Sie eine De-Blur- Aktion an, die Sie jedoch niemals in den ursprünglichen Zustand zurückversetzen kann, da die Daten bereits verloren gehen. Abhängig von der Situation - der Möglichkeit einer logischen umgekehrten Aktion und deren Durchführbarkeit - müssen Sie zwischen diesen beiden allgemeinen Kategorien wählen und sie dann nach Ihren Wünschen implementieren. Natürlich ist es möglich, eine hybride Strategie zu haben, die für Sie funktioniert.

Außerdem ist manchmal, wie in Google Mail, ein zeitlich begrenztes Rückgängigmachen möglich, da die Aktion (Senden der E-Mail) überhaupt nicht ausgeführt wird. Sie "machen" dort also nicht "rückgängig", sondern "machen" nur die Aktion selbst nicht.

Ich habe zwei Texteditoren von Grund auf neu geschrieben, und beide verwenden eine sehr primitive Form der Rückgängig- / Wiederherstellungsfunktionalität. Mit "primitiv" meine ich, dass die Funktionalität sehr einfach zu implementieren war, aber in sehr großen Dateien (z. B. >> 10 MB) unwirtschaftlich ist. Das System ist jedoch sehr flexibel; Beispielsweise werden unbegrenzte Ebenen des Rückgängigmachens unterstützt.

Grundsätzlich definiere ich eine Struktur wie

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

und definieren Sie dann ein Array

var
  UndoData: array of TUndoDataItem;

Dann gibt jedes Mitglied dieses Arrays einen gespeicherten Status des Textes an. Jetzt starte ich bei jeder Bearbeitung des Textes (Zeichentaste nach unten, Rücktaste nach unten, Löschtaste nach unten, Ausschneiden / Einfügen, Auswahl mit der Maus usw.) einen Timer von (sagen wir) einer Sekunde (neu). Beim Auslösen speichert der Timer den aktuellen Status als neues Mitglied des UndoDataArrays.

Beim Rückgängigmachen (Strg + Z) stelle ich den Zustand des Editors wieder her UndoData[UndoLevel - 1]und verkleinere ihn UndoLevelum eins. Standardmäßig UndoLevelentspricht dies dem Index des letzten Mitglieds des UndoDataArrays. Beim Wiederherstellen (Strg + Y oder Umschalt + Strg + Z) stelle ich den Zustand des Editors wieder her UndoData[UndoLevel + 1]und erhöhe ihn UndoLevelum eins. Wenn der Bearbeitungszeitgeber ausgelöst wird, wenn er UndoLevelnicht der Länge (minus eins) des UndoDataArrays entspricht, lösche ich natürlich alle Elemente dieses Arrays danach UndoLevel, wie es auf der Microsoft Windows-Plattform üblich ist (aber Emacs ist besser, wenn ich mich recht erinnere Richtig - Der Nachteil des Microsoft Windows-Ansatzes besteht darin, dass der vorherige Inhalt (der rückgängig gemacht wurde) dauerhaft verloren geht, wenn Sie viele Änderungen rückgängig machen und dann versehentlich den Puffer bearbeiten. Möglicherweise möchten Sie diese Reduzierung des Arrays überspringen.

In einem anderen Programmtyp, beispielsweise einem Bildeditor, kann dieselbe Technik angewendet werden, jedoch natürlich mit einer völlig anderen UndoDataItemStruktur. Ein fortgeschrittener Ansatz, der nicht so viel Speicher benötigt, besteht darin, nur die Änderungen zwischen den Rückgängig-Ebenen zu speichern (dh anstatt "alpha \ nbeta \ gamma" und "alpha \ nbeta \ ngamma \ ndelta" zu speichern, können Sie dies tun Speichern Sie "alpha \ nbeta \ ngamma" und "ADD \ ndelta", wenn Sie sehen, was ich meine. In sehr großen Dateien, in denen jede Änderung im Vergleich zur Dateigröße klein ist, wird die Speichernutzung der rückgängig gemachten Daten erheblich verringert, die Implementierung ist jedoch schwieriger und möglicherweise fehleranfälliger.

Es gibt verschiedene Möglichkeiten, dies zu tun, aber Sie können sich das Befehlsmuster ansehen . Verwenden Sie eine Liste von Befehlen, um durch Ihre Aktionen zurück (Rückgängig) oder vorwärts (Wiederherstellen) zu gehen. Ein Beispiel in C # finden Sie hier .

Ein bisschen spät, aber hier ist es: Sie beziehen sich speziell auf Texteditoren. Im Folgenden wird ein Algorithmus erläutert, der an das angepasst werden kann, was Sie gerade bearbeiten. Das Prinzip besteht darin, eine Liste von Aktionen / Anweisungen zu führen, die automatisiert werden können, um jede von Ihnen vorgenommene Änderung neu zu erstellen. Nehmen Sie keine Änderungen an der Originaldatei vor (falls diese nicht leer ist), sondern bewahren Sie sie als Backup auf.

Führen Sie eine vorwärts-rückwärts verknüpfte Liste der Änderungen, die Sie an der Originaldatei vornehmen. Diese Liste wird zeitweise in einer temporären Datei gespeichert, bis der Benutzer die Änderungen tatsächlich speichert : In diesem Fall wenden Sie die Änderungen auf eine neue Datei an, kopieren die alte und übernehmen gleichzeitig die Änderungen. Benennen Sie dann die Originaldatei in eine Sicherung um und ändern Sie den Namen der neuen Datei in den richtigen Namen. (Sie können die gespeicherte Änderungsliste entweder behalten oder löschen und durch eine nachfolgende Änderungsliste ersetzen.)

Jeder Knoten in der verknüpften Liste enthält die folgenden Informationen:

• Art der Änderung: Sie fügen entweder Daten ein oder Sie löschen Daten: Daten zu "ändern" bedeutet a deletegefolgt von eineminsert
• Position in Datei: kann ein Versatz oder ein Zeilen- / Spaltenpaar sein
• Datenpuffer: Dies sind die Daten, die an der Aktion beteiligt sind. wenn insertes die Daten sind, die eingefügt wurden; if delete, die Daten, die gelöscht wurden.

Zum Implementieren arbeiten UndoSie vom Ende der verknüpften Liste aus mit einem Zeiger oder Index für den aktuellen Knoten rückwärts: Wo sich die Änderung befand insert, führen Sie einen Löschvorgang durch, ohne jedoch die verknüpfte Liste zu aktualisieren. und wo es sich befand delete, fügen Sie die Daten aus den Daten in den Puffer für verknüpfte Listen ein. Tun Sie dies für jeden 'Rückgängig'-Befehl des Benutzers. RedoBewegt den Zeiger 'aktueller Knoten' nach vorne und führt die Änderung gemäß dem Knoten aus. Sollte der Benutzer nach dem Rückgängigmachen eine Änderung am Code vornehmen, löschen Sie alle Knoten nach dem Indikator "Aktueller Knoten" am Ende und setzen Sie den Schwanz gleich dem Indikator "Aktueller Knoten". Die neuen Änderungen des Benutzers werden dann nach dem Schwanz eingefügt. Und das war's auch schon.

Meine einzigen zwei Cent sind, dass Sie zwei Stapel verwenden möchten, um die Operationen zu verfolgen. Jedes Mal, wenn der Benutzer einige Operationen ausführt, sollte Ihr Programm diese Operationen auf einen "ausgeführten" Stapel legen. Wenn der Benutzer diese Vorgänge rückgängig machen möchte, fügen Sie einfach Vorgänge vom "ausgeführten" Stapel in einen "Rückruf" -Stapel ein. Wenn der Benutzer diese Vorgänge wiederholen möchte, fügen Sie Elemente aus dem Stapel "Rückruf" hinzu und verschieben Sie sie zurück in den Stapel "Durchgeführt".

Ich hoffe es hilft.

Wenn die Aktionen umkehrbar sind. Beispiel: Hinzufügen von 1, Bewegen eines Spielers usw. Sehen Sie, wie Sie mit dem Befehlsmuster Rückgängig / Wiederherstellen implementieren . Folgen Sie dem Link, um detaillierte Beispiele zu finden.

Wenn nicht, verwenden Sie den gespeicherten Status, wie von @Lazer erläutert.

Sie können ein Beispiel für ein vorhandenes Undo / Redo-Framework studieren. Der erste Google-Treffer ist Codeplex (für .NET) . Ich weiß nicht, ob das besser oder schlechter ist als jedes andere Framework, es gibt viele davon.

Wenn Sie eine Rückgängig- / Wiederherstellungsfunktion in Ihrer Anwendung haben möchten, können Sie auch einfach ein vorhandenes Framework auswählen, das für Ihre Art von Anwendung geeignet ist.
Wenn Sie lernen möchten, wie Sie Ihr eigenes Rückgängigmachen / Wiederherstellen erstellen, können Sie den Quellcode herunterladen und sich sowohl die Muster als auch die Details zum Verkabeln ansehen.

Das Memento-Muster wurde dafür gemacht.

Beachten Sie, dass dies häufig vorkommt und bereits vorhandener Code vorhanden ist. Wenn Sie beispielsweise in .Net codieren, können Sie IEditableObject verwenden .

Als Ergänzung zur Diskussion schrieb ich einen Blog-Beitrag über die Implementierung von UNDO und REDO, indem ich darüber nachdachte, was intuitiv ist: http://adamkulidjian.com/undo-and-redo.html

Eine Möglichkeit, eine grundlegende Funktion zum Rückgängigmachen / Wiederherstellen zu implementieren, besteht darin, sowohl das Erinnerungs- als auch das Befehlsentwurfsmuster zu verwenden.

Memento zielt darauf ab, den Zustand eines Objekts beizubehalten, das beispielsweise später wiederhergestellt werden soll. Dieses Andenken sollte zu Optimierungszwecken so klein wie möglich sein.

Das Befehlsmuster kapselt in einem Objekt (einem Befehl) einige Anweisungen, die bei Bedarf ausgeführt werden sollen.

Basierend auf diesen beiden Konzepten können Sie einen grundlegenden Rückgängig- / Wiederherstellungsverlauf schreiben, wie den folgenden, der in TypeScript codiert ist ( extrahiert und angepasst aus der Front-End-Bibliothek Interacto ).

Eine solche Geschichte beruht auf zwei Stapeln:

• Der Stapel für Objekte, die rückgängig gemacht werden können
• Der Stapel für Objekte, die wiederholt werden können

Kommentare werden im Algorithmus bereitgestellt. Beachten Sie nur, dass beim Rückgängigmachen der Wiederherstellungsstapel gelöscht werden muss! Der Grund dafür ist, dass die Anwendung in einem stabilen Zustand bleibt: Wenn Sie in die Vergangenheit zurückkehren, um einige von Ihnen durchgeführte Aktionen zu wiederholen, werden Ihre früheren Aktionen nicht mehr vorhanden sein, wenn Sie die Zukunft ändern.

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

Die UndoableOberfläche ist ganz einfach:

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

Sie können jetzt rückgängig zu machende Befehle schreiben, die für Ihre Anwendung ausgeführt werden.

Zum Beispiel (immer noch basierend auf Interacto-Beispielen) können Sie einen Befehl wie diesen schreiben:

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

Sie können den Befehl jetzt ausführen und der UndoHistory-Instanz hinzufügen:

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

Schließlich können Sie eine Schaltfläche zum Rückgängigmachen (oder eine Verknüpfung) an diesen Verlauf binden (dasselbe gilt für Wiederherstellen).

Solche Beispiele finden Sie auf der Interacto-Dokumentationsseite .