Browse Prior Art Database

Equivalent Undo Concept and Its Use

IP.com Disclosure Number: IPCOM000107824D
Original Publication Date: 1992-Mar-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 95K

Publishing Venue

IBM

Related People

Madduri, HH: AUTHOR

Abstract

Many editors provide an "undo" operation that reverses the most recent operation done by a user. Some provide several levels of undo, whereby one can undo not only the most recent operation but several operations, doing one at a time. At least conceptually, there is a stack of operations which can be undone all the way to the bottom, starting from the top. In environments where objects are edited concurrently by multiple subjects, there is a need to undo an operation that is in the middle of the stack. The following is a scheme to achieve such a capability.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Equivalent Undo Concept and Its Use

       Many editors provide an "undo" operation that reverses
the most recent operation done by a user.  Some provide several
levels of undo, whereby one can undo not only the most recent
operation but several operations, doing one at a time.  At least
conceptually, there is a stack of operations which can be undone all
the way to the bottom, starting from the top.  In environments where
objects are edited concurrently by multiple subjects, there is a need
to undo an operation that is in the middle of the stack.  The
following is a scheme to achieve such a capability.

      For some simple editors (such as the text editors), the
following scheme makes it possible to undo any operation in the
middle of update stack.  The key idea is to take the inverse of the
operation (which is in the middle of the stack and needs to be
undone) and apply an equivalent operation to the current state of the
object.  The equivalent operation(s) is obtained by modifying the
inverse operation to absorb the effect of each operation in the stack
that is above the operation to be undone.
      (1)  It is assumed that the object being edited can be
represented by a string of bytes.  More generally, it is a string of
some fundamental entity (for example, if the object we are editing is
a text file, then it is a character; if a binary file, then it is
a bit; if music, then it is a note; and so on).
      (2)  It is assumed that all edits can be expressed in terms of
three simple elementary operations:
      -  insert a string s at position p
      -  delete a string of length l at position p
      -  change the characteristics of a string of length l at
position p
         (The third one represents font/style changes in a text
editor.)
      (3)  Further, any of the three elementary  operations can be
undone by the most straightforward inverse operations (e.g., delete
and insert are mutual inverses; restoring to previous characteristics
of the string is the inverse of the third kind of operation).
      (4) The following algorithm undoes an operation that is n deep
in the operation stack.
"Case I"
      The original operation was an insert, say, I(S,L,P), where S =
string inserted, L= length in bytes, and P= position.
      The undo fo...