创建一个递归迭代器

Question

我正在尝试为一组构成歌曲组件的类编写迭代器。所有类都是抽象的 MusicComponent 基类的实现，并继承了一个 getChildren() 函数。抽象的 MusicTime 子类知道要播放的实际音符/和弦，它的所有实现（如 quaver、crotchet）在 getChildren() 中返回 null。

其他的组件是 MusicComponent，其中包含一组 MusicTimes，例如一小节时间，以及 Section，其中包含 MusicComponents。Song 包含组成歌曲的 Sections，例如诗歌、副歌、拥有不同速度/拍号的部分。

我需要一个迭代器，它将遍历 Song 中的所有 Sections，然后遍历 Section 中的所有 MusicComponents，并且仅当找到 MusicTime 后，基于其音符类型以及其包含 Section 的时间签名和速度播放相应时长的音符。

抱歉如果信息太多，但这是我解释我正在尝试做什么的唯一方式。那我需要使用一个堆栈来处理它，记录我访问过的 MusicComponents，还是有一种只使用递归就可以完成的方法？

- Niall

Answer 1

您可以编写一个迭代器，它“连接”其子级的迭代器，甚至可以懒惰地这样做。在Song的迭代器上调用next()将会遍历Section和MusicComponent迭代器，并最终提供下一个MusicTime。 Guava使这变得容易。将MusicComponent作为Iterable<MusicTime>，并实现iterator()：

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

由于所有的孩子都是 MusicComponent，因此它们本身实现了 Iterable<MusicTime>，Song 的迭代器将是 Section 迭代器的连接，这些迭代器本身是 MusicTime 迭代器的连接。

最后一个迭代器是一个特殊情况。一个 MusicTime 迭代器只应该返回自己一次：

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

或者，Section的迭代器可以替换为：

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

使用这个，迭代就变得像这样容易：

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

现在，您可以在不重新实现递归的情况下执行任何类型的操作（例如播放、计算总时间等）。

不过，对于您的问题有替代解决方案，但这都取决于设计选择。例如，您可以在MusicComponent上拥有一个play方法，然后Song和Section通过调用其所有子级上的play来实现它。这是一种简单的递归实现，但您必须为您打算添加到MusicComponent上的所有操作（例如play、getTotalDuration等）重复递归。

如果您需要更多灵活性，则可以使用 Visitor设计模式并将播放操作制作成访问者（例如PlayVisitor）。这样做的好处是您可以决定从访问者内部控制迭代顺序，但较难添加新的MusicComponent实现。

- Mattias Buelens

---

谢谢，这似乎是我需要的，而且非常简单明了。然而，我遇到了一个错误。我已经下载了Guava并将其添加为外部库，并在MusicComponent上实现了Iterable，但在concat行中出现了java.lang.NoClassDefFoundError: com.google.common.collect.Iterables。您有什么想法是什么原因引起的吗？ - Niall

已经修复了那个错误，现在一切都正常了...但我还有一个问题。迭代器返回一个 MusicTime 作为第一个结果，但是否可能也获取包含它的 Section？这样当客户端遍历组件时，就可以决定如何处理它们。我能使用 Iterables 来实现吗？ - Niall

不用在意我之前的评论，那样处理我的需求是错误的，所以我找到了更好的方法。现在一切都解决了，而且运行得非常完美，非常感谢！ - Niall

@CrazyHorse 如果是这样的话，你最好使用访问者模式。Section 的 accept(Visitor) 方法可以为其所有子元素调用 visitSection 和 visitMusicTime。但是，您将失去迭代器所提供的“透明度”：访问者需要了解 Section 和 MusicTime，而使用迭代器的类只需要了解 MusicTime。无论哪种方式，您都已经解决了问题，这很棒。 :-) - Mattias Buelens

我通过在每个级别设置对包含对象的引用来解决了这个问题，因此我可以向上遍历树以找到每个MusicTime的Section`。不确定这是否是最佳方法，但似乎运行良好。我将研究访问者模式，因为我认为我可能最终需要这种灵活性。 - Niall

如果在您的应用程序中导航树结构很重要，那么这是一个不错的解决方案。您仍然可以在这样的树上使用迭代器，但如果发现需要更多的灵活性，您可能需要添加/切换到访问者模式。 - Mattias Buelens

Answer 2

你需要维护自己的堆栈。迭代器在找到下一个值时必须返回它。如果你可以用递归的方式编写代码，比如 recursiveMethod 调用自身，然后再次调用自身，最后在第三次调用内找出要返回的值，则调用堆栈应该会像这样：

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

当最内层的recursiveMethod返回时，它必须将值返回给客户端，然后客户端必须继续运行。这意味着调用堆栈上的前四个条目必须被弹出。然后，当客户端想要下一个值，并再次调用theIterator.next()时，上述三个recursiveMethod调用堆栈上的条目必须被重建，以便进程可以继续。Java没有一种方法可以做到这一点（至少在Java 7中；如果Java 8可以做到这一点，我不知道，因为我不熟悉所有的新功能）。

我所知道的唯一拥有多个调用堆栈的方法是使用多个线程。我不建议为此目的使用线程，但也许其他人已经成功地使用了它。

您可能想阅读Wikipedia关于协程的文章。

- ajb

Answer 3

由于所有组件都继承自同一个抽象类MusicComponent，我会在该类中实现默认方法play()。假设MusicComponent类还具有属性protected List<MusicComponent> children，则代码如下：

public void play(){

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

}

在 MusicTime 类中，我会重写 play() 方法来实际播放音乐，如下所示：

@Override
public void play(){

    //music playing logic
}

在其他类中不需要覆盖此方法，因为它们只是无法播放音乐的组合类。

创建完整的组件树后。要播放所有音乐，您需要在最顶层的组件上运行play()方法，即Song：

song.play()

它将迭代所有的子元素，最终到达最底层的MusicTime对象，音乐将在那里播放。这个答案基于我对你的问题的解释和我对组合设计模式的理解，我认为这是解决你的问题的一种可行方式。

- M7Jacks