Composite Undo

smee, build 8

Build 8 includes the ability to undo tile plots collectively, from mouse press to mouse release, as you would expect from any sane implementation of undo.

In previous builds, the PlotHistory class would maintain a list of Plot objects which contained the state for individual plots, before and after they took place. PlotHistory managed this list, and navigated through it as necessary when calling undo() or redo().

In order to undo and redo multiple plots all at once, I needed some way to group plots in the same "stroke" together.

My list can already hold a bunch of plots, so one option would be to delimit groups of tiles somehow, in the same way a comma might delimit a list of keywords in a line of text. For example, I could introduce a null element into the list to indicate the start of a group of plots. Then I could add all of my plots for that group.

In this scenario, when calling undo() or redo(), I would check the element in the current position in the history. If it was a Plot, I'd undo that single plot. If it was null, I'd loop through the list and keep undoing all the plots I came across until I either hit the end of the list, or another null element. Running up against null would indicate that I'd run into the start of another group of plots.

I discarded this option almost immediately. It's too much song and dance and overcomplicates the issue.

It also requires a "special" value. That is to say, normally elements in the undo history indicate a plot that can be undone. "But, okay, sometimes an element is a magical null value that means the next bunch of elements are the actual plots to be undone! Cool, huh?"

No. Not cool. Special values take something with an obvious or implied usage and warp it into some strange hybrid.

When one value begins to serve multiple purposes based on special cases, it is splitting responsibilities and should be refactored into two values, each one with a distinct purpose. Special values are notorious for unwanted side effects. Best to avoid them altogether.

There is a good example of this here.

With the above in mind, I wanted each element in my undo history to serve a single purpose. That is, undo one or more plots. I had the "one" down with Plot, so it seemed logical to encapsulate "or more" with another class.

I could store a lst of plots in a CompositePlot class, perhaps like so:

class CompositePlot {
    ArrayList<Plot> plot_list = new ArrayList<Plot>();
}

Nothing much to see here. I'm just representing a list of plots, after all!

I would need to get my CompositePlot into the PlotHistory list, but the history declaration uses generics, and is declared to store only Plot objects:

ArrayList<Plot> history;

I could just sidestep the use of generics in favor of a "vanilla" list:

ArrayList history;

With this in place, I would be able to stuff anything I wanted into the list. In order to determine how to undo each element, I could just use instanceof.

For example, I could rewrite undo() in PlotHistory like so:

public void undo() {
    if (position >= 0) {
        Object o = history.get(position--);
        if (o instanceof Plot) {
            Plot plot = (Plot) o;
            map.set(plot.x, plot.y, plot.prevtile);
        } else if (o instanceof CompositePlot) {
            CompositePlot composite_plot = (CompositePlot) o;
            ArrayList<Plot> list = composite_plot.plot_list;
            for (int i = list.size() - 1; i >= 0; i--) {
                Plot plot = list.get(i);
                map.set(plot.x, plot.y, plot.prevtile);
            }
        }
    }
}

However, relying on instanceof and casting in this way defeats polymorphism, which is one of the key benefits of using an object-oriented language.

Instead, I could derive both types of plot classes from a shared ancestor and simply deal with the ancestory class in my history list. I could rename Plot to SinglePlot, and then recreate the Plot class as a simple ancestor, which both would extend.

class Plot {}

class SinglePlot extends Plot { ... }

class CompositePlot extends Plot { ... }

However, even if I did this, I would neeed to define some methods in my base Plot class that were common to both single plots and multiple plots. Otherwise I'd still have to use instanceof on the items in my undo history to determine what type of element I was dealing with so I'd know what data members and methods were available to me for each type of plot.

Since I've only really been storing state in my plot classes, perhaps a better idea would be to model the action involved. That is to say, a Plot should be able to perform the action in question, as well as reverse it. This covers both sides of the coin: undo and redo.

I could eventually develop all sorts of crazy plots, so I want my Plot class to simply define methods that its inheritors should implement. This can be done with an abstract class.

abstract class Plot {
    abstract void undo();
    abstract void redo();
}

I could then modify SinglePlot and CompositePlot to create themselves with all the information necessary to perform both actions in and of themselves. The only additional piece of information they'd really need is the Map upon which they were to operate.

For example:

class SinglePlot extends Plot {
    Map map;
    int x, y, prevtile, tile;
    Plot(Map map, int x, int y, int prevtile, int tile) {
        this.map = map;
        this.x = x;
        this.y = y;

        this.prevtile = prevtile;
        this.tile = tile;
    }
    void undo() {
        map.set(x, y, prevtile);
    }
    void redo() {
        map.set(x, y, tile);
    }
}

CompositePlot would be similarly adjusted.

Now that my base Plot class has methods, they will be available to any class that extends Plot. This means I can now implement PlotHistory without having to rely on instanceof to determine how to perform or reverse my plots.

In other words, I was previously using instanceof to help me discover the type of plot object I was dealing with, so that I could use that object's "interface." That is to say, its methods (and data, though it's good programming juju never to expose data publicly).

Now that my plots are inheriting from a base class which defines methods common to all plots, I can deal strictly with Plot objects in PlotHistory. The interface is now known to me -- undo() and redo() -- no matter what type of plot I am ultimately dealing with.

Since Plot is an abstract class with methods only, and no true shared behavior, I refactor it as an interface.

interface Plot {
    void undo();
    void redo();
}

No changes are required to the rest of my code, because an interface and an abstract class with only abstract methods are for all intents and purposes equivalent. An interface is simply a more idiomatic way to express this in Java. Idiomatic meaning, "the way such and such is commonly done because Java was designed with that in mind" which usually in turn means a less syntactically verbose way of doing something. As you can see, an interface in Java is a little more compact than an abstract class with abstract methods.

Encapsulating an action in a class as I've done here is what is known in design patterns circles as the Command pattern. This is one of the most used patterns out there, and is used extensively in Java's Swing API.

With all of this in place, I could've called it quits, but I wanted a little more flexibility in my design. I wanted to be able to undo any sort of edit in the future, not just tile plots.

Because the Plot interface doesn't really define any methods that imply some sort of relation to plotting tiles, I rename it to Edit.

I want to modify my undo history class to be more all-purpose too. PlotHistory was tightly coupled with the Plot class in previous builds of SMEE, and contained a reference to a Map as well. The Map was needed because the old-style Plot objects only represented simple state -- PlotHistory would crack open each Plot and use its internal instance of Map to perform the actual undo or redo.

Now that my plots have evolved into edits which know how to perform and unperform themselves, I can streamline PlotHistory to simply manage a list of Edit objects. It need not rely on a specific type of plot now, or data specific to those plots, such as the map. So, I rename it to EditHistory, remove the Map reference.

This means I have to create instance of SinglePlot and CompositePlot where appropriate now, outside of the EditHistory class, and pass them in. But that's good, because now I don't have to modify my undo management class when the particulars of specific type of plot changes. EditHistory just manages a list of Edit objects now -- it doesn't know or care what kind of edits they actually are.

Examine the code to see the final implementation, but you'll find it's pretty clean and simple!