How to keep two iterators over map in java and remove keys in between without ConcurrentModificationException

Question

I have to process a Map <BitSet,List<List<Integer>> MyMap

if (key1 contains all of corresponding true bits of key2)
     Remove from key2 all those values which are common with key1)

In this process, if the number of elements in a list drops below a THRESHOLD (user defined positive integer), it is removed. Also if the Map contains empty list, then corresponding key is removed.

I am using following code:

List<BitSet> keys = new ArrayList<>(MyMap.keySet());  
ListIterator it1=keys.listIterator();
while(it1.hasNext())  {
     BitSet key1=(BitSet)it1.next();
     ListIterator it2=keys.listIterator(it1.nextIndex());
     while(it2.hasNext()) {
         BitSet key2=(BitSet)it2.next();                 
         BitSet ankey=(BitSet)key1.clone();
         ankey.and(key2);    
         if(ankey.equals(key1)) {//key1 is subset and key2 is superset
               if(removePoints(key1,key2))  {
                     it1.remove();
                     break;
               }
         }
         else if(ankey.equals(key2))  {                           
              if(removePoints(key2,key1))  {
                    it2.remove();                         
              }
         }
     }
}

public static boolean removePoints(BitSet key1,BitSet key2)
 {
     List<List<Integer>> list1=MyMap.get(key1);         
     List<List<Integer>> list2=MyMap.get(key2);
     Boolean ret=false;         
     for(int i=0;i<list1.size();i++)  {                   
         List<Integer> sublist1=list1.get(i);            
         for(int j=0;j<list2.size();j++)  {            
             List<Integer> sublist2=list2.get(j);                 
             sublist1.removeAll(sublist2);
             if(sublist1.isEmpty())
                 break;
         }
         if(sublist1.size()<=THRESHOLD)
             list1.remove(sublist1);
         if( list1.isEmpty()) {             
             MyMap.remove(key1); 
             ret=true;                 
         }
     }
     return ret;
 }

But the program is giving error:

java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification
at java.util.ArrayList$Itr.next

Also, am not sure if this is the efficient way to code? As the Map contain ~2000 entries. Please advise.

Answer 1

A ConcurrentModificationException can happen when the underlying collection is modified after an Iterator is created, and that modification isn't done through the Iterator itself.

In your code as written, there is only one place where that can happen: the interation between it1 and it2, which are iterators on the same collection. Anytime you call remove on one, the other one will break the next time you call next.

There's a variety of ways to work around this, but one way is to separate what you're removing from your 'key' collection from the iteration of that collection, like so:

List<BitSet> allKeys = new ArrayList<>(MyMap.keySet());  
List<BitSet> removedKeys = new ArrayList<>();

for (ListIterator<BitSet> it1 = allKeys.listIterator(); it1.hasNext(); ) {
   BitSet key1 = it1.next();
   for (ListIterator<BitSet> it2 = allKeys.listIterator(it1.nextIndex()); it2.hasNext(); ) {
       BitSet key2 = it2.next();
       BitSet ankey=(BitSet)key1.clone();
       ankey.and(key2);    
       if(ankey.equals(key1)) {//key1 is subset and key2 is superset
           if(removePoints(key1,key2))  {
                 removedKeys.add(key1);
                 break;
           }
       }
       else if(ankey.equals(key2))  {                           
          if(removePoints(key2,key1))  {
                 removedKeys.add(key2);
                 break;
          }
       }
    }
}

allKeys.removeAll(removedKeys);

allKeys will then be in the state that you expect. I assume that sometime later you would want to call MyMap.keySet().retainAll() or similar.

Answer 2

You can not use iterator.remove() on the Map's keySet since it's only a "view" on the internal structure of the map.

But you can use an iterator on the map's entrySet(), where each element is an instance of Map.Entry containing all you map entries (key/value pairs). You can call iterator.remove() on this iterator, that will effectivly remove the corresponding key/value pair from the map.

Map<Integer, String> map = new HashMap<Integer, String>();
map.put(Integer.valueOf(0), "0");
map.put(Integer.valueOf(1), "1");
map.put(Integer.valueOf(2), "2");
map.put(Integer.valueOf(3), "3");
map.put(Integer.valueOf(4), "4");

System.out.println(map);

Iterator<Map.Entry<Integer, String>> entryIter = map.entrySet().iterator();
while (entryIter.hasNext()) {
   Map.Entry<Integer, String> entry = entryIter.next();
   if (entry.getKey().intValue() % 2 == 0)
       entryIter.remove();
}

System.out.println(map);

Hope that it helps.

Regards