Cofnij / Ponów implementację

Daj mi kilka przemyśleń, jak zaimplementować funkcję cofania / ponawiania - tak jak w przypadku edytorów tekstu. Jakich algorytmów powinienem używać i co mogę przeczytać. dzięki.

Wiem o dwóch głównych działach typów cofnięć

• ZAPISZ STAN: Jedna kategoria cofania to miejsce, w którym faktycznie zapisujesz stany historii. W tym przypadku dzieje się tak, że w każdym momencie zapisujesz stan w jakimś miejscu pamięci. Kiedy chcesz cofnąć operację, po prostu zamień bieżący stan i zamień stan, który był już w pamięci. Tak to się robi na przykład z Historią w Adobe Photoshopie lub ponownym otwieraniu zamkniętych kart w Google Chrome.

• STAN WYTWARZANIA: Druga kategoria dotyczy sytuacji, w których zamiast utrzymywać same stany, po prostu pamiętasz, jakie były działania. kiedy musisz cofnąć, musisz wykonać logiczne odwrócenie tej konkretnej czynności. Dla prostego przykładu, kiedy zrobisz Ctrl+ Bw jakimś edytorze tekstu, który obsługuje cofanie, zostanie to zapamiętane jako akcja pogrubiona . Teraz każda akcja jest odwzorowaniem jej logicznych odwrotności. Tak więc, kiedy robisz Ctrl+ Z, wyszukuje z tabeli działań odwrotnych i stwierdza, że ​​akcja cofnięcia to znowu Ctrl+ B. To jest wykonywane i osiągasz swój poprzedni stan. Więc tutaj twój poprzedni stan nie był przechowywany w pamięci, ale generowany, kiedy tego potrzebujesz.

W przypadku edytorów tekstu generowanie stanu w ten sposób nie wymaga zbyt wielu obliczeń, ale w przypadku programów takich jak Adobe Photoshop może być zbyt intensywne lub po prostu niemożliwe. Na przykład - w przypadku działania rozmycia określisz opcję usuwania rozmycia czynność , ale to nigdy nie doprowadzi Cię do pierwotnego stanu, ponieważ dane zostały już utracone. Tak więc, w zależności od sytuacji - możliwości logicznego odwrotnego działania i wykonalności tego, musisz wybrać jedną z tych dwóch szerokich kategorii, a następnie wdrożyć je tak, jak chcesz. Oczywiście możesz mieć strategię hybrydową, która będzie dla Ciebie odpowiednia.

Czasami, podobnie jak w Gmailu, możliwe jest cofnięcie ograniczone w czasie, ponieważ akcja (wysyłanie poczty) nigdy nie jest wykonywana w pierwszej kolejności. Zatem nie „cofasz” tego działania, po prostu „nie wykonujesz” samej czynności.

Napisałem od podstaw dwóch edytorów tekstu i oba wykorzystują bardzo prymitywną formę funkcji cofania / ponawiania. Przez „prymitywny” rozumiem, że funkcjonalność była bardzo łatwa do zaimplementowania, ale jest nieekonomiczna w bardzo dużych plikach (powiedzmy >> 10 MB). Jednak system jest bardzo elastyczny; na przykład obsługuje nieograniczone poziomy cofania.

Zasadniczo definiuję taką strukturę

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

a następnie zdefiniuj tablicę

var
  UndoData: array of TUndoDataItem;

Następnie każdy element tej tablicy określa zapisany stan tekstu. Teraz przy każdej edycji tekstu (klawisz znaku w dół, klawisz cofania w dół, klawisz usuwania, wycinanie / wklejanie, zaznaczenie przesuwane myszą itp.) Uruchamiam (ponownie) licznik czasu (powiedzmy) jednej sekundy. Po wyzwoleniu licznik czasu zapisuje bieżący stan jako nowy element członkowskiUndoData tablicy.

Po cofnięciu (Ctrl + Z) przywracam edytor do stanu UndoData[UndoLevel - 1]i zmniejszam UndoLevelo jeden. Domyślnie UndoLeveljest równy indeksowi ostatniego elementu UndoDatatablicy. Po ponownym wykonaniu (Ctrl + Y lub Shift + Ctrl + Z) przywracam edytor do stanu UndoData[UndoLevel + 1]i zwiększam UndoLevelo jeden. Oczywiście, jeśli licznik czasu edycji jest wyzwalany, gdy UndoLevelnie jest równy długości (minus jeden) UndoDatatablicy, usuwam wszystkie elementy tej tablicy po UndoLevel, jak to jest powszechne na platformie Microsoft Windows (ale Emacs jest lepszy, jeśli pamiętam poprawnie - wadą podejścia Microsoft Windows jest to, że jeśli cofniesz wiele zmian, a następnie przypadkowo edytujesz bufor, poprzednia zawartość (która została cofnięta) zostanie trwale utracona). Możesz pominąć tę redukcję tablicy.

W innym typie programu, na przykład w edytorze obrazów, można zastosować tę samą technikę, ale oczywiście o zupełnie innej UndoDataItemstrukturze. Bardziej zaawansowane podejście, które nie wymaga tak dużej ilości pamięci, polega na zapisywaniu tylko zmian między poziomami cofania (to znaczy zamiast zapisywania „alpha \ nbeta \ gamma” i „alpha \ nbeta \ ngamma \ ndelta”, możesz zapisz "alfa \ nbeta \ ngamma" i "DODAJ \ ndelta", jeśli widzisz, o co mi chodzi). W bardzo dużych plikach, w których każda zmiana jest niewielka w porównaniu z rozmiarem pliku, znacznie zmniejszy to użycie pamięci przez cofnięte dane, ale jest trudniejsze do zaimplementowania i prawdopodobnie bardziej podatne na błędy.

Jest na to kilka sposobów, ale możesz zacząć przyglądać się wzorowi polecenia . Użyj listy poleceń, aby przejść wstecz (Cofnij) lub do przodu (ponów) podczas wykonywania czynności. Przykład w C # można znaleźć tutaj .

Trochę późno, ale proszę bardzo: Odnosisz się konkretnie do edytorów tekstu, poniżej wyjaśniono algorytm, który można dostosować do tego, co edytujesz. Zasadą jest przechowywanie listy czynności / instrukcji, które można zautomatyzować, aby odtworzyć każdą wprowadzoną zmianę. Nie wprowadzaj zmian w oryginalnym pliku (jeśli nie jest pusty), zachowaj go jako kopię zapasową.

Zachowaj połączoną listę zmian wprowadzonych w oryginalnym pliku do przodu i do tyłu. Lista ta jest zapisywana sporadycznie w pliku tymczasowym, dopóki użytkownik nie zapisze zmian: kiedy tak się stanie, zastosujesz zmiany do nowego pliku, kopiując stary i jednocześnie wprowadzając zmiany; następnie zmień nazwę oryginalnego pliku na kopię zapasową i zmień nazwę nowego pliku na poprawną. (Możesz zachować zapisaną listę zmian lub usunąć ją i zastąpić kolejną listą zmian.)

Każdy węzeł na liście połączonych zawiera następujące informacje:

• rodzaj zmiany: albo wstawiasz dane, albo usuwasz dane: „zmiana” danych oznacza a, deletepo którym następujeinsert
• pozycja w pliku: może być przesunięciem lub parą linii / kolumn
• bufor danych: są to dane związane z akcją; jeśli insertto dane, które zostały wstawione; jeśli delete, dane, które zostały usunięte.

Aby zaimplementować Undo, pracujesz wstecz od końca listy połączonej, używając wskaźnika lub indeksu „bieżącego węzła”: tam, gdzie nastąpiła zmiana insert, usuwasz, ale nie aktualizujesz listy połączonej; a gdzie to było deletewstawiasz dane z danych do bufora listy połączonej. Zrób to dla każdego polecenia „Cofnij” użytkownika. Redoprzesuwa wskaźnik „bieżącego węzła” do przodu i wykonuje zmianę zgodnie z węzłem. Jeśli użytkownik dokona zmiany w kodzie po cofnięciu, usuń wszystkie węzły za wskaźnikiem „bieżący węzeł” do końca i ustaw koniec równy wskaźnikowi „bieżącego węzła”. Nowe zmiany użytkownika są następnie wstawiane za ogonem. I to wszystko.

Moje jedyne dwa centy to to, że chciałbyś użyć dwóch stosów do śledzenia operacji. Za każdym razem, gdy użytkownik wykonuje jakąś operację, Twój program powinien umieszczać te operacje na stosie „wykonanym”. Gdy użytkownik chce cofnąć te operacje, po prostu przenieś operacje ze stosu „wykonanego” do stosu „przywracania”. Gdy użytkownik chce powtórzyć te operacje, zdejmij elementy ze stosu „przywołaj” i wrzuć je z powrotem do stosu „wykonanego”.

Mam nadzieję, że to pomoże.

Jeśli działania są odwracalne. np. dodanie 1, wykonanie ruchu gracza itp. zobacz, jak używać wzorca poleceń do implementacji cofania / ponawiania . Kliknij link, aby znaleźć szczegółowe przykłady, jak to zrobić.

Jeśli nie, użyj stanu zapisanego, jak wyjaśniono w @Lazer.

Możesz przestudiować przykład istniejącego frameworka cofania / ponawiania, pierwsze trafienie Google jest na codeplex (dla .NET) . Nie wiem, czy to jest lepsze, czy gorsze niż jakikolwiek inny framework, jest ich dużo.

Jeśli Twoim celem jest posiadanie funkcji cofania / ponawiania w aplikacji, równie dobrze możesz po prostu wybrać istniejący framework, który wygląda na odpowiedni dla twojego rodzaju aplikacji.
Jeśli chcesz dowiedzieć się, jak zbudować własne cofanie / ponawianie, możesz pobrać kod źródłowy i przyjrzeć się zarówno wzorcom, jak i szczegółom łączenia rzeczy.

Do tego został stworzony wzór Memento .

Zanim zaimplementujesz to samodzielnie, zwróć uwagę, że jest to dość powszechne, a kod już istnieje - na przykład, jeśli kodujesz w .Net, możesz użyć IEditableObject .

Dodając do dyskusji, napisałem wpis na blogu o tym, jak wdrożyć UNDO i REDO w oparciu o myślenie o tym, co jest intuicyjne: http://adamkulidjian.com/undo-and-redo.html

Jednym ze sposobów zaimplementowania podstawowej funkcji cofania / ponawiania jest użycie wzorców projektowania memento i poleceń.

Memento ma na celu na przykład zachowanie stanu obiektu, który ma być później przywrócony. Ta pamiątka powinna być jak najmniejsza w celu optymalizacji.

Na polecenie kapsułkowane substancje wzór w obiekt (polecenie) jakieś instrukcje do wykonania w razie potrzeby.

W oparciu o te dwie koncepcje możesz napisać podstawową historię cofania / ponawiania, taką jak następująca zakodowana w TypeScript ( wyodrębniona i dostosowana z biblioteki frontendowej Interacto ).

Taka historia opiera się na dwóch stosach:

• stos obiektów, które można cofnąć
• stos dla obiektów, które można przerobić

W algorytmie znajdują się komentarze. Zwróć uwagę, że podczas operacji cofania stos powtórzeń musi zostać wyczyszczony! Powodem jest pozostawienie aplikacji w stabilnym stanie: jeśli cofniesz się w przeszłości, aby powtórzyć niektóre działania, które wykonałeś, poprzednie działania przestaną istnieć, ponieważ zmienisz przyszłość.

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

UndoableInterfejs jest dość prosty:

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

Możesz teraz pisać polecenia, które można cofnąć, które działają w Twojej aplikacji.

Na przykład (wciąż na podstawie przykładów Interacto) możesz napisać takie polecenie:

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

Możesz teraz wykonać i dodać polecenie do instancji UndoHistory:

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

Na koniec możesz przypisać przycisk cofania (lub skrót) do tej historii (to samo dotyczy ponawiania).

Takie przykłady są szczegółowo opisane na stronie dokumentacji Interacto .