Question:

Consider undo in the context of a text editor. Suppose the only operations are 
insert and delete, that is, insert some text somewhere in the document and delete 
some existing text in the document. Consider the possibility of an undo operation 
that can undo previous edits but not only in stack order, that is, you can go go 
back and undo any of the operations without necessarily undoing all the 
operations that occurred after it. 
Consider the problems that this would cause for the implementer. State what those 
problems would be and give a plausible design that would solve the problems. 
There might be two kinds of problems. The first is where it takes some work and 
data structures to do the right thing. 
The second is where the intended effect of the undo operation is ambiguous. Your 
design should handle the first kind of problem. For the second kind of problem 
give an example of a situation where undo is ambiguous and state the various 
interpretations that are possible. then suggest a possible user interface to allow the 
user to resolve the ambiguity. 



Answer:

	The text editor in this example allows only inserts and deletes. The question deals 
with allowing undo commands to be preformed “out of order”. In other words not only is 
the last command available as an undo action but all previous commands will be 
available as an undo action without having to undo all the commands that came after it. 

Some problems that arise from allowing these “out of order” undo’s are having 
access to the command objects in an “out of order” selection and the possibilities of some 
undo commands being ambiguous. With “in order” undo commands the last command 
object created must be available (a stack) but with “out of order” undo commands all 
command objects created (that are deemed undoable) must be available. Also the 
meaning of undo for a command may be ambiguous because of state changes since the 
command was preformed.

	To implement the undoing of commands (insert/delete) this program uses the 
command pattern. The CommandManager class is responsible for managing a collection 
of command objects created by the invoker object. The CommandManager keeps a linked 
list of ConcreteCommand objects that are the commands that have been preformed. 
When the user goes to the undo command in the GIU they are presented with a list 
representing this linked list. In this way the user is able to undo commands “out of order” 
instead of only having the ability to undo the last command issued. The command objects 
encapsulate a specific command and the state information necessary to undo the 
command. In a more complex application some commands may be deemed un-undoable 
for a variety of reasons including the saving of excessive amounts of state.

	To solve the first problem the application uses a linked list to store the command 
objects in and presents a list representation of this data structure to the user when they 
acesses the undo command in the GUI. The command object has its undo method called 
and is removed from the linked list of undoable commands. An example of this situation 
is the following. A user pastes into a document a selection of text (insert1). The user then 
pastes a second text selection (insert2) into the document after (page location as well as 
temporal) the first one. The user then decides to remove paste1 (insert1). This is 
completely unambiguous, as although the state of the document has changed these 
changes did not effect the location of insert1. Now we come to the problem of what if the 
state changes in the document have caused the location of insert1 to change. For instance, 
insert2 was placed before (location in the document) insert1 making the page location for 
insert1 no longer valid. In this case all effected command objects would have to be 
identified and have their page locations adjusted. The command objects would now 
contain the size of the strings being manipulated. Also typing and backspacing (removal) 
would be considered commands.






	In some cases the undoing of a command is truly ambiguous. And no amount of  
“bookkeeping” can solve it. For example  (see diagram 1) the user deletes line 8 (delete1) 
and then later deletes lines 4-10 (delete2). The document now ends at line 3. Now the 
user types in new text for lines 4-8. At this point the user decides to undelete what was 
line 8 (delete1). Where should this line of text go? line9, line8, or line4? No matter how 
good the “bookkeeping” the application is second-guessing the user intentions. The 
application should instead present the user with a message stating that this undo will 
involve placing text in the document, show them the text and warn them that if they 
proceed the text will be placed at the current cursor location. Or if they buy version two 
of this product (kaching!!) the product will allow them to click on where in the document 
they want the text to go without having to leave this message box.