This page is no longer maintained — Please continue to the home page at www.scala-lang.org

ListBuffer's Iterator implementation

No replies
extempore
Joined: 2008-12-17,
User offline. Last seen 35 weeks 3 days ago.

Regarding this ticket:

http://lampsvn.epfl.ch/trac/scala/ticket/3088

Unfortunately the committed fix caught ++=(Traversable) but missed
++=(Iterator), ++(Iterator), and ++(Traversable). The last two of those
are no longer issues as of my recent patch changing them to build a new
collection, since they call clone() ++=.

However in looking at this I think it is the implementation of Iterator
which ought to be changed. The way that ++=(Traversable) avoids looping
is to do a reference equality check on the argument to see if it's
trying to append itself to itself. This is not an option with Iterator,
but it will still loop, because Iterator will keep seeing new elements
in the buffer and keep iterating them. This prints 1s forever:

scala> val b = collection.mutable.ListBuffer[Int](1)
b: scala.collection.mutable.ListBuffer[Int] = ListBuffer(1)

scala> b.iterator foreach (x => { println(x) ; b += x })

I think calling .iterator on a ListBuffer ought to only try to iterate
over the listbuffer of that time: an implementation more like this.

override def iterator = new Iterator[A] {
private var elementsRemaining = size
private var cursor: List[A] = null

def hasNext: Boolean = !start.isEmpty && (cursor ne last0) && (elementsRemaining > 0)
def next(): A =
if (!hasNext) throw new NoSuchElementException("next on empty Iterator")
else {
elementsRemaining -= 1
cursor = if (cursor eq null) start else cursor.tail
cursor.head
}
}

Naturally uniterated elements can still change value between the call
and the iteration, but this makes a lot more sense to me (to the extent
that there's ever a sensible solution to rampant mutability.) If you
want the iterator to fully reflect the current state of the buffer, then
call for the iterator at the time you're iterating.

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland