如何使一个类成为 Scala 中两个链表的成员？

Question

我有一种感觉，我在这里遗漏了一些非常明显的东西。

作为学习练习，我正在将用 Java 编写的编译器生成器转换为 Scala。

它并不是真正用Java编写的，它似乎是音译为C的。

在程序的一部分中，有Nodes。每个节点都是两个链表的一部分，并且有一些字段是对每个链表中下一项的引用（称为“跨”和“下”）。各种方法遍历这些列表（其中一个或两个）并对每个访问的节点执行操作。

我想使用 Scala 的集合而不是这些显式引用，因为有很多样板代码遍历并向这些列表添加内容。我该怎么做？列表是相当多变的，所以我想使用可变列表

我想我不想要节点的链接列表，因为每个节点都需要知道它的下一个跨（或下）邻居是什么，无论我如何到达这个节点所以我需要能够从 Node 转到任一列表。

我可以从 LinkedList 继承，但我需要这样做两次（一次是横向的，一次是向下的）。

我可以有两个内部类（crosslist 和 downlist），每个内部类都是 LinkedList 的实例，但它们可以是 LinkedList[Node] 吗？我无法理解这是如何工作的，因为列表的下一个引用需要是 node.acrosslist.next （比如说），而对于 LinkedList 来说它只是“下一个”。

所以，请指出明显的，或者如果不明显的话，我如何让它发挥作用！

Answer 1

为什么不自己将事物链接起来，然后在每个方向创建迭代器？

class Node(var left: Node, var down: Node) {
  def iterateDown = new Iterator[Node] {
    private[this] var current = this
    def hasNext = down ne null
    def next = { current = down; current }
  }
  def iterateLeft = new Iterator[Node] {
    private[this] var current = this
    def hasNext = left ne null
    def next = { current = left; current }
  }
}

Answer 2

让我详细介绍一下 Rex Kerr 的 答案。 Scala 的所有集合实际上包含三个中心类，但其中只有两个真正属于集合的一部分。它们是Traversable、Iterable和Iterator。

最基本的集合是Traversable。要成为 Traversable ，只有一个先决条件：它需要实现 foreach 方法。因此，只要可以传递一个函数，然后将该函数应用于集合的每个元素，它就可以是一个Traversable。例如：

class Three[A](a: A, b: A, c: A) extends Traversable[A] {
    def foreach[U](f: (A) => U) {    
        f(a); f(b); f(c)
    }
}

这将为您提供所有 Traversable 方法，尽管 map 和 filter 等方法不会返回 Three< /code>，而是一个可遍历。让它返回您定义的类要困难得多，许多专门的类无法做到这一点。例如，Three 无法做到这一点，因为删除一些元素的 filter 的 Three 是什么？

接下来是 Iterator，它的功能与 Traversable 几乎相同，但方式不同。 Iterator 必须定义两个方法：next 和 hasNext。例如：

class Three[A](a: A, b: A, c: A) extends Iterator[A] {
    private var aReady, bIsRead, cIsRead = false
    def hasNext = !(aIsRead && bIsRead && cIsRead)
    def next = (aIsRead, bIsRead, cIsRead) match {
        case (false, _, _) => aIsRead = true; a
        case (_, false, _) => bIsRead = true; b
        case (_, _, false) => cIsRead = true; c
        case _ => Iterator.empty.next
    }
}

这将给出 Iterator 的所有方法，它们大部分看起来与 Traversable 中的方法相同。这些方法之间的差异主要与迭代器只能使用一次这一事实有关。

最后，还有Iterable。要成为 Iterable，类必须实现一个方法：iterator，该方法返回该类的 Iterator。例如：

class Three[A](a: A, b: A, c: A) extends Iterable[A] {
    // not necessary, but may offer a more efficient implementation
    override def foreach[U](f: (A) => U) {    
        f(a); f(b); f(c)
    }

    def iterator = new Iterator[A] {
        private var aReady, bIsRead, cIsRead = false

        def hasNext = !(aIsRead && bIsRead && cIsRead)
        def next = (aIsRead, bIsRead, cIsRead) match {
            case (false, _, _) => aIsRead = true; a
            case (_, false, _) => bIsRead = true; b
            case (_, _, false) => cIsRead = true; c
            case _ => Iterator.empty.next
        }
    }
}

那么，回到你的问题，你必须考虑你想要的预期行为是什么，以及你想要如何实现它。特别是，Scala 集合中没有“向下”和“向左”的概念，这意味着 Node 可以有一个返回 Scala 集合的方法，但永远不可能是一个正确地说，就像我们在 Rex Kerr 的解决方案中看到的那样。

编辑

让我举一个与 Rex Kerr 不同的例子。这里我将做一个Traversable Node，并且遍历的顺序是可选择的。

class Node[A] extends Traversable[A] {
    var left: Node[A] = _
    var down: Node[A] = _
    var traverseLeft = true
    var value: A = _

    def foreach[U](f: (A) => U) = if (traverseLeft) foreachLeft(f) else foreachDown(f)

    def foreachLeft[U](f: (A) => U) { f(value); if (left != null) left.foreachLeft(f) }
    def foreachDown[U](f: (A) => U) { f(value); if (down != null) down.foreachDown(f) }
}

所以这个 Node 是 Traversable，并且它支持所有 Traversable 方法（尽管它仍然不会返回 Node > 来自 map 等 - 查找与此相关的其他问题）。您可以使用标志 (traverseLeft) 选择它是向左还是向下遍历，所有普通的 Traversable 方法都将使用调用该方法的节点中设置的任何内容。

然而，这不是一个好的模型。我宁愿采用 Rex Kerr 的将迭代器返回到左侧和向下的解决方案，或者完全保留 Scala 集合并使用 Kiama。不过，后者是一个完全不同的范例，您不会将其硬塞到转写为 Scala 的代码中。