5

In the first line of the loop I get the error, but I don't see why. From what I read this should happen only if I'm iterating over a collection and trying to modify it at the same time, but this is not the case.

In the code, list is of type ArrayList<Product>.

void mergeSort() { 
    mergeSort(0, list.size() - 1); //128
}

private void mergeSort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(p, q); //133
        mergeSort(q + 1, r);
        merge(p, q, r); //135
    }
}

private void merge(int p, int q, int r) {
    List<Product> left = list.subList(p, q);
    left.add(Product.PLUS_INFINITE);
    List<Product> right = list.subList(q + 1, r);
    right.add(Product.PLUS_INFINITE);
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; ++p) {
        Product x = left.get(i).compareTo(right.get(j)) <= 0 ? left.get(i++) : right.get(j++); //147
        list.set(k, x);
    }
}

This is the stacktrace:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1415)
    at java.base/java.util.ArrayList$SubList.get(ArrayList.java:1150)
    at ProductList$ProductSort.merge(MainClass.java:147)
    at ProductList$ProductSort.mergeSort(MainClass.java:135)
    at ProductList$ProductSort.mergeSort(MainClass.java:133)
    at ProductList$ProductSort.mergeSort(MainClass.java:128)
    at ProductList.sort(MainClass.java:95)
    at MainClass.main(MainClass.java:187)
Boann
  • 48,794
  • 16
  • 117
  • 146
gian_
  • 95
  • 6

1 Answers1

8

subList does not create a new list that has the same elements as the original list in the specified range. Rather, it creates a "view" (docs):

Returns a view of the portion of this list [...]. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa.

Also note:

The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list.

This is exactly what you are doing in merge. You are creating sublists left. Then modifying left structurally with add. So far so good. But then you created another sublist right and modifies it as well. This makes "the semantics of left to become undefined". And this causes the next call to get to throw an exception.

Minimal reproducible example:

ArrayList<String> list = new ArrayList<>(List.of("1", "2", "3", "4"));
List<String> left = list.subList(0, 2);
List<String> right = list.subList(2, 4);
right.add("5");
left.get(0);

Sublists are a bit like iterators in this regard (you can only remove via the iterator, if you remove via the original list, CME might be thrown).

One simple way to fix this is to create copies of the sublists so that they are no longer "views", but are actually independent lists:

List<Product> left = new ArrayList<>(list.subList(p,q));
List<Product> right = new ArrayList<>(list.subList(q+1,r));
Sweeper
  • 213,210
  • 22
  • 193
  • 313
  • Thanks for the information. I tried this solution but the error persists with the same stacktrace. – gian_ May 02 '21 at 02:01
  • @gian_ There shouldn't be a CME any more, but I found that your merge sort algorithm is implemented incorrectly. You probably meant to increment `k` instead of `p` in the for loop, and your indices seem a bit confused. The second parameter of `sublist` is exclusive while the first is inclusive. So `subList(p,q)` and `subList(q+1,r)` is totally skipping `q`, and ignoring `r`. You probably have other mistakes, that's just a few I saw. – Sweeper May 02 '21 at 02:29
  • Oops, yes, I meant to increment ```k```, and I wasn't aware that the second parameter of ```subList``` was exclusive. With these two fixes you suggested the code is working now, and the CME exception is gone. Thanks! – gian_ May 02 '21 at 02:41