Undo-/Redofunktion über Stack implementieren

**:::

Beschreibung:

mir ist neulich die Idee gekommen, dass man Undo- und Redo funktionen doch Prima über einen Stack implementieren kann. Die Vorteile liegen klar auf der Hand:

• Ein Stack ist schnell zugreifbar
• Wir brauchen eh immer nur ein (Das oberste) Element
• Er ist recht simpel zu handhaben

Zur Realisierung des Problems ist aber etwas mehr Überlegung nötig:

Zum Einen benötigen wir ja nicht nur einen temporären Speicher für unsere Informationen, sondern auch eine Unterscheidung, welche Informationen gespeichert werden, bzw. wie diese zu Behandeln sind. Grundsätzlich habe ich damit begonnen eine C++ Klasse zur Organisation eines Stacks für diese Zwecke zu schreiben. Dort habe ich zur Speicherung der Daten einen void*-Pointer verwendet, der dann zurück gecastet wird. Da C# nicht direkt mit Pointern umgehen kann, müssen wir auf den integrierten Typ "object" zurückgreifen. Die Methode des nichttypisierten Objektes, welches über einen Objektcast auf den jeweiligen Datentyp gebracht wird (egal ob integriert oder klassifiziert), ermöglicht es uns eine allgemeine Struktur für eine Operation zu erstellen. Schließlich wollen wir ja einzelne Operationen über einen gewissen Zeitraum zurückverfolgen und auswerten.

Wir wissen also nun, wie wir die Daten im Stack ablegen, benötigen aber noch eine Möglichkeit diese zu spezifizieren, um sie später auswerten zu können. Ich habe mir diese Überlegung einfach gemacht und greife auf eine Enumeration zurück. Folglich können wir eine Struktur wie folgt erstellen:

struct Operation
{
	private object m_oData;
	private OperationType m_oType;

	public object Data
	{
		get
		{
			return m_oData;
		}
		set
		{
			m_oData = value;
		}
	}

	public OperationType Type
	{
		get
		{
			return m_oType;
		}
		set
		{
			m_oType = value;
		}
	}
}

public enum OperationType
{
	otINSERT_ITEM,
	otREMOVE_ITEM,
	otCHANGE_ITEM
}

Ein alternativer Ansatz wäre hier über ein Template zu gehen, welches den jeweiligen Typ des hier verwendeten nichttypisierten Objektes "m_oData" festhält. Problem bei der Sache ist, dass wir dann verschieden typisierte Strukturen in unserem Stack liegen haben. Das wollen wir vermeiden, denn so ersparen wir uns eine eventuelle Typabfrage oder Fehler, die mit eventuellen Typdifferenzen aufkommen können. Wir casten einfach unseren Typ in die gewünchte Form. (Was nicht heißt, das hierbei keine Fehler entstehen können, doch bei konsequenter Mitführung sämtlicher Operationen und Einstellung des Operationstyps, können wir durch casten entstehende Fehler ausschließen.)

In diesem Beispiel werde ich Operationen über einer ListView aufzeichnen. In einer ListView kann ich 3 grundlegende Operationen mit einem ListViewItem ausführen: Hinzufügen, Löschen und Ändern. Darum hat mein Enumerator auch nur diese 3 Einträge. Für den expliziten Fall müssen eventuell mehr Eintragungen im Enumerator gemacht werden, was später auch Auswirkungen auf die Behandlung der Typabfrage hat.

Ich werde nicht explizit auf die Einstellungen und auf die Erstellung einer ListView eingehen. Ich setze voraus, dass Jeder, der dieses Tutorial ließt weiß, wie er Controls auf einem Formular platziert, bzw. mit diesen arbeitet.

Aber nun weiter im Text. Wir haben uns also nun Gedanken über die Organisation der einzelnen Operationen gemacht, machen wir uns nun Gedanken über die Organisation der Operationen als Stack, sowie der jeweiligen Implementierung des Stacks:
Ein Stack zeichnet sich dadurch aus, dass er ähnlich wie eine Liste (System.Collections.Generic.List<>) aufgebaut ist, jedoch ist nur das oberste Element abrufbar. Es handelt sich also um eine einfach verkettete Liste, ohne Such-, Sortiert oder Änderungsoperationen. Ein Stack hat 2 Grundoperationen: push und pop, also Auflegen und Abheben. Implementiert wird ein Stack ähnlich wie eine Liste: Die Elemente sind über Zeiger verkettet - der Zeiger des letzten Elementes ist der NULL-Zeiger. Der Unterschied zur Liste besteht darin, dass es in der Liste einen zusätzlichen Zeiger auf das jeweils Erste Element und das jeweils zur Zeit ausgewählte Element gibt, um in einer Liste navigieren zu können. In einem Stack muss nicht navigiert werden, also entfällt der Zeiger auf das zuletzt gewählte Element.
Wir können einen Stack also einfach durch die Grundoperationen verwenden. Zusätzlich benötigen wir (im Falle des Programmendes übernimmt es der Garbage Collector, allerdings ist es notwendig für optionale Anpassungen) noch eine Clear() Funktion, die glücklicherweiße im System.Collections.Generic.Stack<> Template schon mit implementiert ist. (Wer einmal einen Stack selbst schreibt, wird feststellen, dass sich solch eine Funktion einfach über eine while-Schleife organisieren lässt.) Alles was wir nun noch tun müssen ist die jeweilige Operation über der ListView abzufangen und entsprechend in den Stack eintragen. Schon haben wir unseren Undo-Stapel:

// Definition und Initialisierung
System.Collections.Generic.Stack<Operation> m_oUndoStack;
m_oUndoStack = new System.Collections.Generic.Stack<Operation>();

// ... weiterer Code ...

// Hinzufügen eines ListViewItems in die ListView _lvMyListView
public void AddItem(ListViewItem item)
{
	Operation oOperation = new Operation();
	oOperation.Data = item;		// item muss nicht gecastet werden, weil jeder Typ abstahiert object sein kann.
	oOperation.Type = OperationType.otINSERT_ITEM;
	m_oUndoStack.push(oOperation);	// Operation-Objekt oben auf dem Stack auflegen
	_lvMyListView.Items.Add(item);
}

// Löschen eines ListViewItems aus der ListView _lvMyListView
public void RemoveItem(ListViewItem item)
{
	Operation oOperation = new Operation();
	oOperation.Data = item;
	oOperation.Type = OperationType.otREMOVE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items.Remove(item);
}

// Ändern eines ListViewItems in der ListView _lvMyListView
public void SetItemText(int index, string text)
{
	// Fehlerbehandlung, falls index nicht exestiert der Einfachheit wegen weggelassen
	Operation oOperation = new Operation();
	oOperation.Data = _lvMyListView.Items[index];
	oOperation.Type = OperationType.otCHANGE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items[index].Text = text;
}

So weit, so gut. Jetzt haben wir unsere Operationen schön protokolliert in einem Stack gespeichert. Das eigentlich interessante kommt aber erst noch, denn wir wollen ja eigentlich die Operationen Rückgängig machen. Das funktioniert jetzt, weil wir alle Operationen über der ListView gespeichert haben. Es ist wichtig dies zu tun, denn würden die ListView-Elemente Auswirkungen auf andere Daten haben, so ist es auch wichtig diese mit zu speichern. Würden wir dies nicht tun wäre das fatal. Im besten Falle funktioniert alles scheinbar einwandfrei, bis wir ein paar Operationen rückgängig machen. Durch das Ändern werden Operationen als "nie da gewesen" simuliert, aber die Änderung durch die Operation (oder Teile davon) haben wir nicht beachtet, also auch nicht rückgängig gemacht. Jetzt haben wir ein Ergebniss, aber keine zuvorkommende Ursache. Es ist also eine klare Asynchronität festzustellen und ich kann mir kein Beispiel vorstellen, wo dies Gewünscht ist. Da die Daten fast nie gleich sind (in Anzahl und Wert) können wir hier unter umständen mit undefiniertem Verhalten rechnen. Bei C# haben wir den Vorteil, dass uns die CLR das irgentwann in Form einer Fehlermeldung mitteilt, aber dann sind die Daten meist nicht mehr zu gebrauchen. Darum ist es wichtig alles, was an Änderungen gemacht wird im Stack abzulegen.

Wenn wir das verstanden haben können wir darüber nachdenken, wie wir eine "Undo"-Methode implementieren:

public void undo()
{
	Operation oOperation = m_oUndoStack.pop();	// Wir holen uns die letzte Operation und löschen sie vom Stack
	
	switch(oOperation.Type)
	{
		case OperationType.otINSERT_ITEM:
			{
				// Die Operation war "Einfügen", also müssen wir das ListViewItem wieder "Löschen"
				_lvMyListView.Items.Remove((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otREMOVE_ITEM:
			{
				// Genau umgekehrt
				_lvMyListView.Items.Add((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otCHANGE_ITEM:
			{
				// Das geänderte ListViewItem steht in der ListView, das "Alte" im Stack, also überschreiben wir das "Neue" einfach mit dem "Alten"
				ListViewItem oOldItem = (ListViewItem)oOperation.Data;	// Objektcast
				_lvMyListView.Items[oOldItem.Index] = oOldItem;
				break;
			}
		default:
			{
				// Wenn wir hier heraus kommen haben wir etwas falsch gemacht und nicht alle Operationen, die wir definiert haben auch oben abgefragt.
				return;
			}
	}
}

Das war's schon. Der Redo funktioniert genau so. Alle Elemente, die wir vom Undo-Stack abheben kommen nach der Verarbeitung auf den Redo-Stack.
Doch hier gibt es wieder etwas zu beachten. Was zum Beispiel, wenn der Nutzer 3 ListView-Elemente hat. Er fügt 3 Weitere hinzu und macht die 3 letzten Operationen wieder rückgängig. Es sind also 3 ListViewItems (Die vom Start) in der ListView, sowie 3 Operationen im Redo-Stack. Jetzt fügt der Nutzer ein Element hinzu, welches oben auf dem Undo-Stack landet. Jetzt stellt der Benutzer durch einen Bedienfehler die 3 gelöschten Elemente wieder her. Bei einem der Elemente geschieht Folgendes: Es hat den selben Index, wie ein bereits vorhandenes Element und es wird eine Fehlermeldung ausgegeben. Das ist nur einer von vielen möglichen Fehlern. Sie alle aufzuzählen wäre undenkbar. Und wenn dann noch Operationen über andere Controls hinzukommen würde es spätestens bei der Fehlerbehandlung in einem endlosen if-else-Gehangel enden. Zudem können sich Fehler überlagern, was die Sache noch komplizierter macht. Man muss also pro Fehler alle anderen Fehler mit überprüfen. Ich werde das nicht demonstrieren, damit keiner auf die Idee kommt so einen Unfug zu versuchen. Besser ist es, den gesamten Redo-Stack zu löschen (die oben Angesprochene Clear() Methode des System.Collection.Generic.Stack<> Templates hilft uns dabei), denn wer für gewöhnlich etwas Rückgängig macht hat nicht vor es nach einer anderen Operation wiederzuholen. Wenn er das wöllte, dann würde er das gelöschte Element durch Bearbeiten wiederholen. Die Redo-Methode ist lediglich als "Sicherung" gedacht, falls man einen Schritt zu weit zurück gegangen ist. Für unsere eigentliche Implementierung ist also zunächste wichtig, die bisherigen Methoden anzupassen:

// Definition und Initialisierung
System.Collections.Generic.Stack<Operation> m_oRedoStack;
m_oRedoStack = new System.Collections.Generic.Stack<Operation>();

// ... weiterer Code ...

// Hinzufügen eines ListViewItems in die ListView _lvMyListView
public void AddItem(ListViewItem item)
{
	Operation oOperation = new Operation();
	oOperation.Data = item;		// item muss nicht gecastet werden, weil jeder Typ abstahiert object sein kann.
	oOperation.Type = OperationType.otINSERT_ITEM;
	m_oUndoStack.push(oOperation);	// Operation-Objekt oben auf dem Stack auflegen
	_lvMyListView.Items.Add(item);
	
	// Leeren des Redo-Stacks
	m_oRedoStack.Clear();
}

// Löschen eines ListViewItems aus der ListView _lvMyListView
public void RemoveItem(ListViewItem item)
{
	Operation oOperation = new Operation();
	oOperation.Data = item;
	oOperation.Type = OperationType.otREMOVE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items.Remove(item);
	
	// Leeren des Redo-Stacks
	m_oRedoStack.Clear();
}

// Ändern eines ListViewItems in der ListView _lvMyListView
public void SetItemText(int index, string text)
{
	// Fehlerbehandlung, falls index nicht exestiert der Einfachheit wegen weggelassen
	Operation oOperation = new Operation();
	oOperation.Data = _lvMyListView.Items[index];
	oOperation.Type = OperationType.otCHANGE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items[index].Text = text;
	
	// Leeren des Redo-Stacks
	m_oRedoStack.Clear();
}

public void undo()
{
	Operation oOperation = m_oUndoStack.pop();	// Wir holen uns die letzte Operation und löschen sie vom Stack
	
	switch(oOperation.Type)
	{
		case OperationType.otINSERT_ITEM:
			{
				// Die Operation war "Einfügen", also müssen wir das ListViewItem wieder "Löschen"
				_lvMyListView.Items.Remove((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otREMOVE_ITEM:
			{
				// Genau umgekehrt
				_lvMyListView.Items.Add((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otCHANGE_ITEM:
			{
				// Das geänderte ListViewItem steht in der ListView, das "Alte" im Stack, also überschreiben wir das "Neue" einfach mit dem "Alten"
				ListViewItem oOldItem = (ListViewItem)oOperation.Data;	// Objektcast
				_lvMyListView.Items[oOldItem.Index] = oOldItem;
				break;
			}
		default:
			{
				// Wenn wir hier heraus kommen haben wir etwas falsch gemacht und nicht alle Operationen, die wir definiert haben auch oben abgefragt.
				return;
			}
	}

	// Verschieben der Operation auf den Redo-Stack
	m_oRedoStack.Push(oOperation);
}

Alles was uns jetzt noch fehlt ist die Methode zum wiederholen der Operationen, also die "Redo"-Methode. Wenn wir etwas wiederholen ist es wichtig die Operation wieder auf den Undo-Stack zu legen, denn schließlich wollen wir die Operationen auch wieder rückgängig machen wollen. Ausserdem könnte das Vergessen dieses Schrittes zu genau so fatalen Fehlern wie oben beschrieben führen. Wichtig ausserdem ist, dass wir die Operation, die wir im OperationType Enumerator übergeben bekommen für Redo-Zwecke nicht umkehren, denn "Redo" ist ein "Schritt in die selbe Richtung", den der Benutzer schon einmal getan hat. Eine Implementierung der Redo-Methode könnte also so aussehen:

public void redo()
{
	Operation oOperation = m_oRedoStack.pop();
	
	switch(oOperation.Type)
	{
		case OperationType.otINSERT_ITEM:
			{
				_lvMyListView.Items.Add((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otREMOVE_ITEM:
			{
				_lvMyListView.Items.Remove((ListViewItem)oOperation.Data);
				break;
			}
		case OperationType.otCHANGE_ITEM:
			{
				// Selbe Funktionsweiße wie bei Undo, nur das auf dem RedoStack das "Neue" Item liegt
				ListViewItem oNewItem = (ListViewItem)oOperation.Data;
				_lvMyListView.Items[oNewItem.Index] = oNewItem;
				break;
			}
		default:
			{
				return;
			}
	}

	// Zurückschieben der Operation auf den Undo-Stack
	m_oUndoStack.Push(oOperation);
}

Abschließende Worte
Ich hoffe ich konnte mit diesem Tutorial ein paar von den Lesern inspirieren, bzw. habe zum Verständniss und der Ansatzfindung hinter "Undo/Redo" beigetragen. Die Organisation und Implementierung einer Undo- und Redofunktion über einen Stack ist nur eine Möglichkeit von vielen. Denkbar wäre Beispielsweiße auch eine Implementierung über einen Heap, was den Vorteil hätte, dass man lediglich mit einer Variabe und "leftSide", bzw. "rightSide" arbeiten würde (Was dem "Umstapeln" zwischen unseren Stacks entspricht), aber große Ersparnisse an Speicher und Rechenaufwand hätte man dort nicht. Ich finde die Organisation als Stack recht sinnvoll. Wer also verbesserungsbedürftige Stellen, Kritikpunkte oder Tipps hat kann diese gern mit mir Diskutieren oder hier anbringen.

In diesem Sinne: Happy Coding,

• Aschratt.

**:::

Wenn wir wie im obigen Fall mit Klassen auf Controls (ListViewItem -> ListView) arbeiten, dann wird beim kopieren lediglich eine Referenz kopiert. Wenn wir aber zum Beispiel folgenden Code betrachten...

	Operation oOperation = new Operation();
	oOperation.Data = item;
	oOperation.Type = OperationType.otREMOVE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items.Remove(item);

Ist dies sehr fatal. Hier wird lediglich eine Referenz des ListViewItems als Data Objekt abgelegt (Logisch, denn object korrespondiert zu void*, das heißt "object" ist eine Referenz eines Objektes. Damit wird gewährleistet, dass object immer nur 4 Byte groß ist). Fatal ist dies für unsere undo()-Methode:

switch(oOperation.Type)
{
	// ...	
	case OperationType.otCHANGE_ITEM:
	{
		ListViewItem oOldItem = (ListViewItem)oOperation.Data;
		_lvMyListView.Items[oOldItem.Index] = oOldItem;	// FEHLER!!! oOldItem == _lvMyListVIew.Items[oOldItem.Index]!
		break;
	}
	// ...
}

Da "oOperation.Data" eine Referenz auf das geänderte ListViewItem ist, steht der neue Text auch im Data Objekt im Undo-Stack. Unser alter Text ist somit verloren und durch den Garbage Collector schon lange über den Jordan gegangen. Wir müssen uns also eine Alternative einfallen lassen. Was wir benötigen ist eine Kopie des ListViewItems, vor dem Editieren:

public void SetItemText(int index, string text)
{
	Operation oOperation = new Operation();
	oOperation.Data = _lvMyListView.Items[index].Clone();	// Erzeugen einer Kopie
	oOperation.Type = OperationType.otCHANGE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items[index].Text = text;
	
	// Leeren des Redo-Stacks
	m_oRedoStack.Clear();
}

Problem bei der Sache: Unsere Kopie des ListViewItems ist im Grunde genommen ein eigenständiges ListViewItem. Da es jedoch auf keiner ListView liegt ist der Index (der schreibgeschützt ist) immer -1. Das hat Auswirkungen auf das Wiederherstellen des Items:

switch(oOperation.Type)
{
	// ...
	case OperationType.otCHANGE_ITEM:
		{
			ListViewItem oOldItem = (ListViewItem)oOperation.Data;
			_lvMyListView.Items[oOldItem.Index] = oOldItem;	// FEHLER!!! oOldItem.Index = -1 --> Ungültiger Arrayindex!
			break;
		}
	//...
}

Es ist zwar etwas umständlicher, aber von nöten, dass wir uns für diese Zwecke eine extra Struktur anlegen, die auch unseren Index festhält:

public struct CachedListViewItem
{
    private System.Windows.Forms.ListViewItem m_oItem;
    private int m_oIndex;

    public System.Windows.Forms.ListViewItem Item
    {
        get
        {
            return m_oItem;
        }
        set
        {
            m_oItem = value;
        }
    }

    public int Index
    {
        get
        {
            return m_oIndex;
        }
        set
        {
            m_oIndex = value;
        }
    }
}

In dieser Struktur legen wir unsere Kopie und den Index des Items ab:

public void SetItemText(int index, string text)
{
	Operation oOperation = new Operation();
	CachedListViewItem oItem = new CachedListViewItem();
	oItem.Item = _lvMyListView.Items[index].Clone();	// Erzeugen einer Kopie
	oItem.Index = index;
	oOperation.Data = oItem;
	oOperation.Type = OperationType.otCHANGE_ITEM;
	m_oUndoStack.push(oOperation);
	_lvMyListView.Items[index].Text = text;
	
	// Leeren des Redo-Stacks
	m_oRedoStack.Clear();
}

Für das Wiederherstellen müssen wir jetzt auf diese Struktur casten:

public void undo()
{
	switch(oOperation.Type)
	{
		// ...
		case OperationType.otCHANGE_ITEM:
			{
				CachedListViewItem oOldItem = (CachedListViewItem)oOperation.Data;
				_lvMyListView.Items[oOldItem.Index] = oOldItem.Item.Clone();
				break;
			}
		// ...
	}
}

public void redo()
{
	switch(oOperation.Type)
	{
		// ...
		case OperationType.otCHANGE_ITEM:
			{
				CachedListViewItem oNewItem = (CachedListViewItem)oOperation.Data;
				_lvMyListView.Items[oNewItem.Index] = oNewItem.Item.Clone();
				break;
			}
		// ...
}

Bei der Zuweisung

_lvMyListView.Items[oNewItem.Index] = oNewItem.Item.Clone();

kann das Clone auch weg gelassen werden. Sollte der Stack gelöscht werden bleibt die Referenz im Speicher, weil das ListViewItem auf der ListView referenziert wird. Der GarbageCollector merkt das und löscht es nicht.

Weiterhin wichtig für unsere undo()-Methode ist noch eine Änderung. Im Moment legen wir das alte Item, was wir wiederhergestellt haben auf dem Redo-Stack ab. Das wollen wir aber ja nicht, wir wollen ja später das neuere Item wiederherstellen. Darum müssen wir die Operation noch neu setzen:

public void undo()
{
	switch(oOperation.Type)
	{
		// ...
		case OperationType.otCHANGE_ITEM:
			{
				CachedListViewItem oOldItem = (CachedListViewItem)oOperation.Data;
				CachedListViewItem oItem = new CachedListViewItem();
				oItem.Item = _lvMyListView.Items[oOldItem.Index].Clone();
				oItem.Index = oOldItem.Index;
				oOperation.Data = oItem;
				_lvMyListView.Items[oOldItem.Index] = oOldItem.Item.Clone();
				break;
			}
		// ...
	}
}

Selbiges gilt auch für die redo()-Methode.

Grüße,

• Aschratt

Schlagwörter: Undo Redo Stack System.Collection.Generic.Stack

Hallo Aschratt

Danke für den Beitrag.
Der Vollständigkeits halber noch die zwei anderen Mögichkeiten, bzw. die Möglichkeiten per Command Pattern:

• Multilevel-Undo/-Redo mit dem Command-Muster
• Commandpattern mit Closures - Do/Undo/Redo implementieren

Gruss Peter