mark-p-thomas : State History

This class records the history states of associated with a particular history key, irrespective of the command called. This class holds states for multiple histories, allowing either one global state to track, or separate states, say, associated with one index per object of interest. It basically creates ‘save points’, which a program can switch between if desired.

Benefits of using this library are its flexibility in tracking 1 or multiple states, as well as speed & simplicity in moving between states as the state of interest is returned. A downside is that it requires more memory is required, as each state is saved. Basically, time complexity is O(1) for retrieval, and space complexity is O(n) , for n states saved. A caveat to the time complexity is that O(1) only holds for values. For objects, time complexity is equal to that of cloning the object.

Because the outcome of a command is unknown, this class can only record the current state just before a command. In order to record the latest state reliably & accurately, the pattern of usage is to always pass in the current state with each command execution, undo, or redo. This is so that if there is any missing current state, it can be patched as needed without redundant recordings.

Class Diagram

The StateHistory class is basically a hash map of doubly-linked lists, where each node stores an item state associated with the linked list key, and the ordering of states is set by the linkages of the list. A current state pointer points to the node in this list that is the current state for a particular item. This allows for independent histories & current states of different items.

Operations

One major behavior to point out is that the history object invokes the command delegate passed to it in order to handle preserving state. However, there is no way for the History to know the results of the command. Because of this, when the executeCmd method is invoked, it saves the current state if needed & then appends a placeholder node at the end of the state history set. This placeholder is filled by the next invocation of executeCmd or undo.

NOTE: Mark Thomas Change code, validate with tests, regarding below:

Undo, Redo

The undo & redo methods have a time complexity of O(1). Pass in the key for the desired history to undo/redo and the corresponding linked list pointer will point to the adjacent prior/next state, if it exists. Otherwise, state is unchanged.

ExecuteCmd

The executeCmd method has a time complexity of O(1) for values, or whatever is needed to clone a referenced object. It has a space complexity of O(n), where n reflects the saved copy of the state. Pass in the key for the desired history to save state to, as well as the command to invoke that will change state. The StateHistory object will invoke the command and save the output to the current state.

ADD section on command delegate function

An outline of behavior is as follows:

1. Command invoked

2. Current state is saved (if needed)

3. If current state pointer is not at the end of the state history set, the remaining linked list is trimmed off.

4. A new empty node is appended after. It’s state is set next time undo/redo/execute is called.

5. If a state limit is set & the number of saved states is exceeded, the head nodes of the state history set will be removed until the number of states is at the limit.

	Command invoked, causes action on state
	If current state pointer is not at the end of the state history set, the remaining linked list is trimmed off.
	New state corresponding to the action invoked is appended to the linked list.
	Current state is incremented to the new state.
	If a state limit is set & the number of saved states is exceeded, the head nodes of the state history set will be removed until the number of states is at the limit.

Two important behaviors to note are:

1. State limits apply separately to each state history set, so saving states for one item will not reduce the number able to be saved for another.

2. If a state history set has undo invoked and then executeCmd, a new history branch is created in the linked list and it is no longer possible to redo back to the undone state.

Example Code

Below is some example code of how the library could be used in a React component.

handleCmd (current, unless changed):

history.executeCmd(currentTrack.id, currentTrack.clone(), command);
	setHistory(history);

const [history, setHistory] = useState<StateHistory<Track>>(new...);
const [currentTrack, setCurrentTrack] = useState<Track>();

addTracks(tracks: Track[]) {
	tracks.forEach((track)) => history.addHistorySet(track.id);
	setHistory(history);
}

handleCmd(command: () => void) {
	const track = history.executeCmd(currentTrack.id, command);
	setCurrentTrack(track);
}

handleUndo() {
	const track = history.undo(currentTrack.id);

	...

	setCurrentTrack(track);
}

handleRedo() {
	const track = history.redo(currentTrack.id);

	...
	
	setCurrentTrack(track);
}