java.util.ConcurrentModificationException in recursion

Question

i know after debugging that sons list is changed i don't know why it is changed and this modification causes me problems in my algorithm

public class IDS extends Algo {
public State found = null;

public IDS(char[][] input, int size) {
    super(input, size);
}

public String solve() {
    State root = new State(0, 0, 0, 0, "", 0, 0);
    for (int i = 0; i < size * size; i++) {
        found = DLS(root, i);
        if (found != null) {
            return found.path + " " + found.dist;
        }
    }
    return "no path";
}

private State DLS(State node, int depth) {
    if (depth == 0 && super.inp[node.row][node.col] == 'G') {
        return node;
    }
    if (depth > 0) {
        // List<State> sons = super.find_neighbors(node.row, node.col, node.prod_time);
        // for (int j = 0; j < sons.size(); j++) {
        //State cur = sons.get(j);
        for(State cur : super.find_neighbors(node.row, node.col, node.prod_time)){
            cur.addCost(node.dist);
            cur.path = cur.addpath(node.path);
            found = DLS(cur, depth - 1);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

}

here is the abstract class:

abstract class Algo {
public static Map<Integer,String> ways = new TreeMap<>();
protected char[][]inp;
protected int size;
private Map<Character,Integer>costs = new HashMap<>();
public List<State>sons = new ArrayList<>();

public Algo(){}
public Algo(char[][] input,int size){
   inp = input;
    this.size = size;
    ways.put(1,"R");
    ways.put(2,"RD");
    ways.put(3,"D");
    ways.put(4,"LD");
    ways.put(5,"L");
    ways.put(6,"LU");
    ways.put(7,"U");
    ways.put(8,"RU");
    costs.put('R',1);
    costs.put('D',3);
    costs.put('H',10);
    costs.put('G',0);
    costs.put('S',0);
}
private void addDirection(int row,int col,int prod, int loc){
    int cos = costs.get(inp[row][col]);
    State s = new State(row,col,0,prod,"",loc,cos);
    sons.add(s);
}
public abstract String solve();
//gets the parent i,j and the prod_t of the sons
public List<State> find_neighbors(int i, int j,int prod_t){
    List<String>openD = new ArrayList<>();
    sons.clear();

    if(j+1 < size) {//right
        if (inp[i][j + 1] != 'W') {
            addDirection(i, j + 1, prod_t, 1);
            openD.add("R");
        }
    }
    if(i-1 >= 0) {
        if (inp[i - 1][j] != 'W') {//up
            addDirection(i - 1, j, prod_t, 7);
            openD.add("U");
        }
    }
    if(i+1 < size) {
        if (inp[i + 1][j] != 'W') {//down
            addDirection(i + 1, j, prod_t, 3);
            openD.add("D");
        }
    }
    if(j-1 >= 0){
        if(inp[i][j-1]!='W'){//left
            addDirection(i,j-1,prod_t,5);
            openD.add("L");
        }
    }

    if(openD.contains("L")){
        if(openD.contains("U")){
            if(inp[i-1][j-1]!='W'){
                addDirection(i-1,j-1,prod_t,6);
            }
        }
        if(openD.contains("D")){
            if(inp[i+1][j-1]!='W'){
                addDirection(i+1,j-1,prod_t,4);
            }
        }
    }
    if(openD.contains("R")){
        if(openD.contains("U")) {
            if (inp[i - 1][j + 1] != 'W') {
                addDirection(i - 1, j + 1, prod_t, 8);
            }
        }
        if(openD.contains("D")){
            if(inp[i+1][j+1]!='W'){
                addDirection(i+1,j+1,prod_t,2);
            }
        }
    }
    return sons;
}

}

the exception just helped me know the list has modified however still don't know why :

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:859)
at java.util.ArrayList$Itr.next(ArrayList.java:831)
at IDS.DLS(IDS.java:33)
at IDS.solve(IDS.java:17)
at ex1.main(ex1.java:34)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

Do you understand what a ConcurrentModification indicates, and what causes it to be thrown? — Andy Turner
– Andy Turner, Commented Dec 2, 2016 at 13:47

Arne Deutsch · Accepted Answer · 2016-12-02 14:00:09Z

2

super.find_neighbors modifies and returns the sons list. Inside your loop the method DLS is recursively called which calls super.find_neighbors again (modifying the same list that is currently iterated one recursion above). Because the list is changed during you iterate over it the exception is thrown.

answered Dec 2, 2016 at 14:00

Arne Deutsch

14.8k5 gold badges56 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Esti Queroub Over a year ago

i understand that this function causes the problem... i will try to create a copy of the list so that sons won't held a pointer to the list in Algo class. if you have any creational idea that will solve it i will be glad to know about it, thank you

Serg M Ten · Accepted Answer · 2016-12-02 13:55:15Z

0

You are doings a sons.clear() inside Algo.find_neighbours() That will cause the ConcurrentModification in the loop. Moreover, since find_neighbours() always return an empty List, what's the poingt in trying to iterate over it?

answered Dec 2, 2016 at 13:55

Serg M Ten

5,6064 gold badges29 silver badges49 bronze badges

2 Comments

Maurice Perry Over a year ago

always return an empty list?

Serg M Ten Over a year ago

No, my bad, I missed part of the code, but the clear() inside it will cause the ConcurrentModification anyway in the loop.

Collectives™ on Stack Overflow

java.util.ConcurrentModificationException in recursion

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related