Creating a recursive iterator

Question

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

Other MusicComponent components that contain the MusicTimes , for example. bar at a time, and Section , which contains MusicComponents . Song contains Sections that make up a song, for example. verses, choirs, sections with different tempos / time signatures.

I need an iterator that will MusicComponents over all Sections in Song and then all MusicComponents in Section and only when it finds a descendant of MusicTime , play a note for the length of time based on its type of note and the time and pace of its Section content.

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

Answer 1

You can write an iterator that “concatenates” your child’s iterators, even lazily. The next() call on the Song iterator will then expand through the Section and MusicComponent and finally deliver the next MusicTime .

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

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

Since all children are MusicComponent elements and therefore themselves implement Iterable<MusicTime> , the Song iterator will be a concatenation of Section iterators, which themselves are concatenations of MusicTime iterators.

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

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

Alternatively, the Section iterator can be replaced by:

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

In this case, the iteration becomes as simple as:

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

Now you can perform any operation (playback, counting the total duration, ...) without re-implementing recursion.

There are alternative solutions for your problem, but it all comes down to choosing a design. For example, you can use the play method on MusicComponent , which Song and Section will implement, invoking play for all your children. This is a simple recursive implementation, but you must repeat the recursion for all operations that you intend to add to the MusicComponent (e.g. play , getTotalDuration , ...).

If you need more flexibility, you can use the visitor design template and make your game a game visitor (for example, PlayVisitor ). The advantage of this is that you can control the iteration order within the visitor, but it makes it difficult to add new implementations of MusicComponent .

Answer 2

You will need to save your own stack. The iterator needs to return the next value when it finds it. If you can write it recursively, say using recursiveMethod call yourself, and then call yourself again, and then the third time it calls, it will know what value will be returned, the call stack would look like

 recursiveMethod recursiveMethod recursiveMethod theIterator.next the client that using the iterator 

When the internal recursiveMethod returns, it must return the value to the client, and then the client must continue to work. This means that the first four entries in the call stack should be displayed. Then, when the client wants the next value, and it calls theIterator.next() again, the three above recursiveMethod entries in the call stack must be restored so that the process can continue. Java is not able to do this (at least through Java 7, if Java 8 does this, I don’t know about it, since I am not familiar with all the new features).

The only way I know to have multiple call stacks is to have multiple threads. I would not recommend using threads for this purpose, but maybe others did it with him.

You might want to read the Wikipedia article on coroutine .

Answer 3

Since all components inherit from the same abstract MusicComponent class, I would use the default play() method in this class. Assuming that the MusicComponent class also has a protected List<MusicComponent> children property, it will look like this:

 public void play(){ for(MusicComponent component: children){ component.play(); } } 

In the MusicTime class MusicTime I would override the play () method to actually play the music, as shown below:

 @Override public void play(){ //music playing logic } 

You should not redefine this method in other classes, as they are simply composite classes that cannot play music.

After creating a complete component tree. To play all the music, you need to run the play() method for the top component, which is Song :

 song.play() 

He will sort through all the children, eventually reaching the smallest MusicTime objects where music will be played. This answer is based on my interpretation of your problem and my understanding of the Composite Design Pattern , which in my opinion is a viable way to solve your problem.