Verwaltung für Undo-/Redo-Funktionen

Hier kannst du häufig gestellte Fragen/Antworten und Tutorials lesen und schreiben.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6994
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Verwaltung für Undo-/Redo-Funktionen

Beitrag von STARGÅTE »

Vorwort

Die mehrstufige Rückgängig- und Wiederholen-Funktionen in Anwendungen betrachten wie heute als selbstverständlich.
Beim schreiben eines eigenen Editors, gelangt man also früher oder später zu dem Punkt, wo man sich Gedanken
darüber machen muss, wie man selbst solche Undo-/Redo-Funktionen in sein Programm einbinden könnte.

Um mehrmaliges Rückgängigmachen zu ermöglichen, ist es nötig, ein Protokoll über die gemachten Aktionen anzulegen.
Für den Inhalt eines Protokolleintrags gibt es folgende Möglichkeiten:
  1. Jeder Eintrag enthält die kompletten Informationen des aktuellen Zustands des Projekts.
    Das heißt, es wird mit jeder Aktion, eine aktuelle Version des Projekts gespeichert.
    Vorteil: nicht-lineares Navigieren durch das Protokoll möglich
    Nachteil: hocher Speicherverbrauch mit zunehmenden Einträgen bzw. Inhalt des Projekts
  2. Jeder Eintrag enthält nur genau die Informationen, die für die Ausführung (vor- und rückwärts) einer Aktion nötig sind.
    Das heißt, es werden mit jeder Aktion nur Informationen zur Aktion selbst gespeichert.
    Vorteil: geringer Speicherverbrauch, auch bei zunehmendem Inhalt des Projekts
    Nachteil: nur lineare Navigation möglich
In diesem Tutorial möchte ich zeigen wie man die 2. Variante umsetzen kann.

Vorüberlegungen

Um eine Aktion vorwärts oder rückwärts (Redo/Do oder Undo) ausführen zu können, muss jeder dieser Fälle
in der Aktion selbst definiert sein. Das kann bei einfachen Aktionen nur ein Vorzeichenwechsel sein,
bei anderen Aktionen jedoch entweder das Erstellen oder Löschen eines Objekts, jenachdem ob die Aktion
vorwärts oder rückwärts ausgeführt wird.
Für das Programm bedeutet das Konkret, dass für jede Aktion eine Prozedur und alle dafür nötigen Informationen bereit
gestellt werden müssen, sodass diese beim Ausführen, Wiederholen bzw. Rückgängigmachen angewendet werden können.

Protokollverwaltung

In dem folgenden Code, möchte ich zeigen, wie man eine Protokollverwaltung für Undo/Redo einrichten kann.
Diese stellt das Gerüst da und wird später mit den eigentlichen Informationen zu den Aktionen "gefüttert".

Code: Alles auswählen

EnableExplicit

; Modi für das ausführen einer Aktion
Enumeration
	#Action_Undo = -1 ; Rückgängigmachen
	#Action_Do   =  0 ; Ausführen (erstmalig)
	#Action_Redo =  1 ; Wiederholen
EndEnumeration

; Prototypen für das Ausführen und ggf. wieder Freigeben der Informationen einer Aktion
Prototype.i ApplyAction(*Buffer, Mode.i)
Prototype.i ReleaseAction(*Buffer)

; Struktur einer Aktion
Structure HistoryAction
	*Buffer               ; Speicherpuffer für die Aktionsinformationen
	Apply.ApplyAction     ; Funktion für das Ausführen
	Release.ReleaseAction ; Funktion für das Freigeben der Informationen (optional, zB. bei Stringinhalten)
EndStructure

; Struktur des Aktions-Protokolls
Structure History
	List Action.HistoryAction() ; Auflistung aller Aktionen
EndStructure

;_______________________________________________________________________________
;

; Gibt eine Aktion aus dem Protokoll wieder frei.
Procedure ReleaseAction(*History.History, *Action.HistoryAction)
	If *Action\Release
		; Spezielle Freigabeprozedur, zB. mit ClearStructure() und FreeMemory()
		*Action\Release(*Action\Buffer)
	Else
		; Standardfreigabe des Informationspuffers
		FreeMemory(*Action\Buffer)
	EndIf
	ChangeCurrentElement(*History\Action(), *Action)
	DeleteElement(*History\Action())
EndProcedure

; Führt eine Aktion (vorwärts) aus, und fügt diese zum Protokoll hinzu.
; Alle Aktionen, die bis dahin durch Redo rückgängig gemacht wurden, werden dabei freigegeben.
Procedure ApplyAction(*History.History, *Buffer, Apply.ApplyAction, Release.ReleaseAction=#Null)
	While NextElement(*History\Action())
		ReleaseAction(*History, *History\Action())
	Wend
	AddElement(*History\Action())
	With *History\Action()
		\Buffer  = *Buffer
		\Apply   = Apply
		\Release = Release
	EndWith
	Apply(*Buffer, #Action_Do)
EndProcedure

; Springt im Protokoll auf die nächste Aktion und führt diese vorwärts aus.
Procedure RedoAction(*History.History)
	If NextElement(*History\Action())
		*History\Action()\Apply(*History\Action()\Buffer, #Action_Redo)
		ProcedureReturn #True
	EndIf
EndProcedure

; Führt die aktuelle Aktion rückwärts aus und springt im Protokoll eine Aktion zurück.
Procedure UndoAction(*History.History)
	If ListIndex(*History\Action()) > -1
		*History\Action()\Apply(*History\Action()\Buffer, #Action_Undo)
		If Not PreviousElement(*History\Action())
			ResetList(*History\Action())
		EndIf
		ProcedureReturn #True
	EndIf
EndProcedure

; Gibt die aktuelle Position des Verlaufs zurück (beginnend bei 1) oder 0 wenn keine Aktion verfügbar ist.
Procedure.i GetHistoryState(*History.History)
	ProcedureReturn ListIndex(*History\Action()) + 1
EndProcedure

; Fürt alle nötigen Aktionen aus, um die neue Position im Protokoll zu erreichen.
Procedure.i SetHistoryState(*History.History, State.i)
	State - 1
	While State > ListIndex(*History\Action())
		RedoAction(*History)
	Wend
	While State < ListIndex(*History\Action())
		UndoAction(*History)
	Wend
EndProcedure

; Gibt die aktuelle Länge (Anzahl der Aktionen) des Protokolls zurück.
Procedure.i HistoryLength(*History.History)
	ProcedureReturn ListSize(*History\Action())
EndProcedure

; Gibt den Speicherverbrauch (in Byte) des Protokolls zurück.
; (die Aktionseinträge selbst und deren Informationen)
Procedure.i SizeOfHistory(*History.History)
	Protected Size.i
	If ListSize(*History\Action())
		PushListPosition(*History\Action())
		ForEach *History\Action()
			Size + SizeOf(HistoryAction) + SizeOf(Integer)*3
			Size + MemorySize(*History\Action()\Buffer)
		Next
		PopListPosition(*History\Action())
	EndIf
	ProcedureReturn Size
EndProcedure
Einfaches Beispiel: Plusrechnen

Um mit den zuvor aufgeführten Prozeduren etwas vertrauter zu werden, zeige ich hier
ein sehr einfaches und kleines Beispiel wie man diese beim "Plusrechnen" nutzen kann:

Code: Alles auswählen

; ! Hier bitte nicht vergessen den Code von "Protokollverwaltung" einzufügen !

Global History.History ; Anlegen eines Protokolls

Global Ergebnis.i = 0 ; Variable für das aktuelle Ergebnis

; Definition der Prozedure für eine Aktion: Hier Addieren
Procedure Action_AddNumber(*Buffer.Integer, Mode.i)
	Select Mode
		Case #Action_Undo ; Rückgängigmachen
			Ergebnis - *Buffer\i
		Case #Action_Do, #Action_Redo ; Ausführen, Wiederholen
			Ergebnis + *Buffer\i
	EndSelect
EndProcedure

; Prozedur, welche die Aktion zum Addieren einer Zahl erstellt und ausführt.
Procedure AddNumber(Integer.i)
	; Anlegen und füllen des Informations-Speicherpuffers für die Aktion
	Protected *Buffer.Integer = AllocateMemory(SizeOf(Integer))
	*Buffer\i = Integer
	; Ausführen der Aktion
	ApplyAction(@History, *Buffer, @Action_AddNumber())
EndProcedure

; Testen:
Debug "'Ergebnis' ist am Anfang 0:"
Debug Ergebnis
AddNumber(40)
AddNumber(20)
AddNumber(10)
Debug "'Ergebnis' ist nun 70 (0+40+20+10):"
Debug Ergebnis
UndoAction(@History)
UndoAction(@History)
Debug "'Ergebnis' sollte nun 40 sein (+20+10 wurde rückgängig gemacht):"
Debug Ergebnis
RedoAction(@History)
Debug "'Ergebnis' ist nun 60 (+20 wurde wiederholt):"
Debug Ergebnis
AddNumber(5)
Debug "'Ergebnis' ist nun 65 (+5 wurde ausgeführt, +10 gelöscht):"
Debug Ergebnis
Erweitertes Beispiel: Kreise erstellen und verschieben

Nachdem das einfache Beispiel gezeigt hat, wie die Protokollverwaltung zu nutzen ist,
folgt nun ein größeres Beispiel bei mit auf einem CanvasGadget Kreise mit der linken Maustaste erstellt werden können
und mit der rechten Maustaste verschoben werden können:

Code: Alles auswählen

; ! Hier bitte nicht vergessen den Code von "Protokollverwaltung" einzufügen !

Global History.History ; Anlegen eines Protokolls

; Struktur und Liste der Objekte
Structure Object
	X.i : Y.i
EndStructure
Global NewList Object.Object()

; Speicherpuffer für das Erstellen eines Objekts
Structure Buffer_AddObject
	*Object.Object
	X.i : Y.i
EndStructure

; Aktion für das Erstellen eines Objekts
Procedure Action_AddObject(*Buffer.Buffer_AddObject, Mode.i)
	With *Buffer
		Select Mode
			Case #Action_Do, #Action_Redo
				\Object = AddElement(Object())
				Object()\X = \X : Object()\Y = \Y
			Case #Action_Undo
				ChangeCurrentElement(Object(), \Object)
				DeleteElement(Object())
		EndSelect
	EndWith
EndProcedure

; Erstellt eine Aktion (nicht das Objekt selbst!) zum Erstellen eines Objekts und führt diese aus.
Procedure AddObject(X.i, Y.i)
	Protected *Buffer.Buffer_AddObject = AllocateMemory(SizeOf(Buffer_AddObject))
	*Buffer\X = X : *Buffer\Y = Y
	ApplyAction(@History, *Buffer, @Action_AddObject())
EndProcedure	

; Speicherpuffer für das Verschieben eines Objekts
Structure Buffer_MoveObject
	*Object.Object
	OldX.i : OldY.i
	NewX.i : NewY.i
EndStructure

; Aktion für das Bewegen eines Objekts
Procedure Action_MoveObject(*Buffer.Buffer_MoveObject, Mode.i)
	With *Buffer
		Select Mode
			Case #Action_Do, #Action_Redo
				\Object\X = \NewX
				\Object\Y = \NewY
			Case #Action_Undo
				\Object\X = \OldX
				\Object\Y = \OldY
		EndSelect
	EndWith
EndProcedure

; Erstellt eine Aktion (nicht das Objekt selbst!) zum Bewegen eines Objekts und führt diese aus.
Procedure MoveObject(*Object.Object, OldX.i, OldY.i, NewX.i, NewY.i)
	Protected *Buffer.Buffer_MoveObject = AllocateMemory(SizeOf(Buffer_MoveObject))
	*Buffer\Object = *Object
	*Buffer\OldX = OldX : *Buffer\OldY = OldY
	*Buffer\NewX = NewX : *Buffer\NewY = NewY
	ApplyAction(@History, *Buffer, @Action_MoveObject())
EndProcedure	

;-------------------------------------------------------------------------------

Enumeration
	#Window
	#CanvasGadget
	#UndoGadget
	#RedoGadget
	#HistoryGadget
	#TextGadget
EndEnumeration

OpenWindow(#Window, 0, 0, 800, 600, "Undo/Redo", #PB_Window_MinimizeGadget|#PB_Window_ScreenCentered)
	ButtonGadget(#UndoGadget,  0, 0, 50, 20, "Undo")
	ButtonGadget(#RedoGadget, 50, 0, 50, 20, "Redo")
	ComboBoxGadget(#HistoryGadget, 100, 0, 100, 20)
	DisableGadget(#UndoGadget, #True)
	DisableGadget(#RedoGadget, #True)
	DisableGadget(#HistoryGadget, #True)
	TextGadget(#TextGadget, 210, 0, 200, 20, "")
	CanvasGadget(#CanvasGadget, 0, 20, WindowWidth(#Window), WindowHeight(#Window)-20)

Procedure Update(WithGadgets.i=#True)
	Protected Index.i, Length.i = HistoryLength(@History)
	StartDrawing(CanvasOutput(#CanvasGadget))
		Box(0, 0, OutputWidth(), OutputHeight(), $FFFFFF)
		ForEach Object()
			Circle(Object()\X, Object()\Y, 10, $000000)
		Next
	StopDrawing()
	If WithGadgets
		ClearGadgetItems(#HistoryGadget)
		AddGadgetItem(#HistoryGadget, #PB_Any, "Version 0")
		For Index = 1 To Length
			AddGadgetItem(#HistoryGadget, #PB_Any, "Version "+Str(Index))
		Next
		If Length
			DisableGadget(#HistoryGadget, #False)
		Else
			DisableGadget(#HistoryGadget, #True)
		EndIf
		SetGadgetState(#HistoryGadget, GetHistoryState(@History))
		SetGadgetText(#TextGadget, "Speicherverbrauch des Verlaufs: "+Str(SizeOfHistory(@History))+" Byte")
	EndIf
EndProcedure

Update()

Define *Object.Object, OldX.i, OldY.i, MouseX.i, MouseY.i

Repeat
	Select WaitWindowEvent()
		Case #PB_Event_CloseWindow
			End
		Case #PB_Event_Gadget
			Select EventGadget()
				Case #CanvasGadget
					MouseX = GetGadgetAttribute(#CanvasGadget, #PB_Canvas_MouseX)
					MouseY = GetGadgetAttribute(#CanvasGadget, #PB_Canvas_MouseY)
					Select EventType()
						Case #PB_EventType_LeftClick
							AddObject(MouseX, MouseY)
							Update()
							DisableGadget(#UndoGadget, #False)
							DisableGadget(#RedoGadget, #True)
						Case #PB_EventType_RightButtonDown
							ForEach Object()
								If Sqr(Pow(MouseX-Object()\X,2)+Pow(MouseY-Object()\Y,2)) < 10
									*Object = Object()
									OldX = Object()\X
									OldY = Object()\Y
									Break
								EndIf
							Next
						Case #PB_EventType_MouseMove
							If *Object
								*Object\X = MouseX
								*Object\Y = MouseY
								Update(#False)
							EndIf
						Case #PB_EventType_RightButtonUp
							If *Object
								MoveObject(*Object, OldX, OldY, MouseX, MouseY)
								Update()
								*Object = #Null
							EndIf
					EndSelect
				Case #UndoGadget
					UndoAction(@History)
					Update()
				Case #RedoGadget
					RedoAction(@History)
					Update()
				Case #HistoryGadget
					SetHistoryState(@History, GetGadgetState(#HistoryGadget))
					Update()
			EndSelect
			If GetHistoryState(@History) > 0
				DisableGadget(#UndoGadget, #False)
			Else
				DisableGadget(#UndoGadget, #True)
			EndIf
			If GetHistoryState(@History) < HistoryLength(@History)
				DisableGadget(#RedoGadget, #False)
			Else
				DisableGadget(#RedoGadget, #True)
			EndIf
	EndSelect
ForEver
Komplexes Beispiel: Stringveränderung

Im letzten Beispiel möchte ich noch mal zeigen, dass es auch genügt eine Callback-Prozedure zu definieren,
wenn man zB auch noch selbst einen Typ in der Aktionsinformationen definiert.
Am Beispiel eines Strings der verändert wird soll dies gezeigt werden:

Code: Alles auswählen

; ! Hier bitte nicht vergessen den Code von "Protokollverwaltung" einzufügen !

Global History.History ; Anlegen eines Protokolls

; Informationspuffer
Structure Buffer_StringAction
	ActionType.i  ; Aktionstyp
	*Text.String  ; Adresse der Text (String-Struktur)
	String.s      ; hinzukommender/wegfallender String
	Position.i    ; Position
EndStructure

; Meine eigenen Aktionstypen
Enumeration
	#StringAction_Insert
	#StringAction_Remove
EndEnumeration

; Aktionsprozedur
Procedure StringAction(*Buffer.Buffer_StringAction, Mode.i)
	With *Buffer
		Select Mode
			Case #Action_Undo ; Rückgängigmachen
				Select \ActionType
					Case #StringAction_Insert
						\Text\s = Left(\Text\s, \Position-1) + Mid(\Text\s, \Position+Len(\String))
					Case #StringAction_Remove
						\Text\s = InsertString(\Text\s, \String, \Position)
				EndSelect
			Case #Action_Do, #Action_Redo ; Ausführen, Wiederholen
				Select \ActionType
					Case #StringAction_Insert
						\Text\s = InsertString(\Text\s, \String, \Position)
					Case #StringAction_Remove
						\Text\s = Left(\Text\s, \Position-1) + Mid(\Text\s, \Position+Len(\String))
				EndSelect
		EndSelect
	EndWith
EndProcedure

; Aktionsprozedur
Procedure FreeStringAction(*Buffer.Buffer_StringAction)
	ClearStructure(*Buffer, Buffer_StringAction)
	FreeMemory(*Buffer)
EndProcedure

; Prozedure zum hinzufügen von Text 
Procedure InsertText(*Text.String, TextToInsert.s, Position.i)
	Protected *Buffer.Buffer_StringAction = AllocateMemory(SizeOf(Buffer_StringAction))
	InitializeStructure(*Buffer, Buffer_StringAction)
	*Buffer\ActionType = #StringAction_Insert
	*Buffer\Text = *Text
	*Buffer\String = TextToInsert
	*Buffer\Position = Position
	ApplyAction(@History, *Buffer, @StringAction(), @FreeStringAction())
EndProcedure

; Prozedure zum entfernen eines Textstücks 
Procedure RemoveText(*Text.String, Position.i, Length.i)
	Protected *Buffer.Buffer_StringAction = AllocateMemory(SizeOf(Buffer_StringAction))
	InitializeStructure(*Buffer, Buffer_StringAction)
	*Buffer\ActionType = #StringAction_Remove
	*Buffer\Text = *Text
	; Für das Rückgängigmachen muss der zu löschende Text natürlich gesichert werden
	*Buffer\String = Mid(*Text\s, Position, Length)
	*Buffer\Position = Position
	ApplyAction(@History, *Buffer, @StringAction(), @FreeStringAction())
EndProcedure

Define Text.String ; Aktueller Text

; Testen:
Debug "Der Text ist am Anfang leer:"
Debug Text\s
InsertText(@Text, "Hallo Welt!", 1)
RemoveText(@Text, 7, 4)
InsertText(@Text, "Programmierer", 7)
Debug "Nun sollte hier 'Hallo Programmierer!' stehen:"
Debug Text\s
UndoAction(@History)
UndoAction(@History)
Debug "Nachdem zwei sachen rückgängig gemacht wurden, sollte wieder 'Hallo Welt!' zu sehen sein:"
Debug Text\s
RedoAction(@History)
InsertText(@Text, "Cool", 7)
RemoveText(@Text, 1, 6)
Debug "Nachdem eine Aktion wiederholt wurde, und zwei neue Aktionen ausgeführt wurden, sollte nun 'Cool!' erscheinen"
Debug Text\s
Schlusswort

Ich hoffe ich konnte mit diesem Tutorial die Programmierung einer Undo-/Redo-Funktion erleichtern.
Mit sicherheit wird auch der eine oder andere denken, dass es doch ein enormer Aufwand ist,
für jede Aktion extra ein Informationspuffer und ein Callback anzulegen.
Dem stimme ich auch im zu, allerdings hat man dafür keinerlei Extras mehr für das eigentliche Undo-/Redo
zu programmieren. Lediglich der aufruf von UndoAction() und RedoAction() reicht dann aus.

Es wäre schön wenn der eine oder andere ein Feedback zu diesem Tutorial geben könnte, sodass ich es auch ggf. verbessern kann.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
RSBasic
Admin
Beiträge: 8022
Registriert: 05.10.2006 18:55
Wohnort: Gernsbach
Kontaktdaten:

Re: Verwaltung für Undo-/Redo-Funktionen

Beitrag von RSBasic »

Schönes Tutorial, gefällt mir. :allright:
Aus privaten Gründen habe ich leider nicht mehr so viel Zeit wie früher. Bitte habt Verständnis dafür.
Bild
Bild
c4s
Beiträge: 1235
Registriert: 19.09.2007 22:18

Re: Verwaltung für Undo-/Redo-Funktionen

Beitrag von c4s »

Dies hat mich an ein entsprechendes System von srod erinnert, "Demento":
http://www.purebasic.fr/english/viewtop ... 12&t=42867
"Menschenskinder, das Niveau dieses Forums singt schon wieder!" — GronkhLP ||| "ich hogffe ihr könnt den fehle endecken" — Marvin133 ||| "Ideoten gibts ..." — computerfreak ||| "Jup, danke. Gruss" — funkheld
Benutzeravatar
ts-soft
Beiträge: 22292
Registriert: 08.09.2004 00:57
Computerausstattung: Mainboard: MSI 970A-G43
CPU: AMD FX-6300 Six-Core Processor
GraKa: GeForce GTX 750 Ti, 2 GB
Memory: 16 GB DDR3-1600 - Dual Channel
Wohnort: Berlin

Re: Verwaltung für Undo-/Redo-Funktionen

Beitrag von ts-soft »

:allright:
Interessante Sache, sehr nützlich!
PureBasic 5.73 LTS | SpiderBasic 2.30 | Windows 10 Pro (x64) | Linux Mint 20.1 (x64)
Nutella hat nur sehr wenig Vitamine. Deswegen muss man davon relativ viel essen.
Bild
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6994
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Verwaltung für Undo-/Redo-Funktionen

Beitrag von STARGÅTE »

Nachdem ich nun selbst diese Undo-/Redo-Funktionen in meinem Editor eingebungen habe,
bin ich blöderweise noch auf ein Problem gestoßen.
Das Problem liegt dabei nicht die Verwaltung selbst, sonden in der Art wie ich sie bei mir genutzt habe.

Bei jeder Aktion für ein Objekt verwende ich ja zur Identifizierung die Adresse des Objekts selbst.
Wenn ich nun aber zB. eine Löschaktion ausführe (bei der ein Backup des Objekts gemacht wird, für ein späteres Undo)
dann wird das Objekt ja gelöscht und somit auch die Adresse ungültig.
Beim Rückgängigmachen wurde dann nur eine Kopie erstellt werden, aber nicht mehr das original,
sodass vorherige Aktionen nicht mehr ausgeführt werden können.

Das bedeutet also, dass man bei solchen Undo/Redo-Funktionen entweder ein eigenes ID-System festenlegen muss,
oder man die Objekte nicht wirklich löscht, sonden nur versteckt. Dadurch wäre ein Rückgängigmachen
natürlich noch einfacher. Die Objekte werden erst dann richtig freigegeben, wenn die Aktion nicht mehr benötigt wird.

Ich werde die Beispiele (in den nächsten Tagen) um "das Löschen von Objekte" dem entsprechen erweitern.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Antworten