Iterating over a two level structure using nested iterators

Question

I have the following two level XML structure. A list of boxes, each containing a list of drawers.

<Boxes>
    <Box id="0">
        <Drawers>
            <Drawer id="0"/>
            <Drawer id="1"/>
            ...
        </Drawers>
    </Box>
    <Box id="1">
...
    </Box>
</Boxes>

I'm parsing it using StAX and exposed the structure through two Iterators:

1. BoxIterator implements Iterator<Box>, Iterable<Box>
2. Box implements Iterable<Drawer>
3. DrawerIterator implements Iterator<Drawer>

I can then do the following:

BoxIterator boxList;
for (Box box : boxList) {
  for (Drawer drawer : box) {
    drawer.getId()
  }
}

Under the hood of those Iterators I'm using StAX and both of them are accessing the same underlying XMLStreamReader. If I call BoxIterator.next() it will influence the result that will be returned on subsequent calls to DrawerIterator.next() because the cursor will have moved to the next box.

Does this break the contract of Iterator? Is there a better way to iterate over a two level structure using StAX?

Answer 1

Does this break the contract of Iterator?

No.

The Java Iterator imposes two "contracts". The first contract is the Java interface itself, which declares 3 methods: hasNext(), next(), and remove(). Any class which implements this Iterator interface must define those methods.

The second contract defines the behaviour of the Iterator:

hasNext() [...] returns true if the iteration has more elements. [...] next() returns the next element in the iteration [and] throws NoSuchElementException if the iteration has no more elements.

That is the entire contract.

It is true that if the underlying XMLStreamReader is advanced, it can mess up your BoxIterator and/or DrawerIterator. Alternately, calling BoxIterator.next() and/or DrawerIterator.next() at the wrong points could mess up the iteration. However, used correctly, such as in your example code above, it works properly and greatly simplifies the code. You just need to document the proper usage of the iterators.

As a concrete example, the Scanner class implements Iterator<String>, and yet has many, many other methods that advance the underlying stream. If there existed a stronger contract imposed by the Iterator class, then the Scanner class itself would be violating it.

---

As Ivan points out in the comments, boxList should not be of type class BoxIterator implements Iterator<Box>, Iterable<Box>. You really should have:

class BoxList implements Iterable<Box> { ... }
class BoxIterator implements Iterator<Box> { ... }

BoxList boxList = ...;
for (Box box : boxList) {
  for (Drawer drawer : box) {
    drawer.getId()
  }
}

While having one class implement both Iterable and Iterator is not technically wrong for your use case, it can cause confusion.

Consider this code in another context:

List<Box> boxList = Arrays.asList(box1, box2, box3, box4);
for(Box box : boxList) {
    // Do something
}
for(Box box : boxList) {
    // Do some more stuff
}

Here, boxList.iterator() is called twice, to create two separate Iterator<Box> instances, for iterating the list of boxes twice. Because the boxList can be iterated over multiple times, each iteration requires a new iterator instance.

In your code:

BoxIterator boxList = new BoxIterator(xml_stream);
for (Box box : boxList) {
  for (Drawer drawer : box) {
    drawer.getId();
  }
}

because you are iterating over a stream, you can't (without rewinding the stream, or storing the extracted objects) iterate over the same nodes a second time. A second class/object is not needed; the same object can act as both Iterable and Iterator ... which saves you one class/object.

Having said that, premature optimization is the root of all evil. The savings of one class/object is not worth the possible confusion; you should split BoxIterator into a BoxList implements Iterable<Box>, and BoxIterator implements Iterator<Box>.

Answer 2

It has the potential to break the contract for the reason that hasNext() could return true, but next() could throw a NoSuchElementException.

The contract of hasNext() is:

Returns true if the iteration has more elements. (In other words, returns true if next() would return an element rather than throwing an exception.)

But it could happen that between calling hasNext() and next(), another iterator could have moved the stream position such that there are no more elements.

However, in the way you've used it (the nested loop), you won't encounter the breakage.

If you were to pass an iterator to another process, then you may encounter this breakage.

Answer 3

The only design issue with your piece of code is that BoxIterator implements both Iterator and Iterable. Normally, Iterable object returns new stateful Iterator every time iterator() method is called. Because of that, there should be no interference between two iterators, but you'll need a state object to correctly implement exit from inner loop (probably, you already have that, but I must mention it for clarity).

1. State object will act like proxy for parser with two methods popEvent and peekEvent. On peek iterators will check the last event, but will not consume it. on pop they'll consume last event.
2. BoxIterable#iterator() will consume StartElement(Boxes) and return iterator after that.
3. BoxIterator#hasNext() will peek events and pop them until StartElement or EndElement will be received. It will then return true only if StartElement(Box) was received.
4. BoxIterator#next() will peek-and-pop Attribute events until StartElement or EndElement received to initialize Box object.
5. Box#iterator() will consume StartElement(Drawers) event and then return DrawerIterator.
6. DrawerIterator#hasNext() will peek-and-pop until StartElement or EndElement received. It will then return true only if it was StartElement(Drawer)
7. DrawerIterator#next() will consume Attribute events until EndElement(Drawer) received.

Your user code will remain almost unmodified:

BoxIterable boxList;
/*
 * boxList must be an BoxIterable, which on call to iterator() returns 
 * new BoxIterator initialized with current state of STaX parser
 */
for (Box box : boxList) { 
  /* 
   * on following line new iterator is created and initialized 
   * with current state of parser 
   */
  for (Drawer drawer : box) { 
    drawer.getId()
  }
}