2

I have an ArrayList of objects that have a version number as a field. I want to do some work on that ArrayList, but I only want the most recent version of the object. I was thinking of coding as such:

ArrayList<ObjectVO> ObjectList = getObjectList();
for(ObjectVO myVO : ObjectList) {
  Iterator<ObjectVO> iter = ObjectList.iterator();

  while(iter.hasNext()) {
     ObjectVO checkVO = iter.next();
     if(myVO.getID().equals(checkVO.getID()) {
         //they are the same object ID.  Check the version number, remove it lower
         if(myVO.getVersion() > checkVO.getVersion()) {
              iter.remove();
         }
      }
   }
 }

Is this valid? I don't know if the fact that we are in a for loop originally would break the mutability of the ArrayList at runtime.

9
  • 1
    No, this won't work. iter.remove() will cause the out for loop to fail with ConcurrentModificationException. Commented Jun 20, 2019 at 21:38
  • @AndyTurner Could I just replace the first for loop with another Iterator, and have two iterators running in parallel? Commented Jun 20, 2019 at 21:44
  • You would have to use the iterator in the outer loop, and the enhanced for loop in the inner loop. That should work I guess. Commented Jun 20, 2019 at 21:47
  • @DorianGray no, that would also break. Commented Jun 20, 2019 at 21:47
  • @user3334871 are you trying to keep the thing with the highest version number? Commented Jun 20, 2019 at 21:49

4 Answers 4

0

No, this won't work. iter.remove() will cause the out for loop to fail with ConcurrentModificationException.

Instead of doing this, you can do this with indexed for loops, and a BitSet to keep track of things you want to remove:

BitSet toRemove = new BitSet();
for (int m = 0; m < ObjectList.size(); ++m) {
  if (toRemove.get(m)) continue;
  ObjectVO myVO = ObjectList.get(m);

  for (int c = 0; c < ObjectList.size(); ++c) {
    if (toRemove.get(c)) continue;
    ObjectVO checkVO = ObjectList.get(c);

    if(myVO.getID().equals(checkVO.getID()) {
      //they are the same object ID.  Check the version number, remove it lower
      if(myVO.getVersion() > checkVO.getVersion()) {
          toRemove.set(c);
      }
    }
  }
}

This is basically your code, but it doesn't do the removal yet. Then you can sweep through the list after and remove them:

int dst = 0;
for (int src = 0; src < ObjectList.size(); ++src) {
  if (!toRemove.get(src)) {
    ObjectList.set(dst++, ObjectList.get(src));
  }
}
ObjectList.subList(dst, ObjectList.size()).clear();

The point of using a BitSet like this is that removal from an ArrayList is inefficient if you are removing from anywhere other than the end, because it requires all of the elements "to the right" of the element you remove to be shuffled along by one position. The loop with the set/get and clear allows you to only move each of the retained elements once.


You can do a bit better than the quadratic loop, though, if you group the list elements by things with the same ID: then you don't need to keep on checking the entire list:

BitSet toKeep = new BitSet();
IntStream.range(0, ObjectList.size())
    .mapToObj(a -> a)
    .collect(
        groupingBy(a -> ObjectList.get(a).getID(),
                   maxBy(comparingInt(a -> ObjectList.get(a).getVersion()))))
    .values()
    .forEach(a -> toKeep.set(a));

int dst = 0;
for (int src = 0; src < ObjectList.size(); ++src) {
  if (toKeep.get(src)) {
    ObjectList.set(dst++, ObjectList.get(src));
  }
}
ObjectList.subList(dst, ObjectList.size()).clear();
Sign up to request clarification or add additional context in comments.

Comments

0

Assuming you have the memory, rather than do an O(N^2) operation, you could do this more efficiently (O(N)) by using a Map to track the newest Version for each Id. One pass tracks the newest version for each Id, and the second removes elements which are not the latest.

Map<Integer, Thing> newestById = new HashMap<>();

for (Thing thing : list) {
  newestById.merge(thing.id, thing, (a,b) -> a.version > b.version ? a : b);
}
list.removeIf(thing -> thing != newestById.get(thing.id)); }

Depending on your use case, you might even be able to store your data in a Map instead of a List, and check if the version is the latest before adding it to the Map.

Comments

0

As the other answers have discussed this won't work. You have three options as I see them, trading memory for CPU cycles/flexibility. I've used Integer instead of ObjectVO in my examples, but it'll be trivial to swap them.

Option 1 - moderate memory, single-pass of the array

Track the highest ID you've seen and populate an ArrayList with new items as they meet the criteria. When you encounter a new higher ID, throw away the ArrayList and create a new one:

ArrayList<Integer> objectList = getObjectList();
Integer bestId = -1;
ArrayList<Integer> allObjectsMatchingId = new ArrayList<>();
for(Integer currentObject : objectList) {
    if(currentObject > bestId) {
        bestId = currentObject;
        allObjectsMatchingId = new ArrayList<>();
    } else if(currentObject == bestId) {
        allObjectsMatchingId.add(currentObject);
    }
}
return allObjectsMatchingId;

Option 2 - more expensive memory, single-pass of the array, most flexible.

For each ID you see, create an ArrayList and store it against a map. This allows you to easily change the criteria about what ID you want to keep.

ArrayList<Integer> objectList = getObjectList();
Map<Integer, ArrayList<Integer>> objectsById = new HashMap<>();
for(Integer currentObject : objectList) {
    ArrayList<Integer> listForId = objectsById.get(currentObject);
    if(listForId == null) {
        listForId = new ArrayList<Integer>();
    }
    listForId.add(currentObject);
    objectsById.put(currentObject, listForId);
}
Integer bestId = -1;
for(Integer i : objectsById.keySet()) {
    if(i > bestId) {
        bestId = i;
    }
}
return objectsById.get(bestId);

Option 3 - no additional memory aside from id, two-passes of the array.

Search through the ArrayList for the highest ID, then filter the array to only elements that pass that filter.

This is the closest to your current implementation, the difference being that you do them in separate steps. This reduces complexity from O(N^2) to O(N), and is valid as you aren't modifying the ArrayList while iterating it. You could use a Stream here to filter instead of an iterator if you're Java 8 compatible. See Java: Efficient ArrayList filtering?

ArrayList<Integer> objectList = getObjectList();
Integer bestId = -1;
for(Integer currentObject : objectList) {
    if(currentObject > bestId) {
        bestId = currentObject;
    }
}
Iterator<Integer> iter = objectList.iterator();
while(iter.hasNext()) {
    if(iter.next() != bestId) {
        iter.remove();
    }
}

Comments

0

Why not use Java Streams to solve this:

Collection<ObjectVO> result = objectList.stream()
        .collect(Collectors.toMap(ObjectVO::getID, Function.identity(),
                BinaryOperator.maxBy(Comparator.comparing(ObjectVO::getVersion))))
        .values();

This creates a map which contains the max version for each id. Then you can just use Map.values() to get the object list.

If you need a List or an ArrayList you can just use new ArrayList<>(result).

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.