http://www.developer.com/

Back to article

Working With Design Patterns: Memento


January 10, 2008

A good user interface allows an end user to take back, or undo, operations that they performed. Similarly, the user should be able to redo previously "undone" operations. Just about everyone is familiar with—and often completely dependent on—the ability to revert from undesired changes to a Word document.

Command: The Basis for Undo/Redo

There are many ways to support undo and redo, but the command pattern is the basis of a clean and solid solution. With the command pattern, you represent each operation as a unique object. As the user executes operations, corresponding command objects are stored in a master list. As long as each command can support being "undone," undo and redo is a simple matter of tracking back and forth through this command list.

Listing 1 shows the Command interface, which specifies that all Command implementations must implement execute, redo, and undo methods. Listing 2 contains code for a class, CommandStack, that manages the master list of commands.

Listing 1: The Command interface.

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

Listing 2: CommandStack.

import java.util.*;

public class CommandStack {
   private LinkedList<Command> commandStack =
      new LinkedList<Command>();
   private LinkedList<Command> redoStack =
      new LinkedList<Command>();

   public void execute(Command command) {
      command.execute();
      commandStack.addFirst(command);
      redoStack.clear();
   }

   public void undo() {
      if (commandStack.isEmpty())
         return;
      Command command = commandStack.removeFirst();
      command.undo();
      redoStack.addFirst(command);
   }

   public void redo() {
      if (redoStack.isEmpty())
         return;
      Command command = redoStack.removeFirst();
      command.redo();
      commandStack.addFirst(command);
   }
}

CommandStack encapsulates two stacks—a stack of commands executed, and a stack of commands that have been undone. As a command is executed, it's placed on the command stack. The undo operation removes the last command object from this command stack, undoes it, and places it on the redo stack. The redo stack reverses the sequence, removing from the redo stack, redoing the operation, and adding it back to the command stack (so that it can be undone again if necessary).

Note: Executing a command triggers the clearing of the redo stack. After executing a command, it may no longer make sense to redo a command that was previously undone. This mirrors how a user expects redo behavior to work and avoids otherwise confusing behavior.

The Memento

A memento represents something you want to hold onto (and no, it's not a chewy candy). In software design, the memento pattern provides a preferred way to hold onto information. Memento of course has other uses, but it's often applied as part of a solution to implementing undo and redo.

To support undo, an application must be able to revert to the state in which it existed before a user executed an operation. There are at least a couple ways you can implement a command's revert operation. If you can directly reverse an operation, undo is a simple matter of storing a list of executed operations, each associated with a reversal operation. For example, in a very simple calculator that supports addition and subtraction, you can revert to a prior value by reversing the operation. If a user added 5 to an initial value of 3, undo is a simple matter of subtracting the same quantity (5) from the current value of 8.

Sometimes, however, the prior state must be stored. Perhaps reversing an operation is too complex or not even feasible. As an example, consider a drawing application where random objects are drawn upon a screen. The paint portion of such a user interface must maintain a complete list of all objects to be drawn. Instead of trying to undraw a single object, the simpler approach is to store the complete list of objects prior to executing each command. This stored list is the memento. The memento is kept along with the associated command object.

Listing 3 shows ColoredPath, a model class that stores the coordinates for a polygon and its color. The PathCanvas class (see Listing 4) is the model class representing the composite drawing that contains all of the colored polygons.

Listing 3: ColoredPath.

import java.awt.*;
import java.awt.geom.*;

public class ColoredPath {
   private GeneralPath path;
   private Color color;

   public ColoredPath(GeneralPath path, Color color) {
      this.path = path;
      this.color = color;
   }

   public GeneralPath getGeneralPath() {
      return path;
   }

   public Color getColor() {
      return color;
   }
}

The most relevant portion of PathCanvas is its implementation of the MementoOriginator interface. When you request execution of a command that alters the PathCanvas, that command first must be able to ask for the current state of the PathCanvas. The PathCanvas originates this current state by creating a Memento object in the getMemento method. For the PathCanvas, the Memento is simply a copied collection of the ColoredPath objects (see Listing 5).

When you undo a command, it needs to reset the state of the PathCanvas to a prior point in time. A stored Memento object represents this prior point. The method setMemento updates the state of the PathCanvas object.

Listing 4: PathCanvas.

import java.awt.*;
import java.awt.geom.*;
import java.util.*;
import java.util.List;

public class PathCanvas extends Observable implements
   MementoOriginator, Displayable {
   private List<ColoredPath> paths =
      new ArrayList<ColoredPath>();

   public List<ColoredPath> paths() {
      return paths;
   }

   public void add(ColoredPath path) {
      paths.add(path);
      changed();
   }

   public void displayOn(Graphics2D graphics) {
      for (ColoredPath path: paths) {
         Area polygon = new Area(path.getGeneralPath());
         graphics.setColor(path.getColor());
         graphics.fill(polygon);
      }
   }

   public Memento getMemento() {
      List<ColoredPath> pathCopies =
         new ArrayList<ColoredPath>();
      pathCopies.addAll(paths);
      return new Memento(pathCopies);
   }

   @Override
   public void setMemento(Memento memento) {
      paths.clear();
      paths.addAll(memento.getPaths());
      changed();
   }

   private void changed() {
      setChanged();
      notifyObservers();
   }
}

I created the MementoOriginator interface not out of necessity, but to reinforce the class names used in the Design Patterns book. The interface is simply:

public interface MementoOriginator {
   Memento getMemento();
   void setMemento(Memento memento);
}

Listing 5: Memento.

import java.util.*;

public class Memento {
   private List<ColoredPath> paths;

   public Memento(List<ColoredPath> paths) {
      this.paths = paths;
   }

   public List<ColoredPath> getPaths() {
      return paths;
   }
}

The most involved piece of the puzzle is the set of commands themselves. I implemented TriangleCommand and SquareCommand to demonstrate drawing a couple different shapes. Because each command needs to support being executed, undone, and redone, I was able to move some commonality into a superclass AbstractCommand (see Listing 6).

Listing 6: AbstractCommand.

import java.awt.*;
import java.util.*;
import model.*;
import model.PathCanvas;

import commandframework.*;

abstract public class AbstractCommand implements Command {
   private Memento memento;

   private Random random = new Random();
   protected double width;
   protected double height;
   protected PathCanvas canvas;
   protected Color color;

   public AbstractCommand() {
   }

   public AbstractCommand(PathCanvas canvas, double width,
      double height, Color color) {
      this.width = width;
      this.height = height;
      this.canvas = canvas;
      this.color = color;
   }

   public void execute() {
      this.memento = canvas.getMemento();
      transform();
   }

   abstract protected void transform();

   public void undo() {
      Memento redoMemento = canvas.getMemento();
      canvas.setMemento(memento);
      memento = redoMemento;
   }

   public void redo() {
      Memento undoMemento = canvas.getMemento();
      canvas.setMemento(memento);
      memento = undoMemento;
   }

   protected double random(double max) {
      return random.nextDouble() * max;
   }
}

The only real unique part of each command is its ability to transform the canvas by drawing a polygon (perhaps "transform" was not the best method name I could have chosen). The SquareCommand code in Listing 7 shows what one command looks like. TriangleCommand isn't much different.

Listing 7: SquareCommand.

import java.awt.*;
import java.awt.geom.*;
import model.*;

public class SquareCommand extends AbstractCommand {
   private static final int SIZE = 12;

   public SquareCommand(PathCanvas canvas, Dimension size,
      Color color) {
      super(canvas, size.getWidth(), size.getHeight(), color);
   }

   @Override
   public void transform() {
      canvas.add(new ColoredPath(createSquare(), color));
   }

   private GeneralPath createSquare() {
      GeneralPath path = new GeneralPath();
      double x = random(width);
      double y = random(height);
      path.moveTo(x, y);
      path.lineTo(x + SIZE, y);
      path.lineTo(x + SIZE, y + SIZE);
      path.lineTo(x, y + SIZE);
      path.lineTo(x, y);
      path.closePath();
      return path;
   }
}

The real "meat" of the memento pattern is in the three Command implementation methods:

public void execute() {
   this.memento = canvas.getMemento();
   transform();
}

public void undo() {
   Memento redoMemento = canvas.getMemento();
   canvas.setMemento(memento);
   memento = redoMemento;
}

public void redo() {
   Memento undoMemento = canvas.getMemento();
   canvas.setMemento(memento);
   memento = undoMemento;
}

Prior to execution, the command object stores a memento. For undo, the command object obtains the current canvas state (into redoMemento), changes the state to the previously stored memento, and then stores the redoMemento object so that a subsequent redo operation will work. The redo method works similarly.

The memento pattern (see the UML diagram in Figure 1) is really straightforward. Design patterns don't always need to be complex. Sometimes, the most important thing that comes out of design patterns is that they simplify things by providing a consistent solution with recognizable class names.

I've attached the code for your perusal. The lessons always seem to sink in a little better when you can see the code actually working. The attached zip file contains complete source for a simple user interface that demonstrates drawing polygons, as well as undoing and redoing along the way!



Click here for a larger image.

Figure 1: Memento

Download the Code

You can download the code that accompanies this article here.

About the Author

Jeff Langr is a veteran software developer with over a quarter century of professional software development experience. He's written two books, including Agile Java: Crafting Code With Test-Driven Development (Prentice Hall) in 2005. Jeff is contributing a chapter to Uncle Bob Martin's upcoming book, Clean Code. Jeff has written over 50 published articles on software development, with more than a couple dozen appearing at Developer.com. You can find out more about Jeff at his site, http://langrsoft.com, or you can contact him via email at jeff at langrsoft dot com.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date