Implementing undo and redo for an array

Question

I got this question in a Java interview today.

I have to implement a collection which is an array and have add and delete methods which can perform only at the end of an array.

In addition to that I have to implement two more methods which is the undo and redo methods which can be performed only once.

For example:

Let x be an array containing {1,5,7,9}.

Now I add {44,66,77} in it and make it {1,5,7,9,44,66,77}.

Now when I undo it, the array should delete {44,66,77}. And if I do redo afterwards, it should be back to {1,5,7,9,44,66,77}.

And similarly for the delete.

What is the best way to achieve this in terms of complexity and memory?

My solution to the interviewer:

1. Make one string field which stores the last operation, i.e. "Add"/"Delete".
2. And a hashmap which stores key as an index of array and value as the index value of an array.

Which is a totally incorrect solution as per interviewer.

Answer 1

I would solve it like this. Basically, there will be three lists.

• A list with actual values
• Undo list with instances of Command interface

• Redo list with instances of Command interface (optional, explained below)

  public interface Command {
      void do();
      void undo();
  }
  

There will be two Command implementations: AddCommand and RemoveCommand.

• On add(), new instance of AddCommand created and added to the undo list. Then we call do() of this command, which modifies actual values and stores index of added item.
• On remove(), new instance of RemoveCommand created and added to the undo list. Then we call do() of this command, which modifies actual values and stores index and value of removed item.
• On undo() we pull last command from the undo list and execute undo() method of this command. The command pushed to the redo list. Undo methods of AddCommand and RemoveCommand revert changes back.
• On redo() we pull last command from the redo list and execute do() method again. Pulled command gets added to undo list.

Another optimization would be to remove redo list and use undo index instead. In this case when you undo(), you don't need to remove/add value from the list, but just decrease the undo index by one. Similarly, redo() will increase it by one.

Thus the final solution will have list of values, undo list and an index value.

Update:

For the simplest case, where only one undo()/redo() operation is required, solution will look even simpler. Instead of having undo list and index, it's enough to store the latest command instance. Thus you we will have a list of values and an instance of last undo command.

Answer 2

Either I misunderstand the question, or people are overthinking this. The question has quite a lot of constraints, so:

• Array for current contents
• Extra array for lastly removed items (needed to undo delete / redo add)
• One variable for previous length of array (needed to undo add / redo delete)
• One enum variable for last operation (add/delete)
• One Boolean to say if undo was just done or not

Then just update these on each different operation. No stacks or anything are needed, because multiple undo/redo is not needed.

Answer 3

One thing I will say is the reason the interviewer probably disapproved of your answer is that it's just not very elegant. Not because it's slow or takes up a lot of space.

There are basically two ways to do undo and redo, one of which is to save a copy of the entire array each time. That way is probably not desirable here (and it's very easy to implement for an array) so I'll talk about the other way.

Now, one aspect here is that a redo is actually just an undo as well. If undo is the inverse, then redo is the inverse of the inverse of undo. What this actually means is that each undo action should be able to do both. Undoing should cause the action to flip itself so the next time it undos it performs the original action.

undo and redo method which can be performed only once

Undos and redos being the same thing is more important if you have to store a long history of them (where it becomes very convenient) but it still applies here.

Doing it this way means an undo is an object with a little bit of state. Since there are possibly multiple different actions, an interface is useful here (strategy pattern, as noted in the comments):

interface UndoAction {
    public void undo();
}

For a set operation, a very simple undo object would look like this:

class SetUndoAction implements UndoAction {
    int index;
    Object oldValue;

    SetUndoAction(int index, Object oldValue) {
        this.index = index;
        this.oldValue = oldValue;
    }

    public void undo() {
        Object newValue = get(index);
        set(index, oldValue);
        oldValue = newValue;
    }
}

If you call undo on this, it performs an undo and the next time you call undo it performs a redo.

Add and remove is a little different because they are not just swapping a value. The state for an Undo that reverses an add or remove is also going to involve a method call.

For add:

• To undo, you must save the index to later call remove at that index.
• To redo, you must save the index and the value to later call add at that index.

For remove:

• To undo, you must save the index and the value to later call add at that index.
• To redo, you must save the index to later call remove at that index.

These are inverse again so we can describe a simple add or remove action similar to the set action:

class AddRemoveUndoAction implements UndoAction {
    int index;
    Object theValue;
    boolean wasAdd;

    AddRemoveUndoAction(int index, Object theValue, boolean wasAdd) {
        this.index = index;
        this.theValue = theValue;
        this.wasAdd = wasAdd;
    }

    public void undo() {
        if(wasAdd) {
            remove(index);
        } else {
            add(index, theValue);
        }

        wasAdd = !wasAdd;
    }
}

add creates a new AddRemoveUndoAction(..., ..., true) and remove creates a new AddRemoveUndoAction(..., ..., false).

Now, from the perspective of the class that has the array, it just needs to create and store these objects appropriately.

If you have a history of multiple undos you'd have some type of data structure (probably a stack or queue) to store them in though there's some special functionality you need:

• A maximum number of elements and should begin to discard old edits each time a new one is pushed.
• A 'current element pointer' that can be iterated between next and previous elements when undos and redos are performed. (This could also be achieved by having two stacks, one for undo and one for redo, and you'd pop from one and push to the other.)
• If the 'current element pointer' is in the middle of the stack (undos have been performed and there are redos now), and a new undo is pushed, the redos at the head should be deleted.

You could use a java.util.Stack and manage those things from the outside (via a ListIterator) but I found that's a headache and it's much nicer to write a separate data structure specifically just for this.

For undo and redo that only store a single item, it's a lot easier, you can just have two fields.

When undo is called on the array holding class:

• It should check that there is an undo object.
• It should call undo on the undo object.
• It should move the undo object to the redo field.

When redo is called on the array holding class:

• It should check that there is a redo object.
• It should call undo on the redo object.
• It should move the redo object to the undo field.

Methods called on the array holding class that can be undone should add a new UndoAction object to the undo field and set the redo field to null.

This design is mostly advantageous for a multiple undo situation because each layer of the abstraction is only responsible for itself:

• The undo objects that are self-aware of whether they should undo or redo. (The command pattern or an abstract class can be used to make writing these a little simpler.)
• The undo manager, an iterator that manages a point in time in a history. Moving backwards in time causes undos and moving forwards in time causes redos.
• The undo clients that are aware of their own data and how it should be altered.

Answer 4

I have been doing some research, and as I have suggested, you can either register the number of "things" going into array - and then store that somewhere. So when you do undo - it removes last objects inserted.

So think of it in this way:

The container is holding the number of items entered into the array = 1,2,4,2

Array = {[x][x,x][x,x,x,x][x,x]}

If you want to remove the last action, you take from container 2 and remove the last entry from the array so you are left with:

Container holding number of items entered into array = 1,2,4

Array = {[x][x,x][x,x,x,x]}

And so on and so forth.

Also, you can have a look at this interesting pattern that provides the ability to restore an object to its previous state.

Answer 5

My solution is to use a Map of ArrayLists to hold historical values of the Array. Here is the code:

public class UndoRedoArray {
    private List<Integer> currentValues;
    private int version = 0;
    private int highestVersion = 0;
    private Map<Integer, List<Integer>> history = new HashMap<Integer,List<Integer>>();

    public Integer[] getValues() {
        return (Integer[]) getCurrentValues().toArray();
    }

    private List<Integer> getCurrentValues() {
        if (currentValues == null) {
            currentValues = new ArrayList<Integer>();
        }
        return currentValues;
    }

    private void add(Integer[] newValues) {
        incrementHistory();
        getCurrentValues().addAll(Arrays.asList(newValues));
    }

    private void incrementHistory() {
        if (history.get(version) != null)  {
            throw new IllegalArgumentException("Cannot change history");
        }
        history.put(version,getCurrentValues());
        if (version > 2) {
            history.remove(version - 2);
        }
        version++;
        if (version > highestVersion) {
            highestVersion = version;
        }
    }

    private void delete(Integer[] endValues) {
        incrementHistory();
        int currentLength = getCurrentValues().size();
        int i = endValues.length-1;
        for (int deleteIndex = currentLength - 1; deleteIndex > currentLength - endValues.length; deleteIndex--) {
            if (!endValues[i].equals(getCurrentValues().get(deleteIndex))) {
                throw new IllegalArgumentException("Cannot delete element(" + endValues[i] + ") that isn't there");                
            }
            getCurrentValues().remove(deleteIndex);
        }
    }

    public void undo() {
       version--;
       if (history.get(version) == null) {
           throw new RuntimeException("Undo operation only supports 2 undos");
       }
       this.currentValues = history.get(version);
    }

    public void redo() {
       version++;
       if (history.get(version) == null) {
           throw new RuntimeException("Redo operation only supported after undo");
       }
       this.currentValues = history.get(version);
    }

}

Answer 6

If you want to use minimum memory:

1. Store the main array. It will contain all entries in your array.
2. Store a map (a bitmap will be enough to implement single undo/redo iteration. Use a more complex type of map to implement multilevel undo/redo) to flag the element's status - active/new/delete.

Answer 7

One thing I can think of is having an array of arrays. Something like this:

Actual Data = []
Bitmap History = [[]]
End Index = 0

Add [4, 5]

Actual Data = [[4, 5]]
Bitmap History = [ [00], [11] ]
End Index= 1

Add [6, 7]

Actual Data = [[4, 5], [6, 7]]
Bitmap History = [ [0000], [1100], [1111] ]
End Index = 2

Add [8, 9]

Actual Data = [[4, 5], [6, 7], [8, 9]]
Bitmap History = [ [000000], [110000], [111100], [111111] ]
End Index = 3

Add [1,2] at index 0

Actual Data = [[1,2], [4,5], [6,7], [8,9]]
Bitmap History = [ [00000000], [00110000], [00111100], [00111111], [11111111] ]
End Index = 4

Delete 9

Actual Data = [[1,2], [4,5], [6,7], [8,9]]
Bitmap History = [ [00000000], [00110000], [00111100], [00111111], [11111111], [11111110] ]

Delete 8

Actual Data = [[1,2], [4,5], [6,7], [8,9]]
Bitmap History = [ [00000000], [00110000], [00111100], [00111111], [11111111], [11111110], [11111100] ]

Add 10 at the end

Actual Data = [[1,2], [4,5], [6,7], [8,9], [10]]
Bitmap History = [ [000000000], [001100000], [001111000], [001111110], [111111110], [111111100], [111111000], [111111001] ]
End Index = 7

Undo three times should → End Index = 4 → use bitmap history [111111110] to flatten

Flattened Data = [1,2,4,5,6,7,8,9]

Have a method called flatten() that uses the data in the bitmap history to get the contents of the array and create a single array from it.

Now when you want to undo, all you do is decrement the End Index value. And to redo, just increment the End Index value. The flatten method will take care of showing the right elements from the Actual Data array.

The delete operation inserts a new entry into the bitmap history with the flag for that number turned off.

Answer 8

I will implement it like this:

Operations performed can be maintained in an array/vector as strings. On each operation on an array, information regarding operation can be stored. On each undo/redo on the array, a value will be fetched from the operations array and if undo then counter operation and in case of redo the same operation will be performed and after performing operation value or pointer in operation array will be updated.

Let’s say you have an array arr and operation array say optArr and ptr that will point to last element in optArr.

Add 5 to array

arr{5} and optArr{"Add 5"} and ptr = 0

Add 9 to array

arr{5, 9} and optArr{"Add 5", "Add 9"} and ptr = 1

Add 7 to array

arr{5, 9, 7} and optArr{"Add 5", "Add 9", "Add 7" } and ptr = 2

Delete 9 from array

arr{5, 7} and optArr{"Add 5", "Add 9", "Add 7", "Delete 9" } and ptr = 3

For the undo command

value = optArr[ptr--]

value is "Delete 9" now counter operation ("Add 9") of this will be performed.

For the redo command

value = optArr[++ptr]

value is "Delete 9" will be performed.

Answer 9

Use:

// Create three lists and a string variable that stores the last operation name.
List<Integer> sizeIndex = new ArrayList<Integer>();
List<Integer> finalArray = new ArrayList<Integer>();
List<Integer> lastDelete = new ArrayList<Integer>();
String lastOperation;

// Add the first size of the finalArray.
sizeIndex.add(finalArray.size());

public void add(List<Integer> someArray){
    lastOperation = "add";
    finalArray.addAll(someArray);
    sizeIndex.add(finalArray.size());
}

public void delete(){
    lastOperation = "delete";
    lastDelete = finalArray.subList(sizeIndex.size()-1, sizeIndex.size());
    finalArray = finalArray.subList(0, sizeIndex.size()-1);
    sizeIndex.remove(sizeIndex.size() - 1);
}

public undo(){
    if("add".equals(lastOperation))
        delete();
    else
        add(lastDelete);
}

public redo(){
    if("add".equals(lastOperation))
        add(lastDelete);
    else
        delete();
}

Logic:

When a list is added to the end, the new list is added as the last element in the List. So the last list can be extracted from the index sizeBeforeAdding the list and the sizeAfterAddding. So keep a track on the size; i stores the size on updating on sizeIndex.

Operations

add(listToBeAppended); // Add the list to the current list.

delete(); // Will delete the last list added.

undo(); // Will redo the last operation did i.e., delete if added and add if deleted.

redo(); // Do the last operation again, i.e., if added and then deleted then redo will add again.

Answer 10

I'm not a Java guy, but I think this solution could be translated to Java easily:

First make an analysis of the problem: We need a class designed to perform a set of operations, and this operations could be performed only once, and undone and redone one time each. So the process is:

1. Perform an action (add or delete).
2. (Optionally) undo the action.
3. (Optionally) redo the action.

So it's a system designed with an action/s to be done and undone, and is acceptable to think that the do/redo commands will be performed frequently and design the system in that way.

With that in mind, I suggest to implement the add/delete actions, just not modifying the underlying data in any way, and just provide different proxies to the data depending if the action was undone or redone.