One aspect of the
List interface that has always bugged me is the definition of the
ListIterator interface. In my view, its API is bloated and made overly complex by the fact that it can move in two directions at once, which also makes
testing quite a chore.
How many people have actually used a
ListIterator to do this? I know that in 12 years of writing
Java I haven't; although I've certainly had need of an iterator that can move in
either direction, even from a specific start point.
Assuming that there is a need for such a beast, it seems to me that there is something missing between a standard
Iterator and a
ListIterator - a
directional iterator.
To understand why this is so, one needs to get back to basics: What is an
Iterator?
The Java API simply states that it is an "iterator over a collection", which isn't very helpful. The docs for
Enumeration, which
Iterator succeeded, say that it "generates a series of elements, one at a time", which isn't much better.
What both classes signally fail to mention is that they have an
implied direction - let's call it "forwards" - encapsulated by the
word "next", which is almost always defined, and also consistent for multiple invocations of
iterator() on the same
Collection, providing it hasn't been modified.
Why should it be restricted to "forwards"?
If we can agree that an
Iterator is a mechanism for traversing the elements of a collection in a predictable sequence - even if, as in the case of a
HashSet, that sequence isn't very obvious - then surely it should be possible to reverse it?
ListIterator actually entrenches this by providing a complete set of duplicate methods that have the word "previous" as opposed to "next" in them; but why should this be restricted simply to Lists? Or indeed simply to 'forwards' and 'backwards'? (see below). At the very least, wouldn't it be useful to be able to return the elements of any 'ordered' collection (eg, a
SortedSet) in reverse sequence?
Unfortunately, instead of defining this in the interface, it's been left up to subclasses (eg
TreeSet) to define methods to do it (
two in its case), which leads to bloated and uncoordinated APIs.
Proposal
Add four new interfaces:
A Cursor that extends Iterator, and defines an explicit direction (see below). This interface would not require any extra methods.A Direction that defines what "next" means for a Cursor.A Traverser that extends Cursor, whose Direction can be changed. This interface would have extra methods - at the very least, a getter and setter for its Direction.A Table that looks like a List (ie, it is primarily an indexed structure), but sits above it in the hierarchy. Table's listIterator() methods would return Cursors, rather than ListIterators.
In addition:
Change ListIterator to extend Cursor, rather than Iterator.
Direction should probably be nested - ie,
Cursor.Direction - since its business is solely to define a direction for a
Cursor. In addition,
Cursor should probably define an
enum of
Directions for at least 3 dimensions (see the 'ADDITIONAL STUFF' section at the end for more details).
.
Now, for anyone whose eyes are glazing over, or who feels that this is 'way over the top' for a simple
Collection, please remember that these additions make absolutely no difference to any
existing collection classes; they are simply there to make iterators and "indexable" collections more generic, and to provide the capability to iterate in whatever way makes sense.
Developers who don't fancy implementing their own
List (especially a
linked list) because of that nasty
ListIterator interface, can simply extend
Table and implement the much simpler
Cursor or
Traverser. In addition,
Table becomes a launch point for all kinds of 'matrix' or 'cubic' collections - one that immediately comes to mind for such treatment would be
ResultSet - offering a whole new vista of 'columnar' or 'planar' iterators.
Also, since "next" now becomes a function of
Direction, I can imagine an API of "things I'd like to do with
next" developing around it; indeed, it becomes the defining 'style' of the Iterator. Who, for example, hasn't wished that
Iterator had
peek() or
skip(int) methods?
Furthermore, one could also imagine a generalization of an
Iterator that returns a
Position that encapsulates not only an element value, but also its position relative to its neighbours
without exposing the mechanics of the collection. Such an object wouldn't need to provide any public API beyond
getValue(), but could be passed to
Cursor (or a subclass) as a start point for iteration.
Who hasn't wished they could do that with a
LinkedList before now?
I suspect that we're getting into the realms of Collection wrappers here, which was not my intent; but I feel in my bones that making
Direction an explicit attribute of an
Iterator is a first step down the road - and probably one that should have been there from the start.
ADDITIONAL STUFF
Direction names
The names for an
enum of
Directions as described above are important, since they work in pairs and should be easy to visualise. My suggestions would be:
with the last pair being used for the
z-axis of 'cubic' structures - FORWARDS meaning "towards the front" and BACKWARDS meaning "towards the back" - although I'd have no great problem with the last pair being used for linear collections as well.
Specifically, for each pair, the first name indicates "towards index 0" and the second "away from index 0" for the axis in question.
And if anyone feels like coming up with names for "hypercube" directions, please feel free
- however, I suspect that they're probably specialized enough to warrant an
enum of their own.
listIterator(int)
While it's a bit of a kludge, this method is perfectly capable of returning a
Cursor over a
linear Table for virtually any situation:
Instead of supplying it simply with an index to start from, use the fact that
ints are signed to also supply a
Direction - ie, a negative value
n indicates that the
Cursor should work
backwards from index
-n. I'd suggest that this should probably be
exclusive (ie, the first call to
next() should return the element at index
-n - 1), but I leave that up to others to decide.
Alternatively, don't try to reuse the method at all, and simply put
Table in a separate hierarchy. I think, however, that there are sufficient similarities between
Table and
List to warrant at least trying to group them together.