Как сделать класс членом двух связанных списков в Scala?

Question

У меня такое чувство, что я упускаю что-то очень очевидное здесь.

Я преобразовываю генератор компилятора, написанный на Java, в Scala в качестве учебного упражнения.

Это не совсем написано на Java, кажется, транслитерированный C.

В одной части программы есть узлы. Каждый узел является частью двух связанных списков, и есть поля, которые являются ссылками на следующий элемент в каждом из связанных списков (назовите их "поперек" и "вниз"). Различные методы пересекают эти списки, либо один из них, либо оба из них, и выполняют действия для каждого посещаемого узла.

Я хотел бы использовать коллекции Scala вместо этих явных ссылок, так как существует много шаблонного обхода кода и добавления материала в эти списки. Как мне это сделать? Списки довольно изменчивы, поэтому я хочу использовать изменяемые списки

Я думаю, что мне не нужен связанный список узлов, потому что каждый узел должен знать, каков его следующий сосед (или нисходящий) сосед, независимо от того, как я попал на этот узел, поэтому мне нужно иметь возможность перейти от узла к любому список.

Я мог бы наследовать от LinkedList, но мне нужно сделать это дважды (один раз для поперек и один раз для вниз).

Я мог бы иметь два внутренних класса (по списку и по списку), каждый из которых является экземпляром 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, но Traversable, Получить возвращаемый вами класс намного сложнее, и многие специализированные классы просто не могут этого сделать. Например, Three не могу этого сделать, потому что что бы Three из filter какие элементы удалены?

Далее есть 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, Разница между методами в основном связана с тем, что Iterator можно использовать только один раз.

Наконец, есть 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, но никогда не мог бы быть таковым, если говорить правильно, как мы видим в решении Рекса Керра.

РЕДАКТИРОВАТЬ

Позвольте мне привести пример, отличный от Рекса Керра. Здесь я сделаю TraversableNodeи порядок обхода будет выбираемым.

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 методы будут использовать все, что установлено в узле, где был вызван метод.

Это, однако, не очень хорошая модель. Я бы предпочел пойти с решением Рекса Керра о возврате итераторов влево и вниз или оставить коллекции Scala полностью и перейти к чему-то, обработанному с помощью Kiama. Последняя, ​​тем не менее, представляет собой совершенно другую парадигму, а не то, что вы собираетесь вставить в код, транслитерируемый в Scala.