How to make a class a member of two linked lists in Scala?

Question

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!

Oxpecker

Answer 1

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

Cytolysin

Of course, I can do this. But there's a whole lot of code that's repeated in every case - and that's what I'm trying to avoid. The problem is a bit worse than I described, since there are maybe 6-10 classes, each with at least one linked list so as a mimumum I'd like to generalise the behaviour above into a trait - I've not managed that yet though. I'd also like to be able to use for comprehensions, foreach etc (so far I've found there's equivalents for find, foreach, forall, exists and corresponds) – Oxpecker

For left/down, just trait DoubleIterable[A] { var left: A; var down: A ; /* iterator defs here */ } and then class Node extends DoubleIterable[Node]? – Cytolysin

Yeah. Still more duplication around than I'd like. – Oxpecker

@Paul - What exactly is getting duplicated here? You mean that you have to write more than one iterator? It'll be a bit slower, but you can def makeIterator[A](getNext: => A, setNext: A => Unit) = { /* You fill this in */ } and then trait DoubleIterable[A] { /*...*/ ; def iterateDown = makeIterator(left, left_= _) ; /*...*/ }. – Cytolysin

Is the iterator all I have to write to get foreach/forall etc working? Or will I end up with multiple implementations of them too? Paul (currently attempting a depth first exploration of Scala's collection features :)) – Oxpecker

@Paul - You will get everything in Iterator if you create a new iterator. Keep in mind that methods that create a new collection (e.g. map) will create a collection of its choice, not of whatever custom structure you have. But it's still very useful. – Cytolysin

Answer 2

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.

Cusk

Thanks. I'll need to read that again more slowly. However "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.". In this application, most of the time left and down are insjoint in that I'm either iterating down, or left but not a mixture. Could Node then 'be' each of the two collections? I think you're saying no. because method names like iterator are hardwired. – Oxpecker

@Paul Yes, there is a single order of traversal in a collection, though it could be toggled. I'll put an example of that in the answer. – Cusk