an interview question of undo/redo
-
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?
-
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?
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/[^]
-
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?
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
-
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
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
-
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
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
-
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
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
-
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
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.
-
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.
-
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?
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
-
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
-
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.
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
-
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
Having a test on MS-WORD, I find that you delete 20 page then perform undo. After 30 times there's no complain about memory and the action performs very fast. So I assume, there must has other way than "command pattern" to perform such an action. cheers
-
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.
that's not usually true - you can't undo an undo - when you do the first undo, the stack is emptied