not sure of reason for ConcurrentModificationException

Question

This is my code to construct a possible tour of citys in a Locale l (it's not optimal it's just to give my AI search a head start).

I'm getting a ConcurrentModificationException, which to my knowledge happens when more than one piece of code accesses an variable / collection and attempts to modify it. Causing this code to get unhappy:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

I modify it as I'm adding an element in, but as the Iterator does not have a method for adding (only removing) I'm using the collection's method.

So, my questions are:

1. Is my adding the element what's causing the problem?
2. If it is, how do I add it in correctly so that the modCount is correct and I don't get the ConcurrentModificationException?

Full method below, with a comment on the line where the ConcurrentModificationException happens:

public void construct() {
    tour = new ArrayList();
    ArrayList<City> lcl = new ArrayList(l.getCitys());

    tour.add(lcl.remove(0));
    tour.add(lcl.remove(1));

    while (!this.tourComplete()) {
        System.out.println(tour.size());
        Iterator tourit = tour.iterator();
        City g1 = (City) tourit.next();
        City g2 = (City) tour.get(lcl.indexOf(g1)+1);

        int gapDist = l.distanceBetweenCitys(g1, g2);

        while (tourit.hasNext()) {
            City C = null;
            int best = Integer.MAX_VALUE;

            for (Iterator lclit = lcl.iterator(); lclit.hasNext(); ) {
                City c = (City) lclit.next();
                int avg = (l.distanceBetweenCitys(g1,c) + 
                           l.distanceBetweenCitys(g2, c))/2 ;

                if ( (avg<gapDist) && (avg<best) ) {
                    C = c;
                    best = avg;
                }
            }

            if (C != null) {
                assert(best == Integer.MAX_VALUE);
                City A = tour.get(0);
                City Z = tour.get(tour.size()-1);

                boolean begin = true;

                for (Iterator lclit = lcl.iterator();   lclit.hasNext(); ) {
                    City c = (City) lclit.next();
                    int dist = l.distanceBetweenCitys(A,c);

                    if ( dist<best ) {
                        begin = true;
                        C = c;
                        best = dist;
                    }
                }

                for (Iterator lclit = lcl.iterator();   lclit.hasNext(); ) {
                    City c = (City) lclit.next();
                    int dist = l.distanceBetweenCitys(Z,c);

                    if ( dist<best ) {
                        begin = false;
                        C = c;
                        best = dist;
                    }
                }

                if (begin) {
                    // one of these is causing the problem
                    tour.add(0,C);
                }
                else {
                    // one of these is causing the problem
                    tour.add(C);
                }
            }
            else {
                // one of these is causing the problem
                tour.add(tour.indexOf(g2),C);
            }

            g1 = (City) tourit.next(); // this is where it all goes wrong 
            g2 = (City) tour.get(lcl.indexOf(g1)+1);
            gapDist = l.distanceBetweenCitys(g1, g2);
        }
    }
}

Answer 1

You cannot modify the underlying collection while using the iterator (except through the iterator itself).

I have not gone through your algorithm (you seem to want to insert at arbitrary positions, which could be tricky), but maybe you can do one of the following:

1. collect everything you want to add in a second collections, and doing an addAll after you're done.

2. Iterate over a copy of the collection instead.

3. Use a ListIterator, which does have an add method in addition to remove.

4. Not use an iterator at all, and just access the ArrayList by index (which you already do in other places anyway)

Also, you can do away with a lot of typecasts, by specifying the type of the iterator (same as you did with the list).

Answer 2

From the javadoc for ArrayList:

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Answer 3

Inside Iterator loop you are trying to modify the List
Excerpt from your code

if (begin) {
                    // one of these is causing the problem
                    tour.add(0,C);
                }
                else {
                    // one of these is causing the problem
                    tour.add(C);
                }

This is not permissible. Acc to javaDoc http://java.sun.com/j2se/1.4.2/docs/api/java/util/ConcurrentModificationException.html

This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible.For example, it is not generally permssible for one thread to modify a Collection while another thread is iterating over it. In general, the results of the iteration are undefined under these circumstances. Some Iterator implementations (including those of all the collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected. Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Answer 4

You can easily work around this by using an index variable instead of an iterator:

int i = 0;
while (i < tour.size()) {
    ....
    i++;
}

However, you will notice that inserting elements into a list you are iterating over raises some tricky questions. There is a reason why Iterator throws a ConcurrentModificationException, being that the logic for continuing the iteration is not well defined. If you insert an element before your index position, then the index no longer points to the same 'current' element and you need to increase the index by two to find the next element. If you insert after, then nothing changes except the stop condition (but tour.size() will grow correctly so that's ok). If you do multiple inserts/deletes at different positions, it gets kind of hard to keep track...

I have a feeling your algorithm cuold be simplified too, although it's not exactly clear to me what it's supposed to be doing.

Answer 5

This is my Ugly but now working code for anyone who want to see how i got it in the end, i intend to pretty it up quite a bit but for moment im happy with the fact it works

    public void construct()
{
tour = new ArrayList();
ArrayList<City> lcl = new ArrayList(l.getCitys());

tour.add(lcl.remove(0));
tour.add(lcl.remove(1));
tour.add(lcl.remove(2));

while (!this.tourComplete())
{

System.out.println(tour.size());
ListIterator<City> tourit = tour.listIterator();
City g1 = (City) tourit.next();
City g2 = (City) tour.get(tour.indexOf(g1)+1);

int gapDist = l.distanceBetweenCitys(g1, g2);

    while ((tourit.nextIndex()!=tour.size()-1) && !this.tourComplete())
    {
    System.out.println("x");
    City C = null;
    int best = Integer.MAX_VALUE;

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
        City c = (City) lclit.next();
        int avg = (l.distanceBetweenCitys(g1,c)+ l.distanceBetweenCitys(g2, c))/2 ;

        if ( (avg<gapDist) && (avg<best) )
        {
        C=c;
        best=avg;
        }

        }

    if (C==null)
    {
    System.out.println("C null");
        assert(best==Integer.MAX_VALUE);
        City A = tour.get(0);
        City Z = tour.get(tour.size()-1);

        boolean begin = true;

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
            City c = (City) lclit.next();
            int dist = l.distanceBetweenCitys(A,c);

            if ( dist<best )
            {
            begin=true;
            C=c;
            best=dist;
            }

        }

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
            City c = (City) lclit.next();
            int dist = l.distanceBetweenCitys(Z,c);

            if ( dist<best )
            {
            begin=false;
            C=c;
            best=dist;
            }

        }

        if(begin)
        {
        System.out.println("add at begining");
        System.out.println(this.TourtoString());
         // add in at 0

            int itpos = tourit.nextIndex();
            //move iterator to 0
            while (tourit.hasPrevious())
            {
            tourit.previous();
            }

            lcl.remove(C);
            // add in C
            tourit.add(C);

            // move iterator back
            while(tourit.nextIndex()!=(itpos+1))
            {
            tourit.next();
            }
        System.out.println(this.TourtoString());
        }
        else
        {
         // add in at end
            int itpos = tourit.nextIndex();
            //move iterator to end
            while (tourit.hasNext())
            {
            tourit.next();
            }

            lcl.remove(C);
            // add in C
            tourit.add(C);

            // move iterator back
            while(tourit.nextIndex()!=itpos)
            {
            tourit.previous();
            }
        }

    }
    else
    {
    System.out.println("C not null");

    // add in at g2
    int moveto = tour.indexOf(g2);
    int itpos = tourit.nextIndex();

    System.out.println("add at: "+ moveto);
    System.out.println(this.TourtoString());


    if (itpos>=moveto)
    {
    itpos++;
    }

    //move iterator to 0
    while (tourit.hasPrevious())
    {
    tourit.previous();
    }

    // move iterator to insertion location
    while (tourit.nextIndex()!=moveto)
    {
    tourit.next();
    }

    lcl.remove(C);
    // add in C
    tourit.add(C);

    //move iterator to 0
    while (tourit.hasPrevious())
    {
    tourit.previous();
    }


    // move iterator back
    while(tourit.nextIndex()!=itpos)
    {
    tourit.next();
    }

     System.out.println(this.TourtoString());
    }


    g1 = (City) tourit.next(); 
    g2 = (City) tour.get(tour.indexOf(g1)+1);
    gapDist = l.distanceBetweenCitys(g1, g2);
    }

}

}