Updating a PriorityQueue when iterating it

Question

I need to update some fixed-priority elements in a PriorityQueue based on their ID. I think it's quite a common scenario, here's an example snippet (Android 2.2):

for (Entry e : mEntries) {
    if (e.getId().equals(someId)) {
        e.setData(newData);
    }
}

I've then made Entry "immutable" (no setter methods) so that a new Entry instance is created and returned by setData(). I modified my method into this:

for (Entry e : mEntries) {
    if (e.getId().equals(someId)) {
        Entry newEntry = e.setData(newData);
        mEntries.remove(e);
        mEntries.add(newEntry);
     }
}

The code seems to work fine, but someone pointed out that modifying a queue while iterating over it is a bad idea: it may throw a ConcurrentModificationException and I'd need to add the elements I want to remove to an ArrayList and remove it later. He didn't explain why, and it looks quite an overhead to me, but I couldn't find any specific explanation on internet.

(This post is similar, but there priorities can change, which is not my case)

Can anyone clarify what's wrong with my code, how should I change it and - most of all - why?

Thanks, Rippel

PS: Some implementation details...

PriorityQueue<Entry> mEntries = new PriorityQueue<Entry>(1, Entry.EntryComparator());

with:

public static class EntryComparator implements Comparator<Entry> {
    public int compare(Entry my, Entry their) {
        if (my.mPriority < their.mPriority) {
            return 1;
        }
        else if (my.mPriority > their.mPriority) {
            return -1;
        }
        return 0;
    }
}

Create a stack maybe and then add the elements you want onto there after you are done. — Matt, Aug 18 '11 at 10:32

score 7 · Accepted Answer · 2011-08-18T10:57:52.790

This code is in the Java 6 implementation of PriorityQueue:

private class Itr implements Iterator<E> {
  /**
   * The modCount value that the iterator believes that the backing
   * Queue should have.  If this expectation is violated, the iterator
   * has detected concurrent modification.
   */
  private int expectedModCount = modCount;

  public E next() {
    if(expectedModCount != modCount) {
      throw new ConcurrentModificationException();
    }


  }

}

Now, why is this code here? If you look at the Javadoc for ConcurrentModificationException you will find that the behaviour of an iterator is undefined if modification occurs to the underlying collection before iteration completes. As such, many of the collections implement this modCount mechanism.

To fix your code

You need to ensure that you don't modify the code mid-loop. If your code is single threaded (as it appears to be) then you can simply do as your coworker suggested and copy it into a list for later inclusion. Also, the use of the Iterator.remove() method is documented to prevent ConcurrentModificationExceptions. An example:

List<Entry> toAdd = new ArrayList<Entry>();
Iterator it = mEntries.iterator();
while(it.hasNext()) {
  Entry e = it.next();

  if(e.getId().equals(someId)) {
    Entry newEntry = e.setData(newData);
    it.remove();
    toAdd.add(newEntry);
  }
}
mEntries.addAll(toAdd);

nice explanation and solution :) – berlindev Aug 18 '11 at 10:56 — berlindev, Aug 18 '11 at 10:56

ratchet freak · Answer 2 · 2011-08-18T13:12:41.157

0

a slightly better implementation is

List<Entry> toAdd = new ArrayList<Entry>();
for (Iterator<Entry> it= mEntries.iterator();it.hasNext();) {
    Entry e = it.next();
    if (e.getId().equals(someId)) {
        Entry newEntry = e.setData(newData);
        it.remove();
        toAdd.add(newEntry);
     }
}
mEntries.addAll(toAdd);

this uses the remove of the iterator and a bulk add afterwards

edited Aug 18 '11 at 13:12

answered Aug 18 '11 at 10:49

ratchet freak

47,288
5
68
106

score 0 · Answer 3 · answered Aug 18 '11 at 11:09

The Javadoc for PriorityQueue says explicitly:

"Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the list structurally. Instead, use the thread-safe PriorityBlockingQueue class."

This seems to be your case.

score 0 · Answer 4 · answered Aug 18 '11 at 11:26

What's wrong in your code was already explained -- implementing iterator, which can consistently iterate through collection with intersected modification is rather hard task to do. You need to specify how to deal with removed items (will it be seen through iterator?), added items, modified items... Even if you can do it consistently it will be rather complex and unefficient implementation -- and, mostly, not very usefull, since use case "iterate without modifications" is much more common. So, java architects choose to deny modification while iterate, and most collections from Java collection API follow this, and throw ConcurrentModificationException if such modification detected.

As for your code -- for me, your just should not make items immutable. Immutability is great thing, but it should not be overused. If Entry object you use here is some kind of domain object, and you really want them to be immutable -- you can just create some kind of temporary data holder (MutableEntry) object, use it inside your algorithm, and copy data to Entry before return. From my point of view it will be best solution.

Updating a PriorityQueue when iterating it

4 Answers4