I have a feeling I'm missing something very obvious here.
I'm converting a compiler generator written in Java into Scala as a learning exercise.
It's not really written in Java, it seems to be transliterated C.
In one part of the program, there are Nodes. Each node is part of two linked lists, and there are fields that are references to the next item in each of the linked lists (call these "across" and "down"). Various methods traverse these lists, either one of them or both of them and do things to each visited node.
I'd like to use Scala's collections instead of these explicit references, since there's a lot of boilerplate code traversing and adding stuff to these lists. How do I do this? The lists are quite changeable so I want to use mutable lists
I think I don't want a linked list of Node, because each Node needs to know what its next across (or down) neighbor is, regardless of how I got to this node so I need to be able to go from Node to either list.
I could inherit from LinkedList, but I need to do that twice (once for across and once for down).
I could have two inner classes (acrosslist and downlist) each an instance of LinkedList, but can they be LinkedList[Node]? I can't get my head around how this would work, as the 'next reference for the list would need to be node.acrosslist.next (say) and for LinkedList it's just "next".
So, please point out the obvious, or if not obvious, how I get this to work!
Why don't you link things up yourself, and then create iterators in each direction?
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 }
}
}
Let me expand a bit on Rex Kerr's answer. There are really three central classes to all of Scala's collection, and only two of them are really part of the collections. They are Traversable, Iterable and Iterator.
The most basic collection is the Traversable. There's only one requisite for something to be a Traversable: it needs to implement the method foreach. So, as long as one can pass a function which will then be applied to each element of the collection, it can be a Traversable. For example:
class Three[A](a: A, b: A, c: A) extends Traversable[A] {
def foreach[U](f: (A) => U) {
f(a); f(b); f(c)
}
}
This will give you all of Traversable methods, though methods such as map and filter won't return a Three, but a Traversable. Getting it to return the class you defined is much more difficult, and many specialized classes just can't do it. For example, Three can't do it, because what would be the Three of a filter which removed some elements?
Next, there's the Iterator, which really does pretty much the same thing as Traversable, but in a different manner. An Iterator has to define two methods: next and hasNext. For example:
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
}
}
This will give all methods of Iterator, which mostly look the same as the methods in Traversable. The difference between the methods are mostly related to the fact that an Iterator can only be used once.
Finally, there's Iterable. To be an Iterable, a class has to implement one method: iterator, which returns an Iterator for that class. For example:
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
}
}
}
So, back to your question, you have to consider what is the expected behavior you want, and how do you want it. In particular, there's no notion of "down" and "left" in Scala collections, which means a Node could have a method returning a Scala collection, but could never be one properly speaking, such as we see on Rex Kerr's solution.
EDIT
Let me give an example distinct from Rex Kerr's. Here I'll do a Traversable Node, and the order of traversal will be selectable.
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) }
}
So this Node is Traversable, and it supports all of Traversable methods (though it still won't return a Node from map, etc -- look up other questions about this). You can select whether it will traverse left or down with a flag (traverseLeft), and all normal Traversable methods will use whatever is set in the node where the method was called.
This, however, is not a good model. I'd rather go with Rex Kerr's solution of returning iterators to left and down, or leave Scala collections completely and go with something processed with Kiama. The latter is a completely different paradigm, though, and not something you are going to shoe-horn into a code being transliterated to Scala.
