Prograph Undo
Volume Number: 11
Issue Number: 3
Column Tag: Visual Programming
Filters & Sieves in Prograph CPX 
Fooling the user gets the job undone
By Kurt Schmucker, Apple Computer, Inc.
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Command objects as implemented in most Macintosh frameworks provide an excellent
way to implement undo for most types of user actions in most types of applications -
most, but not all.
Typically, the command object stores enough information to be able to perform
the action, to be able to undo the action, and to be able to redo the action. In response to
a user action, your code allocates an appropriate command object, initializes that
object, and then returns that object to the framework. The framework will
immediately send the “DoIt” message to this object to have the desired action
performed. The framework holds onto that command object and will automatically send
the “UndoIt” and “RedoIt” messages to the object if the user chooses the Undo or Redo
from the Edit menu. The command object, using its stored data, will then undo or redo
the operation. This completely relieves the developer from the responsibility for the
run-time handling of the Undo menu item. [1]
This scheme works as long as there is enough memory and speed to undo and redo
the operation (which is the whole point of implementing the command object.)
Unfortunately, this is not always the case. For example, consider a structured drawing
program like MacDraw or Canvas. In such a program, the user can select any subset of
the objects that have been drawn and bring those selected objects “to the front,” that
is, re-order them in the z-coordinate. It would not be possible to store the old order
of the objects, in a reasonable amount of memory, in order to be able to effect an undo.
(Admittedly, the definition of ‘reasonable’ is subjective. The straightforward use of
command objects for this Bring to Front operation would require memory proportional
to the number of objects in the entire drawing. The approach explained here requires
only memory for the number of objects in the selection.)
The problem is that sometimes, implementing undo with the basic command
object is inefficient, impractical, or actually impossible. One way around this
difficulty is to use the technique of filters and sieves in conjunction with command
objects. Neither MacApp, TCL, nor the Prograph ABCs implement filters and sieves,
although the Lisa Toolkit did.[2] I have added a rudimentary version of filters and
sieves to the Prograph ABCs, and this article is about that implementation and about
how you can make use of this technique in your applications.
To illustrate these ideas, I have implemented two small applications that use the
technique of filters and sieves: an icon editor, and a modified version of the
MiniQuadWorld application.[2] The Prograph version of both these apps is on the
associated MacTech Magazine diskette, along with the its full source code (in standard
Prograph project and section files).
Introduction to Filters and Sieves
Filters and sieves address situations where there is just not a reasonable way to
implement undo for the user. The operations in question are not those for which undo
is simply impossible - how do you get the LaserWriter to suck back in the paper after
you have issued a print command, for example - but rather those operations that from
the point of view of the average user should be undoable, but which you know will take
too long, consume too much space, or are just computationally intractable. So, if these
operations are too difficult to undo in reality, then we will just fool the user into
thinking that they are undoable. And the way to do that is to fool the user into thinking
that we have ever done them at all: that way we never really have to undo them!
Let’s consider a very small example. Suppose we are implementing a structured
graphics editor like MacDraw or Canvas. Further suppose that we want to provide the
user with the ability to change the fill pattern of a shape, and that to undo this
operation is extremely difficult. (Yes, I know that undoing this type of operation is
actually trivial. Let’s just pretend that it is extremely difficult.) Yet, we want to
provide the user with the ability to undo fill pattern changes. We can provide undo for
this operation if we just fool that user that we have ever performed the fill pattern
change in the first place. Since we haven’t really changed the fill pattern, then
undoing it is easy-we just stop fooling the user and the status quo, which never really
changed, is again revealed. We fool the user by modifying the drawing code something
like this:
PROCEDURE TShapeGraphicalView.Draw(area: Rect);
PROCEDURE FilterAndDrawShape(shape: TShape);
VAR tempShape: TShape;
BEGIN
IF shape <> newlyPatternedShape
THEN shape.Draw {this shape is NOT the special one }
ELSE BEGIN
tempShape := shape.Clone;
tempShape.SetFillPattern(newFillPattern);
tempShape.Draw;
tempShape.Free;
END
END;
BEGIN
SELF.fDocument.EachShapeDo(FilterAndDrawShape);
END;
This code enables the view to check whether each shape in the document is a
special shape that should not be drawn in the normal manner, but rather in a special
way - in this example with a new fill pattern. Thus the shapes in the document are
filtered through a sieve that allows most shapes to pass through and thus be drawn
unchanged. But this sieve catches one special shape, the one referenced by the variable
newlyPatternedShape, doesn’t let this shape be drawn, but rather clones it, changes
the fill pattern of the clone, draws the clone, and then throws the clone away. This is
conceptually represented in Figure 1. (The small code fragment above is not at all
representative of the way in which filters and sieves would actually be used, nor of
how they would be added to an application framework. It is merely illustrative of the
idea of filtering. More realistic code will be shown later.)
Figure 1. Conceptual model of a filter that alters the display of a single object
in the view presented to the user.
What we have done here is to present to the user the illusion that the shape’s
fillPattern has changed. In reality, of course, it has not. Thus, if the user wants to
undo this action, all we have to do is nil out the newlyPatternedShape reference and
re-draw the view. The old pattern will automatically be drawn. If, on the other hand,
the user wants to continue modifying the drawing, then we need only actually perform
the pattern change just before we execute the next request from the user. With this
pattern change thus ‘committed’, we need only nil out the newlyPatternedShape
reference-there is no need to re-draw the view since the screen is already showing the
shape drawn with the new pattern. At this point the pattern change operation cannot be
undone.
It is possible to consider using filters and sieves when the data of the application
is inherently structured, as is the case in graphics editor like MacDraw or Canvas, a
database application, word processor, etc. It is not so easy to apply when the data of
the application is unstructured, as in a bitmap editor. In an application with an
unstructured store, it is not reasonable to have a filter that will distinguish one of the
unstructured bits in the document and process it differently. However, a technique
that can sometimes be used to get an effect similar to that of filters and sieves is the
technique of transparencies. Like filters and sieves, transparencies enable you to
present to the user the illusion of having performed some operation, when in reality
you have not done so. As with filters and sieves, this enables you to easily undo the
operation. With transparencies, you superimpose additional image data in such a way
that it can add to or subtract from the actual image data. Figure 2 illustrates the
conceptual model of transparencies. The technique of filters and sieves, and the
technique of transparencies are similar, so I will describe an implementation that will
add both techniques to the Prograph ABCs.
Figure 2. Conceptual model of a transparency that adds to (or can subtract from)
the display of unstructured data in the view presented to the user.
Filters and Sieves in an Application Framework
The code fragment shown in the last section is not representative of the way in
which you would use filters and sieves in a large application. This is because the
approach in that fragment would lead to a situation in which the quirks of each
operation’s undo requirements would be reflected in the structure of the view’s Draw