The stack interface is very simple, as reflected in the small number of test cases. Still, it is important not to become complacent and presume that due to the simplicity, no testing is required.

public void testPushAndPop() {
        Stack stack = createStack();

        stack.push(VALUE_B);
        stack.push(VALUE_A);
        stack.push(VALUE_C);

        assertEquals(3, stack.size());
        assertFalse(stack.isEmpty());

        assertSame(VALUE_C, stack.pop());
        assertEquals(2, stack.size());
        assertFalse(stack.isEmpty());

        assertSame(VALUE_A, stack.pop());
        assertEquals(1, stack.size());
        assertFalse(stack.isEmpty());

        assertSame(VALUE_B, stack.pop());
        assertEquals(0, stack.size());
        assertTrue(stack.isEmpty());
    }

You also need to ensure that any attempt to call pop() on an empty list results in an appropriate exception being thrown:

public void testCantPopFromAnEmptyStack() {
        Stack stack = createStack();

        assertEquals(0, stack.size());
        assertTrue(stack.isEmpty());

        try {
            stack.pop();
            fail();
        } catch (EmptyStackException e) {
            // expected
        }
    }

This test pushes the three values B, A, and C onto the stack and then pops them off one at a time, ensuring that they are removed in the correct order: C; then A; and finally B.

After first ensuring the stack is empty, you attempt to pop a value. If the call to pop() is successful, you fail the test because this is incorrect behavior—you shouldn't be able to pop from an empty stack. If instead an EmptyStackException is thrown, the stack is working as expected.

public void testPeek() {
        Stack stack = createStack();

        stack.push(VALUE_C);
        stack.push(VALUE_A);
        assertEquals(2, stack.size());

        assertSame(VALUE_A, stack.peek());
        assertEquals(2, stack.size());
    }

To test peek, you push two values—C and then A—and ensure that not only does peek() return the last value pushed—in this case, an A—but also that nothing has been removed from the stack as a consequence:

public void testCantPeekIntoAnEmptyStack() {
        Stack stack = createStack();

        assertEquals(0, stack.size());
        assertTrue(stack.isEmpty());

        try {
            stack.peek();
            fail();

} catch (EmptyStackException e) {
            // expected
        }
    }

Last but not least, you confirm that clear() performs as expected and removes all elements from the stack:

public void testClear() {
        Stack stack = createStack();

        stack.push(VALUE_A);
        stack.push(VALUE_B);
        stack.push(VALUE_C);

        assertFalse(stack.isEmpty());
        assertEquals(3, stack.size());

        stack.clear();

        assertTrue(stack.isEmpty());
        assertEquals(0, stack.size());

        try {
            stack.pop();
            fail();
        } catch (EmptyStackException e) {
            // expected
        }
    }
}

After initially filling the stack with some values, the stack is then cleared, after which the size is checked and an attempt is made to pop a value, which should fail: Popping a value from an empty stack should throw an EmptyStackException.

The only thing this class needs to hold is a list to use as the underlying data structure. A linked list has been used because it is very efficient at adding and removing items from the ends—something a stack does. Having said this, you could easily substitute an array list without much worry. The main thing to understand is that rather than extend a particular list implementation, you've instead used composition to "wrap" a list. This prevents the list methods from "leaking" out, which may cause users of your ListStack class to believe that they can use the methods on the list interface as well as those defined for the stack.

As you can see, push() just adds the value to the underlying list, while enqueue() simply delegates to push().

Notice also that you haven't checked for a null value here because you can delegate that responsibility to the underlying list implementation.

public Object pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return _list.delete(list.size() − 1);
    }

    public Object dequeue() throws EmptyQueueException {
        try {
            return pop();
        } catch (EmptyStackException e) {
            throw new EmptyQueueException();
        }
    }

The performance of push() and pop() as implemented here relies entirely on the performance of the underlying list's add() and delete() methods, respectively.

The peek() method allows access to the value at the top of the stack without removing it:

public Object peek() throws EmptyStackException {
        Object result = pop();
        push(result);
        return result;
    }

To complete the class, you can delegate the remaining methods to the underlying list, as the expected behavior is identical:

public void clear() {
        _list.clear();
    }

    public int size() {
        return _list.size();

}

    public boolean isEmpty() {
        return _list.isEmpty();
    }

This time you are being a little more cautious. Without the defensive check, the list's delete() method might well throw an IndexOutOfBoundsException—not what the caller would have expected. Instead, you explicitly check the size of the stack and throw EmptyStackException as specified in the Stack interface, before removing and returning the last element in the underlying list.

Also notice that even though dequeue() can delegate most of its behavior to pop(), it still needs to convert an EmptyStackException into an EmptyQueueException.

Then, using the peek() method, you call pop() to retrieve the next item, record its value, and push it back on again before returning the value to the caller. In this way, you have effectively returned the value at the top of the stack without actually removing it.

You should now be able to compile and run the tests against the completed, list-based stack. As satisfying as this no doubt is, once all your tests are passing, you'll probably want to use your stack for something a bit more constructive.

The tests first ensure that an empty list starts off with nothing to undo. A single value is then inserted in or added to the list. Because the test class itself extends AbstractListTestCase, you can be confident that the actual behavior of inserting a value into the list works. Therefore, all you need to ensure next is that calling undo removes the inserted value.

In both the undo and delete cases, the tests are relatively simple, as you need not concern yourself with the behavior of the actual delete() method—this has been tested by the methods in the superclass. The list is first initialized with some predefined values. Then, delete a value and, after calling undo(), ensure that it has reappeared in the expected location.

The final test starts off with an empty list and variously adds and removes values, invoking undo() along the way. In particular, you will see that the very first add is never undone until right at the end of the test, even though two other actions are undone in the meantime. This proves that the stack-based undo is working as expected.

Tests in place, it's time to actually implement the UndoableList class, as shown in the following Try It Out.

package com.wrox.algorithms.stacks;

import com.wrox.algorithms.iteration.Iterator;
import com.wrox.algorithms.lists.List;

public class UndoableList implements List {
    private final Stack _undoStack = new ListStack();
    private final List _list;

    public UndoableList(List list) {
        assert list != null : "list can't be null";

_list = list;
    }

    private static interface UndoAction {
        public void execute();
    }

    ...
}

To get going, you need to start capturing state information each time a value is inserted in or added to the list by intercepting calls to insert():

private final class UndoInsertAction implements Action {
        private final int _index;

        public UndoInsertAction(int index) {
            _index = index;
        }

        public void execute() {
            _list.delete(_index);
        }
    }

    public void insert(int index, Object value) throws IndexOutOfBoundsException {
        _list.insert(index, value);
        _undoStack.push(new UndoDeleteAction(index));
    }

    public void add(Object value) {
        insert(size(), value);
    }

Next you need to intercept calls to delete() so that you can restore the deleted value at some later stage:

private final class UndoDeleteAction implements Action {
        private final int _index;
        private final Object _value;

        public UndoDeleteAction(int index, Object value) {
            _index = index;
            _value = value;
        }

        public void execute() {
            _list.insert(_index, _value);
        }
    }

    public Object delete(int index) throws IndexOutOfBoundsException {
        Object value = _list.delete(index);
        _undoStack.push(new UndoInsertAction(index, value));
        return value;

}

    public boolean delete(Object value) {
        int index = indexOf(value);
        if (index == −1) {
            return false;
        }

        delete(index);
        return true;
    }

The method first calls indexOf() to determine the position of the value within the list. Then, if the value isn't found, false is returned; otherwise, the delete() method that takes an index is called, which will record the necessary state to perform an undo operation later. Calling set() also modifies the state of the list, so you need a way to restore its effect as well:

private final class UndoSetAction implements Action {
        private final int _index;
        private final Object _value;

        public UndoSetAction(int index, Object value) {
            _index = index;
            _value = value;
        }

        public void execute() {
            _list.set(_index, _value);
        }
    }

    public Object set(int index, Object value) throws IndexOutOfBoundsException {
        Object originalValue = _list.set(index, value);
        _undoStack.push(new UndoSetAction(index, originalValue));
        return originalValue;
    }

Now that you have defined the necessary infrastructure to record the undo state, you can write the code for the undo() method:

public void undo() throws EmptyStackException {
        ((Action) _undoStack.pop()).execute();
    }

As a convenience, you might also enable callers to determine whether there are any more actions to undo. This would be handy, for example, if you wanted to enable/disable an undo button in a user interface:

public boolean canUndo() {
        return !_undoStack.isEmpty();
    }

To determine whether there are any more actions to undo, you can just query the undo stack: If it's empty, then there is no more to undo and vice-versa.

Even though clear() modifies the list, it was decided that for this example, no undo state would be recorded and the list would be reset:

public void clear() {
        _list.clear();
        _undoStack.clear();
    }

Besides clearing the underlying list, the undo stack is also cleared, thereby resetting the entire structure.

Completing the interface requirements for this class is somewhat of a formality:

public Object get(int index) throws IndexOutOfBoundsException {
        return _list.get(index);
    }

    public int indexOf(Object value) {
        return _list.indexOf(value);
    }

    public Iterator iterator() {
        return _list.iterator();
    }

    public boolean contains(Object value) {
        return _list.contains(value);
    }

    public int size() {
        return _list.size();
    }

    public boolean isEmpty() {
        return _list.isEmpty();
    }

    public String toString() {
        return _list.toString();
    }

    public boolean equals(Object object) {
        return _list.equals(object);
    }

None of the remaining methods make any modifications to the state of the list, so it is sufficient that they simply delegate to the underlying instance.

Aside from the underlying list, the class also holds the undo stack, which will hold instances of the inner interface UndoAction (also shown), which defines a single method, execute(), that will eventually be called to perform most of the work involved in implementing the undo functionality.

The action UndoDeleteAction class implements the UndoAction interface and, of course, more important, the execute() method. To undo an insert is to delete, so when execute() is called, it uses the recorded position to delete a value from the underlying list.

The insert() method calls insert() on the underlying list and then pushes an undo action. The add() method can then call insert(). You could have created a special action to delete from the end of the list, but calling insert(), passing in the position, has exactly the same effect and requires much less code.

The UndoDeleteAction class implements the UndoAction interface and holds the recorded position and value for later use. To undo a deletion is to insert, so when execute() is called, the action reinserts the value into the underlying list.

The first delete() calls delete() on the underlying list and retrieves the deleted value before pushing an insert action and returning to the caller. Deleting by value is a little trickier. Because you have no way of knowing where in the list the value was deleted, you must re-implement delete by value based on delete by position—not a particularly efficient solution, but your only option.

A call to set() on the underlying list always returns the original value contained at the specified position, so in this case, the UndoSetAction's execute() method stores the old value, together with the position in order to perform the undo. Notice again that, as was the case for the previous two undo actions, the execute() method makes calls on the underlying list in order to prevent the undo from pushing additional undo action onto the stack.

As you can see, there's not a lot of code to actually write for the actual undo() method. All the hard work has already been done by each of the UndoAction classes, so making it all come together is a simple matter of popping the next action (if any) off the stack and calling execute().

And there you have it. You now have a fully tested and implemented list that supports undo functionality.