Modify iterator

Question

I have a iterator (ite) created from a set (a):

var a = Set(1,2,3,4,5)
var ite = a.iterator

If I remove 2 element of my set:

a -= 2

Now, if I move iterator for all elements, I get all elements (2 element included). It's ok, but... How I can tell to iteratator to delete 2 element?

Answer 1

It looks like you're confused. a -= 2 doesn't remove element 2. If it could, then a would, by definition, be a mutable set, since you're changing it. a -= 2 creates a brand new set that looks like the old one, and assigns it to the variable a. How is ite supposed to magically know that this has happened?

The answer is, it can't--not if it's already started running. That is, in fact, the whole point of using immutable data structures. If someone else decides the world looks differently now, you aren't thrown into confusion--you keep working on your old copy that looks the same as ever.

But if the iterator hasn't already been used, and you just want a handy label that means "get the iterator of a", you can

var a = Set(1,2,3,4,5)
val ite = () => a.iterator
a -= 2
ite().foreach(println)  // Prints 5,1,3,4 or the like--no 2

Here, ite is not a variable, it's a function that happens to be a closure of a.iterator. It calls a.iterator every time you use it, so it's always up to date (at least initially). You could also create a lazy iterator that doesn't actually pick which version a to use until it's needed:

var a = Set(1,2,3,4,5)
lazy val ite = a.iterator   // Not a.iterator now, but will be when we need it!
a -= 2
ite.foreach(println)   // Need it now--so we'll get 5,1,3,4

Note that in this case, if you call a method that takes an iterator, ite will be set when it is passed to the function. The previous version--that takes a function returning an iterator--will only create the iterator once.

Now, you might want an iterator that can deal with deleted entries by looking at the current value of a. You can do that, too, but it's easier to implement if the deleted results come back None and the undeleted ones come back Some(x):

var a = Set(1,2,3,4,5)
val ite = new Iterator[Option[Int]] {
  private val it = a.iterator
  def hasNext = it.hasNext
  def next = {
    val i = it.next
    if (a(i)) Some(i) else None
  }
}
a -= 2
ite.foreach(println)  // Some(5),Some(1),None,Some(3),Some(4)

(Otherwise, you'd have to cache values, since hasNext in this iterator would need to call next in the a's iterator so it could check if that element still existed.)

Anyway, there are lots of options, but you need to decide which sensible thing to do that it is that you really want to do.

Answer 2

If you absolutely, positively insist on this narrow definition of the task, you've got a problem.

One way to reconceptualize the problem is to iterate over the collection's elements while collecting a new collection that holds the elements to be deleted. Then delete those elements from the input collection after the iteration loop completes.

Another way is to use the partition(...) method to create two new collections from the input, those for which a predicate is true and those for which it is false.

Answer 3

You can store the deleted elements for iterator and skips these.

class DeletableIterator[X](it : Iterator[X]) extends Iterator[X]{
    val deleted = collection.mutable.Set[X]()
    var nextElement : Option[X] = getNext
    private def getNext : Option[X] = {
        if(it.hasNext) {
            val n = it.next
            if(deleted contains n) getNext else Some(n) 
        } else None
    }
    def next = {
        val r = nextElement.get
        nextElement = getNext
        r
    }
    def hasNext = nextElement.isDefined
    def -(x : X) = {
        deleted += x
        this
    }
}

implicit def iterator2DeltableIterator[X](i : Iterator[X]) = new DeletableIterator(i)

This could be useful as long as there are not too many elements to delete.

var a = Set(1,2,3,4,5)
var ite = a.iterator
ite -= 2
ite -= 1
ite.toList

scala> ite.toList
res2: List[Int] = List(5, 3, 4)

Answer 4

The problem is that your Set is immutable (Scala defaults to immutable collections), but because a is a variable and not a value, the following call a -= 2 is actually performing a = a - 2. So it does not mutate the set but assign a new set to a.

Instead, you can use a mutable set: var a = collection.mutable.Set(1,2,3,4,5).

scala> var a = collection.mutable.Set(1,2,3,4,5)
a: scala.collection.mutable.Set[Int] = Set(1, 4, 2, 5, 3)

scala>  val i = a.iterator
i: Iterator[Int] = non-empty iterator

scala> a -= 2
res0: scala.collection.mutable.Set[Int] = Set(1, 4, 5, 3)

scala> i.toList
res1: List[Int] = List(5, 3, 1, 4)

Answer 5

The problem is that you have to use a mutable Set for this to work. Otherwise a new Set is created with the expression: a -= 2. And the previously generated iterator ite has reference to the first one not the new one. See the next transcript of 2 REPL sessions (with immutable and mutable Set)

Welcome to Scala version 2.8.0.RC3 (Java HotSpot(TM) Client VM, Java 1.6.0_11).
Type in expressions to have them evaluated.
Type :help for more information.

scala> var a = Set(1,2,3,4,5)
a: scala.collection.immutable.Set[Int] = Set(4, 5, 1, 2, 3)

scala> var ite = a.iterator
ite: Iterator[Int] = non-empty iterator

scala> a -= 2

scala> a.toList
res1: List[Int] = List(5, 1, 3, 4)

scala> ite.toList
res2: List[Int] = List(5, 1, 2, 3, 4)

scala> ite.toList
res3: List[Int] = List()

----------------------------------

Welcome to Scala version 2.8.0.RC3 (Java HotSpot(TM) Client VM, Java 1.6.0_11).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.collection.mutable.Set
import scala.collection.mutable.Set

scala> var a = Set(1,2,3,4,5)
a: scala.collection.mutable.Set[Int] = Set(1, 4, 2, 5, 3)

scala> var ite = a.iterator
ite: Iterator[Int] = non-empty iterator

scala> a -= 2
res0: scala.collection.mutable.Set[Int] = Set(1, 4, 5, 3)

scala> ite.toList
res1: List[Int] = List(5, 3, 1, 4)

scala> ite.toList
res2: List[Int] = List()