History Back and Forth

When ever you write a level editor or maybe a turn based game it would be of great help having undo and redo functionality at hand.

Based on the Game Programming Pattens Book from Robert Nystrom I did like to implement an undo / redo history object. The implementation is based on the command pattern by the gang of four.

The whole thing start with a command interface which looks like this

package mygame;

public interface Command {
    public void execute();
    public void undo();
}

The only thing you need in a command is execute and undo. With that you can even make a redo. Really? Really, I'll show you the idea of the history implementation.

package myexample;

public History {
        public void execute(Command command) {}
    public void undo() {}
    public void redo() {}
}

To make the whole thing work you need to encapsulate everything needed to execute the command in your command object, that is of great importance.

For the implementation I used a LinkedList as it was the simplest way I found for this. Of course you can implement as well some ring buffer structure using plain arrays, but I did not had the nerve for this. I'm sure you have.
Ok let's start with the basics. First of all we need to execute the command like this

public void execute(Command command) {
        command.execute();
}

That wasn't too hard, but to be able to undo it, we need to hold that command in a data structure, a linked list in my case.

    private LinkedList<Command> commands;

public History(int size) throws InstantiationException {
    commands = new LinkedList<>();
}

public void execute(Command command) {
    commands.add(command);
    command.execute();
}

public void undo() {
    commands.removeLast().undo();
}

Oh wait what if I undo when the list is empty? Yes it fails, so we need some guards to protect it.

public void undo() {
    if (!commands.isEmpty()) {
        commands.removeLast().undo();
    }
}

That looks not that bad and it works already. But let's improve it a little more. For example does this implementation not limit the number of commands in our history, so let's introduce a size.

    private int size;

public History(int size) throws InstantiationException {
    if (size == 0) {
        throw new InstantiationException("0 is not a valid history size");
    }
    this.size = size;
    commands = new LinkedList<>();
}

And now we have to improve the execute method with this size information, be dropping the first command if we hit the capacity of our history.

public void execute(Command command) {
    if (commands.size() >= size) {
        commands.removeFirst();
    }
    commands.add(command);
    command.execute();
}

A redo would be cool and it turns out to be very simple. We need a linked list for book-keeping.

private LinkedList<Command> redoCommands;
        
public History(int size) throws InstantiationException {
            // ...

    redoCommands = new LinkedList<>();
}

Then we have to store all undoed commands in that redoCommands list.

public void undo() {
    if (!commands.isEmpty()) {
        Command command = commands.removeLast();
        redoCommands.add(command);
        command.undo();
    }
}

Now we are prepared for the redo method

public void redo() {
    if (!redoCommands.isEmpty()) {
        execute(redoCommands.removeLast());
    }
}

One small problem we have to solve, what if we did undo 2 times and then call execute and after that call redo? Yeah it will end up in redo commands which actually should be cleared. So let's clear the redo command list on execute. This is not that easy as the redo itself call execute to have the command book-keeping for free. The easiest way is to have an internal execute which is called by execute and redo and only execute clears the redo commands list.

public void execute(Command command) {
        redoCommands.clear();
    internalExecute(command);
}

public void redo() {
    if (!redoCommands.isEmpty()) {
        internalExecute(redoCommands.removeLast());
    }
}

private void internalExecute(Command command) {
    if (commands.size() >= size) {
        commands.removeFirst();
    }
    commands.add(command);
    command.execute();
}    

And to make it a simple copy&past task to take this into your project here the things you need

package myexample;

import java.util.LinkedList;

public class History {

    private LinkedList<Command> commands;
    private LinkedList<Command> redoCommands;
    private int size;

    public History(int size) throws InstantiationException {
        if (size == 0) {
            throw new InstantiationException("0 is not a valid history size");
        }
        this.size = size;
        commands = new LinkedList<>();
        redoCommands = new LinkedList<>();
    }

    public void execute(Command command) {
            redoCommands.clear();
        internalExecute(redoCommands.removeLast());
    }
    
    public void redo() {
        if (!redoCommands.isEmpty()) {
            internalExecute(redoCommands.removeLast());
        }
    }
    
    public void internalExecute(Command command) {
        if (commands.size() >= size) {
            commands.removeFirst();
        }
        commands.add(command);
        command.execute();
    }

    public void undo() {
        if (!commands.isEmpty()) {
            Command command = commands.removeLast();
            redoCommands.add(command);
            command.undo();
        }
    }
}

That's it folks.

Comments

comments powered by Disqus