How to design undo & redo in text editor?

Question

Part of my project is to write a text editor that is used for typing some rules, compiling my application and running it. Writing compiler was end and release beta version. In the final version we must add undo and redo to the text editor. I use a file and save it periodically for the text editor. How to design undo and redo to my text editor? What is changed in the structure of persistent of file?

Enchondroma

you should have a look at #50255 – Manualmanubrium

If I make changes a.txt in our editor, then close your editor, then open it again and load a.txt, I should be able to undo changes from my previous session? – Hiltner

@lins314159: No of course, I think no app in world have this feature – Enchondroma

Pretty sure I've seen some software advertised with this. It's just a matter of writing what you're already storing in memory to a file and using some control file to indicate which undo file to use for which text file. It needs to be managed to ensure that you don't end up with heaps of no longer useful undo files lying around though. – Hiltner

Answer 1

You can model your actions as commands, that you keep in two stacks. One for undo, another for redo. You can compose your commands to create more high-level commands, like when you want to undo the actions of a macro, for example; or if you want to group individual keystrokes of a single word, or phrase, in one action.

Each action in your editor (or a redo action) generates a new undo command that goes into the undo stack (and also clears the redo stack). Each undo action generates the corresponding redo command that goes into the redo stack.

You can also, as mentioned in the comments by derekerdmann, combine both undo and redo commands into one type of command, that knows how to undo and redo its action.

Roofing

Conversely, you could make a single command that knows how to both undo and redo itself; when you undo the action, pop it off the undo stack, call the undo action, and simply move it to the redo stack. When you call redo, pop the top off the redo stack, call the redo action, and push it onto the undo stack. This saves you from having to create new objects all the time; you just reshuffle the existing ones around. – Capriole

Answer 2

There are basically two good ways to go about it:

• the "Command" design pattern

• using only OO over immutable objects, where everything is just immutable objects made of immutable objects made themselves of immutable objects (this is less common but wonderfully elegant when done correctly)

The advantage of using OO over immutable objects over the naive command or the naive undo/redo is that you don't need to think much about it: no need to "undo" the effect of an action and no need to "replay" all the commands. All you need is a pointer to a huge list of immutable objects.

Because objects are immutable all the "states" can be incredibly lightweight because you can cache/reuse most objects in any state.

"OO over immutable objects" is a pure jewel. Probably not gonna become mainstream before another 10 years that said ; )

P.S: doing OO over immutable objects also amazingly simplifies concurrent programming.

Fellowman

The "OO over immutable objects" technique sounds interesting. Can you provide any references I could check out? I'm assuming you're using OO to stand for "Object Orientation"? Thanks. – Garb

Oh, I think I found something on undo with immutable objects: #1813478 – Garb

Answer 3

If you don't want anything fancy, you can just add an UndoManager. Your Document will fire an UndoableEdit every time you add or remove text. To undo and redo each change, simply call those methods in UndoManager.

The downside of this is UndoManager adds a new edit each time the user types something in, so typing "apple" will leave you with 5 edits, undoable one at a time. For my text editor, I wrote a wrapper for edits that stores the time it was made in addition to text change and offset, as well as an UndoableEditListener that concatenates new edits to previous ones if there is only a short period of time between them (0.5 seconds works well for me).

This works well for general editting, but causes problems when a massive replace is done. If you had a document with 5000 instances of "apple" and you wanted to replace this with "orange", you'd end up with 5000 edits all storing "apple", "orange" and an offset. To lower the amount of memory used, I've treated this as a separate case to ordinary edits and am instead storing "apple", "orange" and an array of 5000 offsets. I haven't gotten around to applying this yet, but I know that it'll cause some headaches when multiple strings match the search condition (eg. case insensitive search, regex search).

Hiltner

An easier way to do this is to compare the lengths of the content before and after it has been changed, and only store an edit if it has been changed by more than say 20 characters since the last time an edit was saved. – Rivulet

Answer 4

You can do it in two ways:

• keep a list of editor states and a pointer in the list; undo moves the pointer back and restores the state there, redo moves forward instead, doing something throws away everything beyond the pointer and inserts the state as the new top element;
• do not keep states, but actions, which requires that for every action you have a counteraction to undo the effects of that action

In my (diagram) editor, there are four levels of state changes:

• action fragments: these are part of a larger action and not separately undoable or redoable (e.g. moving the mouse)
• actions: one or more action fragments that form a meaningful change which can be undone or redone, but which are not reflected in the edited document as changed on disk (e.g. selecting elements)
• document changes: one or more actions that change the edited document as it would be saved to disk (e.g. changing, adding or deleting elements)
• document saves: the present state of the document is explicitly saved to disk - at this point my editor throws away the undo history, so you can't undo past a save

Headphone

Answer 5

Wow, what a conicidence - I have literally in the last hour implemented undo/redo in my WYSIWYG text editor:

The basic idea is to either save the entire contents of the text editor in an array, or the difference between the last edit.

Update this array at significant points, i.e. every few character (check the length of the content each keypress, if its more than say 20 characters different then make a save point). Also at changes in styling (if rich text), adding images (if it allows this), pasting text, etc. You also need a pointer(just an int variable) to point at which item in the array is the current state of the editor)

Make the array have a set length. Each time you add a save point, add it to the start of the array, and move all of the other data points down by one. (the last item in the array will be forgotten once you have so many save points)

When the user presses the undo button, check to see if the current contents of the editor are the same as the latest save (if they are not, then the user has made changes since the last save point, so save the current contents of the editor (so it can be redo-ed), make the editor equal to the last save point, and make the pointer variable = 1 (2nd item in array ). If they are they same, then no changes have been made since the last save point, so you need to undo to the point before that. To do this, increment the pointer value + 1, and make the contents of the editor = the value of pointer.

To redo simply decrease the pointer value by 1 and load the contents of the array (make sure to check if you have reached the end of the array).

If the user makes edits after undoing, then move the pointed value array cell up to cell 0, and move the rest up by the same amount (you dont want to redo to other stuff once they've made different edits).

One other major catch point - make sure you only add a save point if the contents of the text editor have actually changed (otherwise you get duplicate save points and it will seem like undo is not doing anything to the user.

I can't help you with java specifics, but I'm happy to answer any other questions you have,

Nico

Rivulet

Answer 6

This is a job for the command pattern.

Causative

Answer 7

Here is a snippet that shows how SWT supports Undo/Redo operations. Take it as practical example (or use it directly, if your editor is based on SWT):

SWT Undo Redo

Esmeralda

Answer 8

Read a book Design Patterns: Elements of Reusable Object-Oriented Software. As far as I remember, there is a pretty good example.

Menendez