Wednesday, May 14, 2008

How to implement undo/redo functionality

After searching the web, I finally managed to implement an undo/redo class for Saya. I never imagined that with simple use-cases, I'd be able to straighten my thoughts and get rid of all the complications in thinking up a good algorithm.

So here goes.




Use case: Undo History
======================

1. Beginning
============

curstate ----> 0. EOF


2. Do "something"
=================
BEFORE:

curstate ----> 0. EOF

AFTER:
0. RECENTLY SAVED STATE, transition: "something"
curstate ----> 1. EOF

ACTIONS:
If current state is EOF, save state in current slot with the transition to be done;
increment state pointer.


3. Do "somethingElse"
=====================

BEFORE:

0. SAVED STATE, transition: "something"
curstate ----> 1. EOF

AFTER:

0. SAVED STATE, transition: "something"
1. RECENTLY SAVED STATE, transition: "somethingelse"
curstate ----> 2. EOF

ACTIONS:
If current state is EOF, save state in current slot with the transition to be done;
increment state pointer.


3. Undo
=======

BEFORE:

0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "somethingelse"
curstate ----> 2. EOF

AFTER:

0. SAVED STATE, transition: "something"
curstate ----> 1. SAVED STATE, transition: "somethingelse"
2. RECENTLY SAVED STATE, transition: ""

ACTIONS:
If current state is EOF, Save state in current slot with an empty transition name;
decrement state pointer and restore state.


4. Redo
=======

BEFORE:

0. SAVED STATE, transition: "something"
curstate ----> 1. SAVED STATE, transition: "somethingelse"
2. SAVED STATE, transition: ""

AFTER:
0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "somethingelse"
curstate ----> 2. SAVED STATE, transition: ""

ACTIONS:
If next state not EOF, Increment state pointer and restore state.

5. Undo
=======

BEFORE:

0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "somethingelse"
curstate ----> 2. SAVED STATE, transition: ""

AFTER:
0. SAVED STATE, transition: "something"
curstate ----> 1. SAVED STATE, transition: "somethingelse"
2. SAVED STATE, transition: ""

ACTIONS:
If current state not EOF, just decrement state pointer and restore state.

6. Do aNewThing
===============

BEFORE:

0. SAVED STATE, transition: "something"
curstate ----> 1. SAVED STATE, transition: "somethingelse"
2. SAVED STATE, transition: ""

INTERMEDIATE STEP:

0. SAVED STATE, transition: "something"
curstate ----> 1. SAVED STATE, transition: "somethingelse"
2. EOF

AFTER:

0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "anewthing" (transition was renamed)
curstate ----> 2. EOF

ACTIONS:

If next state not EOF, delete all states until next state is EOF.
Rename current slot's transition; increment the pointer.

--------- Alternative case: -----------

BEFORE:
0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "somethingelse"
curstate ----> 2. SAVED STATE, transition: ""

AFTER:

0. SAVED STATE, transition: "something"
1. SAVED STATE, transition: "somethingelse"
2. SAVED STATE, transition: "aNewthing"
curstate ----> 3. EOF

ACTIONS:
If next state is EOF, rename current slot's transition; increment the pointer.

Pseudocode:
============

Function Do() {
1. while(!IsNextEof()) delete the topmost state.
2. if(IsEof()) Save state in current slot with the transition to be done;
else
just rename current slot's transition.
3. ++curpos;
}

function Undo() {
1. if(IsEof()) Save state in current slot with an empty transition name;
2. if(curpos) { curpos--; restore state; }
}

function Redo() {
1. if(!IsNextEof()) { curpos++; restore state; }
}

function IsNextEof() {
return (curpos+1 >= undostack.size(); )
// Note that we use a double-ended queue instead of just a stack to be able to delete
// old states in case memory usage exceeds a given limit.
}

function IsEof() {
return (curpos >= undostack.size());
}

No comments: