remove (and count) duplicates from a list

Is it possible to iterate between two iterators of a same list and remove an item within the nested iterator?

Version 1 (does not work):

var i = all.iterator();
while (i.hasNext()) {
    var a = i.next();
    var j = all.iterator();
    while (j.hasNext()) {
        var b = j.next();
        if (!a.shouldBRemoved(b)) {
            a.setDuplicates(a.getDuplicates + 1);
            // I want to remove the element on the fly 
            // because on each iteration the iterated elements will have a decreased size and will iterate faster (because of fewer elements)
            // However: this does NOT work because of ConcurrentModificationException:
            j.remove();  
        }
    }

JavaScript
​x
 
var i = all.iterator();while (i.hasNext()) {    var a = i.next();    var j = all.iterator();    while (j.hasNext()) {        var b = j.next();        if (!a.shouldBRemoved(b)) {            a.setDuplicates(a.getDuplicates + 1);            // I want to remove the element on the fly             // because on each iteration the iterated elements will have a decreased size and will iterate faster (because of fewer elements)            // However: this does NOT work because of ConcurrentModificationException:            j.remove();          }    }​

}

I get a java.util.ConcurrentModificationException, because I modify an element within the same iterator..

I can solve this issue by using another list removableItems and put those items in it:

Version 2 (works):

for (var a : all) {
    for (var b : all) {
        if (!a.shouldBRemoved(b)) {
            a.setDuplicates(a.getDuplicates + 1);
            // this works, 
            // however I must use an additation list to keep track of the items to be removed
            // it's also not more performant than removing the elements on the fly 
            // because on each iteration the iterated elements has the same size
            removableItems.add(b);
        }
    }
}
all.removeAll(removableItems);

JavaScript
 
for (var a : all) {    for (var b : all) {        if (!a.shouldBRemoved(b)) {            a.setDuplicates(a.getDuplicates + 1);            // this works,             // however I must use an additation list to keep track of the items to be removed            // it's also not more performant than removing the elements on the fly             // because on each iteration the iterated elements has the same size            removableItems.add(b);        }    }}all.removeAll(removableItems);    ​

Is there a way to solve this without needing an intermediate list removableItems? I want to remove the element on the fly.

Answer

I found a good solution so far (Version 3):

List<Item> removeDuplicates(List<Item> all) {
        var uniqueResults = new ArrayList<Item>();
        for (var a : all) {
            for (var b : all) {
                // check if "a" and "b" is not the same instance, but have equal content
                if (!a.equals(b) && a.isDeepEqualTo(b)) {
                    if (a.duplicates == 0 && b.duplicates == 0) {
                        // "a" has duplicates: 
                        // Add only "a" and discard "b" for the rest of the loops.
                        uniqueResults.add(a);
                    }
                    // count the number of duplicates
                    a.duplicates = a.duplicates + 1;
                }
            }
            // "a" has no duplicates, add it.
            if (a.duplicates == 0 && !uniqueResults.contains(a)) {
                uniqueResults.add(a);
            }
        }
        return uniqueResults;
}

JavaScript
 
List<Item> removeDuplicates(List<Item> all) {        var uniqueResults = new ArrayList<Item>();        for (var a : all) {            for (var b : all) {                // check if "a" and "b" is not the same instance, but have equal content                if (!a.equals(b) && a.isDeepEqualTo(b)) {                    if (a.duplicates == 0 && b.duplicates == 0) {                        // "a" has duplicates:                         // Add only "a" and discard "b" for the rest of the loops.                        uniqueResults.add(a);                    }                    // count the number of duplicates                    a.duplicates = a.duplicates + 1;                }            }            // "a" has no duplicates, add it.            if (a.duplicates == 0 && !uniqueResults.contains(a)) {                uniqueResults.add(a);            }        }        return uniqueResults;}​

It works so far – I don’t see any edge cases where this would wrongly (not) remove.

It’s also better than using version 2 (with its removableItems()-list) as this is more performant (especially for huge lists) because we do not use remove or removAll, we only add items (which has O(1)).

Advertisement

Answer