Java Puzzle for Iterator!

Few days back I came across this puzzle posted on the java specialist news letter.
When I tried to run this program I got following error:-
 
public class test {
 public static void main(String args[])
 {
  final List list = new ArrayList() {{ add("Hello"); }};
  final Iterator iterator = list.iterator();
  System.out.println(iterator.next());
  list.add("World");
  // FIXME : work here while I'm sunbathing
  System.out.println(iterator.next());
}
}
 
Error:-
 
Hello
Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:449)
        at java.util.AbstractList$Itr.next(AbstractList.java:420)
        at test.main(test.java:11)
 

When I analyzed further I  found that there is a piece of code in AbstractList(ArrayList extends AbstractList) which creates new Instance of Itr class(Inner class of
AbstractList) :-
 
public Iterator iterator() {
                return new Itr();
    }
 

From Itr class:-
Itr class has a line which set expectedModCount to modCount. Here  modCount is defined in AbstractList. This variable keep track of number of time the internal Array is “structurally modified”.
int expectedModCount = modCount;
 
When we call list.iterator() the value of expectedModCount and modCount will be zero.
When we add “World” the modCount is increment to 1.
 
Now when we call iterator.next(), Itr.next() will be called which in turn call checkForComodification(), and this method check the expectedModCount to modCount and if these are not equal then throws
“ConcurrentModificationException()”.
 
The whole idea is that once we create an Iterator, and while doing the operation on the iterator the underlying List object should not be modified. If we modify the list structure then modCount will not be same as the expectedModCount.
 
 
Now coming to the solution part:-
After executing list.add(“World”) the value of modCount will be 1 (increment from 0) and expectedModCount will be 0.
Our aim is to make modCount to zero so that when we call iterator.next() we don’t get ConcurrentModificationException.
 
If you analyze the code if ArrayList you realize that there is no way we can decrease the value of modCount. There is only one possible solution is to increment modCount so that it will overflow the capacity of integer(modCount is declared as int) and this value become zero(if you do Integer.MAX_VALUE+1 you get Integer.MIN_VALUE) and if adding 1 you will get 0). There are two methods which modify(increment) the modCount  without modifying the underlying List. These are
ArrayList. ensureCapacity and ArrayList. trimToSize. Here is the solution:-
 

 
import java.util.*;
import java.math.*;
 public class test2 {
 public static void main(String args[])
 {
  final List list = new ArrayList() {{ add("Hello"); }};
  final Iterator iterator = list.iterator();
  System.out.println(iterator.next());
  list.add("World");
  // FIXME : work here while I'm sunbathing
//This loop will take long time.
  for(int modCount=2;modCount != -1 ;modCount++)
  {
      // ((ArrayList)list).trimToSize();
         ((ArrayList)list).ensureCapacity(0);
  }
 //((ArrayList)list).trimToSize(); //After this statement:- modCount = -1
 //((ArrayList)list).trimToSize(); // After this statement modCouunt = 0
   ((ArrayList)list).ensureCapacity(0);
   ((ArrayList)list).ensureCapacity(0);
 System.out.println(iterator.next());
  }
}
 
Output:-
 
Hello
World

Advertisements

One response to “Java Puzzle for Iterator!

  1. Grt Vivek 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s