Creating a recursive iterator

Question

I am trying to write an iterator for a hierarchy of classes that collectively make up the components of a song. All classes are implementations of the abstract MusicComponent base class and inherit a getChildren() function. The abstract MusicTime subclass knows the actual note/chord to play, and all its implementations (e.g. quaver, crotchet) return null for getChildren().

The other components are MusicComponent which holds a collection of MusicTimes e.g. a bar at a time, and Section which holds the MusicComponents. Song holds the Sections that make up the song e.g. verses, choruses, sections with different tempos/time signatures.

What I need is an iterator that will iterate through all Sections in a Song, then all MusicComponents in the Section and only when it finds a MusicTime descendant, play the note for the length of time based on its note type, and the time signature and tempo of its containing Section.

Sorry if too much info, but was the only way I could explain what I'm trying to do. So do I need to handle this with a stack, recording which MusicComponents I've visted or is there a way to do this just using recursion?

Answer 1

You can write an iterator which "concatenates" the iterators of its children, even lazily. Calling next() on a Song's iterator would then drill down through the Section and MusicComponent iterators and finally deliver the next MusicTime.

Guava makes this easy. Make MusicComponent an Iterable<MusicTime> and implement iterator() as:

@Override
public Iterator<MusicTime> iterator() {
    return Iterables.concat(getChildren()).iterator();
}

Since all children are MusicComponents and thus implement Iterable<MusicTime> themselves, Song's iterator will be a concatenation of Section iterators, which are themselves concatenations of MusicTime iterators.

This last iterator is a special case. A MusicTime iterator should only return itself once:

@Override
public Iterator<MusicTime> iterator() {
    return Iterators.singletonIterator(this);
}

Alternatively, Section's iterator could be replaced with:

@Override
public Iterator<MusicTime> iterator() {
    return getChildren().iterator();
}

With this, iterating becomes as easy as:

for (MusicTime time : song) {
    player.play(time);
}

You can now do any kind of operation (playing, counting the total duration,...) without re-implementing the recursion.

There are alternative solutions for your problem though, but it all comes down to design choices. For example, you could have a play method on MusicComponent which Song and Section would implement by calling play on all of their children. This is a straightforward recursive implementation, but you must repeat the recursion for all operations you intend to add on MusicComponent (such as play, getTotalDuration, ...).

If you need more flexibility, you could use the Visitor design pattern and make your play operation a visitor (e.g. PlayVisitor). This has the advantage that you can decide to control the iteration order from within the visitor, but makes it harder to add new MusicComponent implementations.