Need help modifying list based on comparison values (ConcurrentModification)

Question

I am trying to see what possibility there is for something (don't tell me there isn't, this is my failed project) throughout an arrangement of points and their distances.

for (Point p1 : results) {
    remove.clear();
    for (Point p2 : results) {
        if (Math.sqrt(
            Math.pow(p1.getX() - p2.getX(), 2)
            + Math.pow(p1.getY() - p2.getY(), 2)
        ) % 1 > 0) {
            results.remove(p2);
        }
    }
}

Basically, I am trying to check if two points have an integer distance, and, if not, remove it from the set, and do this for all points (that remain).

However, I am getting a ConcurrentModificationException and I am not certain how to refactor it to accomplish the same task without just provoking the error in another way.

Are there any ways around this or is it just a limitation of Java?

EDIT: While the duplicate suggested link offers insight, the answers' focus on single loops has berth of excess that is not applicable. If this question is duplicate, it's on premise of that using an Iterator is just the answer.

possible duplicate of [Iterating through a list, avoiding ConcurrentModificationException when removing in loop](http://stackoverflow.com/questions/223918/iterating-through-a-list-avoiding-concurrentmodificationexception-when-removing) — Robert Moskal, Jul 07 '15 at 17:14
Not actually a duplicate since it involves a nested loop, which the referenced question does not. — Warren Dew, Jul 07 '15 at 17:16
@Warren: I don't see how an extra loop changes the problem or the solution. Do you think that the way of solving the problem will be different because of the extra loop? — sstan, Jul 07 '15 at 17:20
It doesn't work directly, it would require more handling because once a point is removed it is invalid for all future consideration. It gives the basis for a solution, but it itself is not one. — Captain Prinny, Jul 07 '15 at 17:21
@sstan The linked solution could work for the inner loop, but the outer loop will still throw a ConcurrentModificationException, even if you use an Iterator. To use an Iterator in the inner loop, the author will need to independently track what elements have been examined in the outer loop, rather than using an Iterator or for construct. This might mean that it would be better not to use an Iterator, but instead separately track what elements to delete, and delete them at the end. — Warren Dew, Jul 07 '15 at 17:22
@WarrenDew Same concept applies: removing an item from a collection directly while iterating over it. The "nested loop" doesn't change anything. — Vince, Jul 07 '15 at 17:23
@VinceEmigh Are you certain it works that way, or would both loops need converting to iterator, and, even then, would that work? — Captain Prinny, Jul 07 '15 at 17:41

score 1 · Answer 1 · answered Jul 07 '15 at 17:22

1

You could do this:

Iterator<Point> iterator = results.iterator();
while (iterator.hasNext()) {
  Point p1 = iterator.next();
  boolean shouldBeRemoved = false;
  for(Point p2 : results) {
    if (p2 != p1 && (Math.sqrt(Math.pow(p1.getX() - p2.getX(), 2)
                             + Math.pow(p1.getY() - p2.getY(), 2))
                     % 1 > 0)) {
      shouldBeRemoved = true;
      break;
    }
  }
  if (shouldBeRemoved) {
    iterator.remove();
  }
}

The difference is that obviously p1 gets removed instead of p2, but since we're dealing with a Set here...

remove it from the set

... the ordering isn't important, right?

answered Jul 07 '15 at 17:22

Sam Estep

12,974
2
37
75

A good basis, but it needs to still iterate through the entire set of p2. Doing this through iteration seems to be where the problem comes in. – Captain Prinny Jul 07 '15 at 17:24
@CaptainPrinny By "problem", I assume you mean the `ConcurrentModificationException`. Does the code I've posted actually cause such an exception? – Sam Estep Jul 07 '15 at 17:25
I expect it might not, but I was trying my own modifications while waiting. Currently waiting for it to finish or fail. – Captain Prinny Jul 07 '15 at 17:26
Not all `Set` implementations are unordered. And set isn't capitalized. – Vince Jul 07 '15 at 17:56

Vince · Accepted Answer · 2015-07-07T18:02:53.577

1

Some Collection implementations use a "fail-fast" iterator. When removing an item from a Collection directly (using Collection#remove) while iterating over it will cause that exception.

Enhanced for-loops uses the collection's iterator to iterate through the collection.

You could change your enhanced loops to regular for loops:

for(int i = 0; i < results.size(); i++) {
    for(int j = 0; j < results.size(); j++) {
    Point result = results.get(j);
        if(...) {
            //results.remove(j); or
            //results.remove(result);
        }
    }
}

As mentioned in the comments, this will not work for Set. In that case, you could simply keep a reference to the collection's iterator, and use that to remove the item:

Iterator<Point> firstIter = results.iterator();
while(firstIter.hasNext()) {
    Point p1 = iterator.next();

    Iterator<Point> secondIter = results.iterator();
    while(secondIter.hasNext()) {
        Point p2 = secondIter.next();

        if(...) {
            secondIter.remove();
        }
    }
}

edited Jul 07 '15 at 18:02

answered Jul 07 '15 at 17:26

Vince

14,470
7
39
84

This only works if `results` is a `List`, not if it is a `Set` or other type of `Collection`. – Sam Estep Jul 07 '15 at 17:27
@RedRoboHood Check the title.. "*Need help modifying **list***" – Vince Jul 07 '15 at 17:29
Nowhere in the title or the post does "List" with a capital L appear. The word "set" (*"remove it from the **set**"*), however, does appear, which gives me reason to believe that this question is about arbitrary collections. – Sam Estep Jul 07 '15 at 17:30
It's what I went to immediately, while waiting. I was initially using List, but I think about it as a "set" of things, poor rigor on my part. – Captain Prinny Jul 07 '15 at 17:42
@CaptainPrinny Editing my answer – Vince Jul 07 '15 at 17:45
So do Iterators themselves remain safe from the base problem? I've yet to use iterators in Java, I'll have to add it to my bag. – Captain Prinny Jul 07 '15 at 18:04
@CaptainPrinny Yes. Using an `Iterator` gets rid of the possibility of the exception. Although, you should only use it if you feel you need to remove an item whole iterating over a `Set` – Vince Jul 07 '15 at 21:44
@VinceEmigh Any good resources on the operation of Iterators in java for why/why not? I've only used them in C++, so I'm not fully grasping the why of that I should only use it in that situation. – Captain Prinny Jul 08 '15 at 13:51
@CaptainPrinny As mentioned in the answer, enhanced for-loops use an `Iterator` under the hood, so you'd just use one of those (unless you want to remove an element, of course). As for the indexed loop, the only data structure I find it to have an impact on is `LinkedList`, which is [pretty understandable](http://stackoverflow.com/a/2113226/2398375). I personally cannot find any other data structure besides `LinkedList` (or other doubly linked lists) that suffer from a huge performance impact while using indexed loops. – Vince Jul 08 '15 at 15:36

score 0 · Answer 3 · answered Jul 07 '15 at 17:25

This seems to be happening because you are trying to remove the same Point structure. Consider the case of the first point. Both p1 and p2 refer to the first point in results. The distance between p1 and p2 is zero because they refer to the same point. You are then trying to remove p2 which is actually p1 itself. Please refer to the link http://docs.oracle.com/javase/7/docs/api/java/util/ConcurrentModificationException.html for more on why you can get this exception even in the case when one thread is trying to access and modify some structure.

You could modify the above code like the following:-

boolean[] if_deleted = new boolean[results.size()];

for (int i = 0; i < results.size(); ++i) {
    if_deleted[i] = false;
}

for (int i = 0; i < results.size(); ++i){
    for(int j = i + 1; j < results.size(); ++j)
            Point p1 = (Point)results.get(i);
            Point p2 = (Point)results.get(j);
            if (!if_deleted[i] && !if_deleted[j]) { 
                if (Math.sqrt(
                    Math.pow(p1.getX() - p2.getX(), 2)
                            +
                            Math.pow(p1.getY() - p2.getY(), 2))
                    % 1 > 0){
                        if_deleted[j] = true;
                        results.remove(p2);
                }
            }    
    }
}

for (int i = 0; i < results.size(); ++i) {
    if (if_deleted[i]) {
        results.remove(i);
    }
}

This only works if `results` is a `List`, not if it is a `Set` or other type of `Collection`. — Sam Estep, Jul 07 '15 at 17:27
It's not important that it is or isn't a set, trying it. Giving "variable declaration not allowed here", so needs more refactoring. Missing a { after second for. — Captain Prinny, Jul 07 '15 at 17:31
I am trying to suggest a way using which the intended behavior may work. This is not the complete and compilable solution as such. — gaurav gupta, Jul 07 '15 at 17:39
Ah, my bad. It actually doesn't seem to work. I didn't look at it strongly, but it appears to be stuck in an infinite loop somewhere. The math logic doesn't actually remove the point itself, as in my running code it output 0,0 (point "1") just fine. — Captain Prinny, Jul 07 '15 at 17:44

score 0 · Answer 4 · answered Jul 07 '15 at 17:31

I refactored to

    for (int p1 = 0;  p1 < results.size() ; p1++){
        for (int p2 = p1;  p2 < results.size() ; p2++){
                if (Math.sqrt(
                        Math.pow(results.get(p1).getX() - results.get(p2).getX(), 2)
                            +
                        Math.pow(results.get(p1).getY() - results.get(p2).getY(), 2))
                        % 1 > 0){
                            results.remove(p2);
                            p2--;
                }
        }
    }

But I'm not sure it's working as I expected it to.

Need help modifying list based on comparison values (ConcurrentModification)

4 Answers4