C / C++ / MFC

5-Jul-05 8:16

I got an interview yestoday and was stumbed by the following question,

Suppose you have a MS-Word like application. How do implement the UNDO/REDO function.

Initially, I suggest saving the file everytime with a change. After I spoke it out. I realize that it's impossible. I can't save the file everytime I typed a character. I can't give a resonable solution on this one.

Anybody can help?

Jose Lamas Rios5-Jul-05 8:40

Jose Lamas Rios

5-Jul-05 8:40

It's usually implemented using GOF's Command design pattern[^].

This article, A Basic Undo/Redo Framework For C++[^], might be of help too.

--
jlr
http://jlamas.blogspot.com/[^]

David Crow5-Jul-05 9:18

David Crow

5-Jul-05 9:18

After each action that can be undone, push the current state of the document onto a stack. Each time an "undo" is requested, pop the most recent document state off the stack and notify the view that a "new" document needs to be rendered.

"Ideas are a dime a dozen. People who put them into action are priceless." - Unknown

qudayong5-Jul-05 9:46

5-Jul-05 9:46

If this is a grphic oriented application, I agree that every primitive has a counter to track the refernece number. This is text processing, MS-Word like application. Is it resonable to change the document state everytime when you type a character?

Thank you for response

David Crow5-Jul-05 9:55

David Crow

5-Jul-05 9:55

qudayong wrote:
Is it resonable to change the document state everytime when you type a character?

I don't know if it's a good idea or not. I've never had the need to implement such a feature so I'm not sure how I'd actually do it. It was just a guess.

"Ideas are a dime a dozen. People who put them into action are priceless." - Unknown

Toby Opferman5-Jul-05 9:59

Toby Opferman

5-Jul-05 9:59

Just think of the stack:

character: rowpos, colnumber

For graphics you could have something like:

OperationType, MetaData

For example. So it's just a stack of commands. You could even determine that a "word" is basically a state, so once an entire word is typed you put it on the stack.

So, some considerations could be:

1. How much data are you storing per-letter/state operation?
2. How long of a history buffer do you want?

If you store a letter as being character, followed by rowposition, column number you are actually storing 2 bytes (unicode let's say), then 2 bytes (say you can't have a line longer than 65536), then say 4 bytes (you have up to 4 billion lines in the document).

2+2+4 = 8 bytes per character operation. If you type 10,000 words and say each word is an average of 7 characters, that's 70,000 characters, that's 560,000 bytes or about 560k of undo changes. That's also 70,000 entries in your undo list. Not to mention possible optimizations in referencing and things or combining operations that cancel each other out.

How many does word go back to?

8bc7c0ec02c0e404c0cc0680f7018827ebee

Tim Smith5-Jul-05 13:20

Tim Smith

5-Jul-05 13:20

One option (which is required for usability) is to group words into single undo entries. Otherwise, just undoing single letters gets to be really annoying. Anyway, most people use backspace to correct single letter errors, not undo.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.

qudayong5-Jul-05 15:14

5-Jul-05 15:14

Thank you. You opinion ia valuable

C^hris L^osinger5-Jul-05 15:27

C^hris L^osinger

5-Jul-05 15:27

for text, it's pretty easy:

when the user performs an action, save the action in a stack, then perform the action on the document. for undo, pop the last action off the stack and reverse the action.

the trick is to define 'action' in such a way that you can undo it.

ex. for deleting text, save the deleted text and its position as the action (to undo, insert the deleted text at the position). for inserting text, save the position and the number of characters added (to undo, remove the number of characters at the position).

Cleek | Image Toolkits | Thumbnail maker

qudayong6-Jul-05 1:59

6-Jul-05 1:59

Suppose you have 20 pages file.
You last action is delete 19 pages, and the perform undo. If you perform this action servral times, your stack will be overloaded.

C^hris L^osinger6-Jul-05 2:13

C^hris L^osinger

6-Jul-05 2:13

that's why programs put up messages like "Insufficient space in the Undo buffer to save this action. Do you wish to proceed anyway?" (from the Visual Studio editor)

Cleek | Image Toolkits | Thumbnail maker