Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-lcc!pyramid!voder!apple!lsr
From: lsr@apple.UUCP (Larry Rosenstein)
Newsgroups: comp.sys.mac
Subject: Re: Filtering as a way of implementing undo
Message-ID: <886@apple.UUCP>
Date: Sun, 31-May-87 20:56:42 EDT
Article-I.D.: apple.886
Posted: Sun May 31 20:56:42 1987
Date-Received: Tue, 2-Jun-87 03:31:36 EDT
References: <8705130929.AA17766@cogsci.berkeley.edu>
Reply-To: lsr@apple.UUCP (Larry Rosenstein)
Organization: Advanced Technology Group, Apple Computer
Lines: 108

In article <19205@ucbvax.BERKELEY.EDU> oster@dewey.soe.berkeley.edu.UUCP (David Phillip Oster) writes:
>
>I know that this is how MacApp does it, but frankly I've never understood
>why:

MacApp only provides a framework for implementing Undo; it does not require
that you use a filtering approach.  Most commands are implemented by saving
the necessary document state and restoring it if Undo is chosen.

As you said, there are disadvantages to the filtering approach.  It does
mean that the NEXT command could take longer depending on whether the
previous command needs to be committed.  

>2.) A filter implementation of undo seems no better from a storage
>usage point of view:
>  Let's take a common, but tougher case than the one Larry used:
>suppose, in a text editor you do a complex pattern-matching
>search-and-replace command that scans an entire large document, doing

In this case, there is no good way of implementing Undo.  If you look at
existing applications, you will see that most of them punt and make the
operation non-Undoable.

If you have a lot of memory or disk space and the amt. of text is small,
then saving the entire document would be the easiest approach.
Implementing a filter might be difficult, because you couldn't record the
changes in a very compact form, and couldn't apply them very efficiently.

One thing you should not do is prevent the user from making the change
simply because there is not enough memory, disk space, etc.  You should fall
back to making the operation non-Undoable.  The other thing you should not
do is make the operation non-Undoable without getting permission from the
user first.

Changing the font of some text or the color of an object is different.  The
storage space required by the filter is much less, also it takes less
processing time to apply the filter. 

>3.) A filter implementation of undo seems bad from a programming
>complexity point of view.
>  A filter implementation of undo requires that you write, for each
>command that mutates the data structure, a routine that does the real
>work, and also a routine that pretends to have done the work.  These

This is not a problem.  

Normally you would implement a set of access routines that the rest of the
program uses to access the data structures.  These access routines would
hide the existence of filters from the rest of the application.

In MacApp, the data is stored in a Document object, and normally you
implement methods of the Document to access the data.  In addition,
undoable commands are implemented using Command objects, so the knowledge
about doing, undoing, and committing the command (ie, whether there is a
filter and how to apply it) is isolated in one place.

>structure back if the user says to.  You need to write the mutator
>function, the preamble function, and the inverse-mutator function. I
>use this scheme in my programs. One of the nifty things about this
>scheme is that the mutator function is often identical to the
>inverse-mutator function. (Copy-to-clipboard, rename-file,

Unfortunately, this is not always the case.  Stretching an object can't be
undone this way without losing information, because of rounding in the
arithmetic.  (This is especially true if the stretch factor is large.)

>  Another advantage of the actually-do-it school of undo is that if I
>ever decide to implement more undo than just undo-the-last-operation,
>all I need do is manage a list of those records that my preambles
>made for me. Just takes some space. On the the other side, the
>filter-scheme of undo means I'd have to keep layering filters between
>the real data and what the user sees. Each filter takes compute power
>each time it is used (imagine scrolling through a document that had to
>percolate the data through 10 layers of active filter before you could
>see the result of your scroll command.)

Everything you said in your message (including the paragraph above) is
absolutely true.

The key words above are "just some space".  The purpose of filtered Undo is
to save memory space by using processing time.  On the Macintosh, memory
space is generally more limited than processing time, therefore filtering
is a viable way of implementing Undo.  On a machine with virtual memory or
large hard disks, then filtering is not as useful.

It is true that filtering is more difficult to implement than just saving
the document state.  It is also a technique that programmers might not think
of at first (which is why I mentioned it in the first place).

I'm not saying that filtering should be used for all operations (or even
all operations within a single program).  There are cases, however, where
creating the filter and applying it doesn't take an excessive amount of
processing power, compared to the amount of memory you would have to use to
save the entire state.  For those cases, filtering can be a good
alternative.


Thanks for the good comments!

-- 
Larry Rosenstein

Object Specialist
Apple Computer

AppleLink: Rosenstein1
UUCP:  {sun, voder, nsc, mtxinu, dual}!apple!lsr
CSNET: lsr@Apple.com