Filters & Sieves in Prograph CPX

Fooling the user gets the job undone

By Kurt Schmucker, Apple Computer, Inc.

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 method - the depths of unmodularity! A more uniform, modular, and scalable mechanism is needed. One way to do this is to combine the notions of filters and sieves with that of command objects. Each command object would have a Filter method that would traverse the objects in the document, and enable that command object to specially process certain objects, in whatever way is necessary for the operation that the command implements. The view would call the current command’s Filter method to perform tasks like drawing or processing of mouse clicks.

Let’s sketch out how this more modular approach would work for the same operation examined above: changing a shape’s fill pattern in a structured graphics editor. Assume the existence of TShapeView, TShapeDocument, and TChangeFillPatternCommand classes that provide the standard behaviors that you would expect in an application framework like MacApp, TCL, or the ABCs. In addition to this standard behavior, command objects have a FilterAndDo method, documents have an EachShapeDo method, and views have a slightly modified Draw method as shown here (expressed in a generic textual object-oriented language that just happens to look a lot like Object Pascal):

PROCEDURE TShapeGraphicalView.Draw(area: Rect);

 PROCEDURE FilterAndDrawShape(shape: TShape);
 BEGIN
 shape.Draw;
 END;
BEGIN
 SELF.fDocument.EachShapeDo(FilterAndDrawShape);
END;

PROCEDURE TShapeDocument.EachShapeDo(
 PROCEDURE DoToShape(shape: TShape));
VARtempShape:  TShape;
 shapeList: TList;
BEGIN
 IF gLastCommand <> NIL THEN
 IF gLastCommand.fDone THEN
   IF gLastCommand.fFiltering
 THEN gLastCommand.FilterAndDo(DoToShape)
 ELSE BEGIN
 shapeList := SELF.GetShapeList;
 tempShape := shapeList.First;
 WHILE (tempShape <> NIL) DO
 BEGIN
 DoToShape(tempShape);
 tempShape := shapeList.Next;
 END;
 END;
END;

PROCEDURE TChangeFillPatternCommand.FilterAndDo(
 PROCEDURE DoToShape(shape: TShape));

VARtempShape:  TShape;
 shapeList: TList;
BEGIN
 shapeList := SELF.GetShapeList;
 tempShape := shapeList.First;
 WHILE (tempShape <> NIL) DO
 BEGIN
 IF (tempShape <> 
 SELF.fNewlyPatternedShape)
 THEN DoToShape(tempShape); 
    {this shape is NOT the special one }
 ELSE BEGIN
 tempShape := tempShape.Clone;
 tempShape.SetFillPattern(newFillPattern);
 DoToShape(tempShape); 
 tempShape.Free;
 END;
 tempShape := shapeList.Next;
 END;
END;

Or, as expressed in Prograph, as shown in Figure 3.

Figure 3. Basic use of filters and sieves with command objects

Filters and Sieves in CPX

Approach

There were two somewhat conflicting goals in my approach to adding filters, sieves, and transparencies (FST) to the Prograph ABCs: my first goal was to produce a design that was good enough to use on several Prograph projects I was working on, and hopefully, would be useful to other Prograph developers. The second goal was to modify the ABCs as little as possible so that the FST section would be easy to port to new versions of the ABCs as they were released. These goals are in conflict because to FST requires modifications throughout the command handling apparatus of a framework, thus I had to make some compromises.

I had to be able to distinguish a command that used FST from a command that didn’t. I also had to add an extra operation in the command handling algorithm: committing a FST command operation just before it was disposed. I had to have both the filtering mechanism for structured documents and the transparency mechanism for unstructured ones. Thus, the obvious steps looked like:

• adding a boolean ‘Filtering?’ attribute to Command

• adding a ‘Commit Command’ step to the Commander’s processing of commands

• adding a Filter & Do method to Command, making use of the Prograph inject mechanism to have this single method accomplish different tasks, and

• adding a new drawing step (transparencies) to the already multilevel drawing algorithm used in the ABCs.

Adding a boolean ‘Filtering?’ attribute to Command

I expected this to be the easiest step, but it turned out to be the hardest. While adding an attribute to a class in Prograph is just a single mouse click, there are a lot of side effects when that class is the ancestor to a large number of classes with aliases in many different sections, and when there are instances of that class (or its subclasses) scattered throughout your application. The Command class is the ancestor of more than 15 classes in the ABCs, and instances of many of these classes (e.g., Menu Behavior, (Click or Draw) Behavior, etc.) are created by the editors while you are designing your application with Prograph’s graphical interface builder, the ABEs. In fact, after I finally realized that adding the attribute was not going to work, just backing out of this change took over an hour.

I still needed to add something like a boolean attribute to Command. What I ended up doing was using a method as a virtual attribute. Since the value of the Filtering? attribute that I wanted to add was not going to change for the lifetime of any particular instance, and since the value would be the same for all instances of a given Command subclass, I added a method Filtering? to Command that just returns FALSE. When you subclass Command to make a filtering command, you just overshadow the Filtering? method and change its implementation to return TRUE.

Adding a ‘Commit Command’ step to the Commander

This turned out to be very easy. In the standard version of the ABCs, the Commander disposes of the last command object as the first step in processing a new one (in Commander/Do Command). While I could have just instructed Prograph programmers using my FST unit to perform any commit action in their command subclass’s Dispose method, I felt this was probably something that would be a common source of programming errors, so I added a Commit method to Command, and a call to this method in Commander/Do Command. Most filtering subclasses will override Commit to perform the operation associated with the command, and store the results in the document.

Adding a Filter and Do method to Command

This turned out to be less elegant than I hoped for, primarily because the differing arities for the different uses of Filter & Do make a single implementation of Filter & Do impossible. When the task to be done by the filtering command object is drawing, then there is no return value from the operation. However, when the task is determining the set of objects currently shown to the user, there is a return value, the list of objects. And when the task is processing a mouse click, there is an additional input value, the click point.

The inject operator in Prograph is powerful and it lets you do some really nifty stuff, but the methods that use inject have the same arity matching requirements as any other method. This arity difference meant that one single abstract Filter & Do method could not be designed. In effect, what I had to do was to implement three methods: Filter-&-Do-one-input-and-no-return-value, a Filter-&-Do-with-one-input-and-one-return-value and a Filter-&-Do-with-two-inputs-and-one-return-value. It didn’t feel real elegant, but there didn’t seem to be any way around it. (I guess I shouldn’t feel so bad, since even the designers of Smalltalk had to make exactly the same compromise that I did. The Smalltalk equivalent of inject is perform; if you look at the Smalltalk sources you will see the inelegant but necessary perform: (one arguments), perform: with:(two arguments), perform: with: with: (three arguments), and perform: withArguments: (many arguments).)

Rather than pick method names that were so generic as to be almost meaningless, I decided to name the three Filter & Do variants in a way that suggested their most common uses: Filter & Draw, Filter Virtual Document, and Filter & Process Click. All filtering commands must override all of these methods.

Adding transparencies

Adding transparencies to the ABCs turned out to be quite straightforward. After the standard View/Draw Content method executes, the Draw Virtual Content checks to see if there is a filtering command currently being stored by the Commander. If so, then that command is given the opportunity to draw its ‘transparency’ on top of the already drawn view. (See Figure 4.) It is up to the individual application and command to determine how to store this virtual data, and how to make sure that the virtual data can both add to and subtract from the view of the data shown to the user.

Figure 4. Adding transparencies to the ABCs.

Using Filters and Sieves

I implemented two small applications that use my FST section. While these applications are far from being full-bodied applications, they do show how these techniques can be used in real products.

Structured Graphics Editor

The small structured graphics editor that I built has one window that uses ordinary vanilla command objects, and one that uses command objects with filters and sieves. (See Figure 5.) There are only 4 operations that a user of this app can perform on the geometric shapes shown in the window: select any number of shapes, clear any number of shapes, rotate any number of shapes by 45°, and recolor a single shape. Of these operations, all are undoable except selection. In the standard window (with vanilla commands) undo for each of the undoable operations is provided with the standard undo mechanism, but in the filtering window, undo for all three of the commands is provided for with filters and sieves. Thus, examining the source for this application will enable you to quickly compare and contrast these two approaches to undo. I purposely designed and implemented these windows to be as independent as possible to assist you in this comparison. While it would have been possible to have either as the subclass of the other, I believed that this would have been an arbitrary code sharing decision, and not a conceptually clean design that would be the easiest to learn from.

Figure 5. The small structured graphics editor
modified to use filters and sieves for undo.

This application is a modification of the MiniQuadWorld app described in an earlier MacTech Magazine article. I tried to make the minimal modifications to this app to add the use of filters and sieves for undo, so this app is indicative of the kind of work you would have to do to add filters and sieves to an existing application.

Let’s examine what I had to do to add filters and sieves to this app. First, I had to make a new document subclass that let the current command control how a search for a particular object in the document was conducted when the user clicked in the window’s view. This meant that I had to modify the Find Quad under the Click method, but this was the only method I had to change. (I did have to add one new Document method: Get Virtual QuadList.) Since I was not using transparency in this app, my view class descends just from View and not from View with Transparency. I did have to modify this view’s Draw method to let the command object manage the drawing operation. A new window subclass was needed only because the ABCs require a new window subclass for every kind of window, not because of filters and sieves. I then added new command classes for each of the undoable operations.

To make a command subclass use filters & sieves involved the following steps (see Figure 6):

Figure 6. The method overloading necessary to use filters and sieves
in a command object.

• Make sure that the command’s Do, Undo, and Redo just set things up for the particular state desired, as opposed to actually performing the command’s basic operation (e.g., clearing)

• Overload the Filtering? method and change its return value to TRUE

• Overload the Filter & Draw and the Filter & Process Click methods to control drawing and mouse click operations when the command has been executed but not committed. Figures 7 and 8 show these methods for the Filtered Rotate Quad Cmd class.

• Add a method to return the set of objects currently being shown to the user, the virtual document data. In this application, this method is named Get Virtual Quadlist.

Figure 7. The Filtered Rotate Quad Cmd/Filter & Draw method.

Figure 8. The Filtered Rotate Quad Cmd/Filter
& Process Click method.

Icon Editor

Figure 9 shows the main window of the small icon editor I wrote that uses transparencies to implement undo for the icon editing operation. (The functionality of this small app is modeled after the icon editing app used in the MacApp 3.0 tutorial.)

Figure 9. The main window of the icon editing app
which uses transparencies to implement undo for the editing operation.

Transparencies turned out to be a very natural and easy way to implement undo in this application. Figure 10 shows the important pieces of code involved in the view’s drawing operation.

Figure 10. The transparency drawing code for the icon view.
This code retrieves the data stored in the transparency and draws that data
in a manner similar to, but not identical with, the main drawing code of the view.
The difference is that the transparency has to be able to, in effect,
erase portions of what was drawn by the main drawing code.

What Worked and What Didn’t

This all worked about like I expected it would, although with a few small surprises. Because much of the ABCs standard functionality (saving, printing, etc.) is not implemented with undoable commands, and because I was now fooling the user by presenting something that wasn’t really stored in the document, I had to take care not the fool the framework also. For example, when printing or saving, I had to make sure that any filtering command was committed first.

Certainly, if Prograph International added FST to a future release of the ABCs, they would be able to do a smoother job of integrating, making the job of the application implementor a little easier. Until then, I hope my filtering unit is of some use.

References

[1] Schmucker, Kurt. “Commands and Undo in Prograph CPX”, MacTech Magazine, January 1995.

[2] Schmucker, Kurt. Object Oriented Programming for the Macintosh, Hayden Book Company, 1986.