Bookmark Topic Watch Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Report post to moderator
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.
     
    Honk if you love justice! And honk twice for tiny ads!
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com
      Bookmark Topic Watch Topic
    • New Topic