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

Question

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

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

Это на самом деле не написано вЯва, кажется, транслитерирована 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

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

EDIT

Позвольте мне привести пример, отличный от Рекса Керра. Здесь я сделаю 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 будут использовать все, что установлено в узле, где был вызван метод.

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