Wie mache ich eine Klasse zu einem Mitglied zweier verketteter Listen in Scala?

Question

Ich habe das Gefühl, dass mir hier etwas sehr offensichtlich fehlt.

Ich konvertiere einen Compiler-Generator in Java in Scala als Lernübung.

Es ist in Java nicht wirklich geschrieben hat, so scheint es, C. transkribiert werden

In einem Teil des Programms gibt es Knoten. Jeder Knoten ist Teil von zwei verknüpften Listen, und es gibt Felder, die Verweise auf das nächste Element in jeder der verknüpften Listen sind (rufen Sie diese "across" und "down" auf). Verschiedene Methoden durchqueren diese Listen, entweder eine von ihnen oder beide und tun Dinge zu jedem besuchten Knoten.

Ich würde gerne Scalas Kollektionen anstelle dieser expliziten Referenzen verwenden, da es eine Menge Standardcode gibt, der diese Listen durchquert und hinzufügt. Wie mache ich das? Die Listen sind ziemlich veränderbar, also möchte ich änderbare Listen verwenden.

Ich denke, ich möchte keine verknüpfte Liste von Knoten, weil jeder Knoten wissen muss, was sein nächster über (oder nach unten) Nachbar ist, egal wie ich bin zu diesem Knoten gekommen, also muss ich in der Lage sein, von Knoten zu jeder Liste zu gehen.

Ich könnte von LinkedList erben, aber ich muss dies zweimal tun (einmal für across und einmal für down).

Ich könnte zwei innere Klassen (acrosslist und downlist) jeweils eine Instanz von LinkedList haben, aber können sie LinkedList [Node] sein? Ich kann mir nicht vorstellen, wie das funktionieren würde, da die nächste Referenz für die Liste node.acrosslist.next (say) sein müsste und für LinkedList einfach "next".

Also, bitte zeigen Sie die offensichtliche, oder wenn nicht offensichtlich, wie ich das zum Funktionieren bringen!

Answer 1

Warum verknüpfen Sie die Dinge nicht selbst und erstellen dann Iteratoren in jeder Richtung?

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

Lassen Sie mich ein bisschen auf Rex Kerr ‚s answer erweitern. Es gibt wirklich drei zentrale Klassen für alle Scala-Sammlung, und nur zwei von ihnen sind wirklich Teil der Sammlungen. Sie sind Traversable, Iterable und Iterator.

Die grundlegendste Sammlung ist die Traversable. Es gibt nur eine Voraussetzung für etwas, um ein Traversable zu sein: es muss die Methode foreach implementieren. Solange also eine Funktion übergeben werden kann, die dann auf jedes Element der Sammlung angewendet wird, kann es sich um eine Traversable handeln. Zum Beispiel:

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

Dies wird Ihnen alle Traversable Methoden geben, obwohl Methoden wie map und filter keinen Three zurück, sondern eine Traversable. Es ist viel schwieriger, die von Ihnen definierte Klasse zurückzugeben, und viele spezialisierte Klassen können das einfach nicht. Zum Beispiel, Three kann es nicht tun, denn was wäre die Three einer filter, die einige Elemente entfernt?

Als nächstes gibt es die Iterator, die wirklich so ziemlich die gleiche Sache wie Traversable tut, aber auf andere Weise. Eine Iterator muss zwei Methoden definieren: next und hasNext.Zum Beispiel:

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 
    } 
} 

Dadurch werden alle Methoden der Iterator, geben die meist die gleichen wie die Methoden in Traversable suchen. Der Unterschied zwischen den Methoden hängt hauptsächlich damit zusammen, dass ein Iterator nur einmal verwendet werden kann.

Schließlich gibt es Iterable. Um eine Iterable zu sein, muss eine Klasse eine Methode implementieren: iterator, die eine Iterator für diese Klasse zurückgibt. Zum Beispiel:

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 
     } 
    } 
} 

Also, zurück zu Ihrer Frage, müssen Sie überlegen, was das erwartete Verhalten ist, dass Sie wollen, und wie wollen Sie es. Insbesondere gibt es in Scala-Sammlungen keine Vorstellung von "down" und "left", was bedeutet, dass Node eine Methode haben könnte, die eine Scala-Sammlung zurückgibt, aber niemals wäre, wie wir auf Rex Kerrs Lösung sehen.

EDIT

mich Lassen Sie uns ein Beispiel geben sich von Rex Kerr. Hier mache ich eine TraversableNode, und die Reihenfolge der Traversierung wird wählbar sein.

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) } 
} 

Also das Node ist Traversable und unterstützt alle Traversable Methoden (obwohl es noch kein Node von map usw. zurückkehren - andere Fragen zu diesem Thema nachschlagen). Sie können auswählen, ob es mit einem Flag (traverseLeft) nach links oder nach unten durchlaufen wird, und alle normalen Traversable Methoden verwenden das, was im Knoten festgelegt ist, auf dem die Methode aufgerufen wurde.

Dies ist jedoch kein gutes Modell. Ich würde lieber mit Rex Kerrs Lösung der zurückkehrenden Iteratoren nach links und nach unten gehen oder die Scala-Sammlungen vollständig verlassen und mit etwas arbeiten, das mit Kiama verarbeitet wurde. Letzteres ist jedoch ein völlig anderes Paradigma, und nicht etwas, das Sie in einen Code umwandeln, der nach Scala transkribiert wird.