Sunday, July 24, 2005

ReverseList for Java

One of my Java pastimes is writing trivial utility classes. Part of my interest is stylistic: I hate seeing blocky, chunky code that could be replaced by elegant, simple code. Illustrating my point, I needed a reversed list which presented an underlying list in reverse order. So I created a simple utility class, ReverseList, which fits the bill:

class ReverseList<E>
        extends AbstractList<E> {
    private final List<E> list;

    public ReverseList(final List<E> list) {
        this.list = list;
    }

    public void add(final int index, final E element) {
        list.add(reverseIndex(index) + 1, element);
    }

    public E remove(final int index) {
        return list.remove(reverseIndex(index));
    }

    public E get(final int index) {
        return list.get(reverseIndex(index));
    }

    public E set(final int index, final E element) {
        return list.set(reverseIndex(index), element);
    }

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

    private int reverseIndex(final int index) {
        return size() - index - 1;
    }
}

The only trick to it is to note that add(int, Object) requires one bump the reversed index. I only discovered this during unit testing and was puzzled for a while. Then I realized that add is conceptually akin to inserting in that it shifts elements to the right: reversing the list shifts to the left, hence, requires that indices be off by one.

UPDATE: An even better explanation for the index in add: The indices are akin to point in Emacs, that is, they note the spot between elements and are just to the left of a given element. If you think of elements as boxes in a row, the point is the gap to the left of a box between it and the box next to it.

Reversing a list is like reflecting it in a mirror: traversing it from beginning to end becomes end to beginning when reversing. Likewise, point is reflected from being just to the left of an element to just to the right of an element. To represent this change in the original, underlying list is to increase the index of point by one.

UPDATE: Andrew McCormick pointed out that "reverse list" also has another name: Stack.

2 comments:

Anonymous said...

Interesting article but I was wondering why you didn't create and itertor that walks the list in reverse which may had been a little easier?

Paul

Brian Oxley said...

Hey, Paul!

Well, I do have a ReverseIterator that does just that, but I have an interface which returns a List so I needed to match that contract, hence ReverseList.

The ReverseIterator (logically) takes a ListIterator as its input. I write about it here:

http://binkley.blogspot.com/2003/09/iterators.html