java.util.ConcurrentModificationException due to unintended modification

Question

I'm implementing the A* algorithm to allocate a given number of taxis to a given number of customers:

public SearchNode AStarSearch(List<Car> allCars, List<Customer> allCustomers) {

    // creates first node
    SearchNode firstNode = createFirstNode(allCars, allCustomers);
    open.add(firstNode);

    SearchNode currentNode;

    while(true) {
        currentNode = open.poll();   //error thrown here
        if (currentNode.allCustomers.isEmpty()) break;

        closed.add(currentNode);

        SearchNode temp;

        Iterator<Customer> itrCus = currentNode.allCustomers.iterator();
        Iterator<Car> itrCar = currentNode.allCars.iterator();

        while (itrCus.hasNext()) {
            Customer currentCustomer = itrCus.next();
            while (itrCar.hasNext()) {
                Car currentCar = itrCar.next();
                temp = new SearchNode(currentNode, currentCar, currentCustomer);
                openUpdate(currentNode, temp);
            }
        }
    }
    return currentNode;
}

Now for the children SearchNode I want to delete the customer, that it has served. But this should only happen inside the search node.

This is what's happening in the SearchNode class:

public class SearchNode implements Comparable<SearchNode> {

List<Car> allCars;
List<Customer> allCustomers;
SearchNode parent;

public SearchNode(SearchNode parent, Car currentCar, Customer currentCustomer) {
    // inheriting values from parent search node
    this.allCars = parent.allCars; 
    this.allCustomers = parent.allCustomers;
    this.parent = parent;

    // now updating this node's values
    this.allCustomers.remove(currentCustomer);
}

I checked with some prints and in the second iteration of the while(itrCar.hasNext()), the parent's allCustomer list is missing the currentCustomer.

Edit: I should rather ask: can someone please tell my why I changed my parent node's value? It's probably because I haven't understood the whole java being actually pass-by-reference.

"Can someone please tell me how I could have changed the parent node's values?" `this.allCustomers.remove(currentCustomer);`, since `this.allCustomers = parent.allCustomers`. — Andy Turner, Mar 19 '19 at 08:28
Java is 100% pass by value. References to objects are passed by value. — Peter Lawrey, Mar 19 '19 at 08:30
@AndyTurner well yes, but i thought this (with this. in front) will only change the value inside the node. not the value of the parent node that was only passed to create a new object instance...? — vanessaxenia, Mar 19 '19 at 08:30

score 4 · Answer 1 · answered Mar 19 '19 at 08:29

You should create a copy of the List from which you want to locally remove the customer:

public SearchNode(SearchNode parent, Car currentCar, Customer currentCustomer) {
    // inheriting values from parent search node
    this.allCars = parent.allCars; // consider making a copy here too
                                   // if required
    this.allCustomers = new ArrayList<>(parent.allCustomers); // make a 
                                                              // copy
    this.parent = parent;

    // now updating this node's values
    this.allCustomers.remove(currentCustomer); // now you can safely 
                                               // remove currentCustomer
                                               // without affecting 
                                               // parent.allCustomers
}

can I also ask at this point what's the difference between initializing the ArrayList as `new ArrayList(parent.allCustomers);` and your suggestion? — vanessaxenia, Mar 19 '19 at 21:55

Corrodias · Accepted Answer · 2019-03-21T17:56:50.160

All variables holding Objects such as Lists are essentially pointers (nitpickers might disagree with the exact terminology, but I'm sure it's close enough). So when you say

this.allCustomers = parent.allCustomers

this.allCustomers and parent.allCustomers now point to the same List object. Then

this.allCustomers.remove(currentCustomer)

is running .remove() on that list... which is the parent's allCustomers... which is currently being iterated over. Since the list gets modified, the iteration fails.

To clarify a comment made on the question, "Java is 100% pass by value. References to objects are passed by value." means that you cannot implement the function "swap" from the C language^[1] because the function gets copies (values) of the pointers/references and cannot change the values of the originals, but a function can modify the properties of an object whose pointer/reference it is given and have those modifications visible to the caller who passed the object in because they refer to the same object. Primitive types (int, boolean, etc) pass by value, but they are immutable (you can say x = 3 and then x = 5, but there is no 3.changeValueTo(5)), so the difference can largely be ignored.

···

[1]: That is barring use of the Unsafe class, which has direct access to memory. Don't use it, as it can seriously break things. Clever engineers who can use it for good (e.g., Java internals use it sometimes) won't need my advice on it anyway.

java.util.ConcurrentModificationException due to unintended modification

2 Answers2