I'm trying to implement Dijkstra's shortest path algorithm in my maze. ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm )
I got two HashSets, one for visited and one for unvisited fields. Once a field has been visited by all its neighbors through the algorithm, I want to put it in the visited map and remove it from the unvisited.
However, when I try to run the algorithm I get a ConcurrentModificationException in Netbeans.
Funny thing is - I've read up on the problem and from what I understand, this issue comes forth from trying to manipulate / remove data from the Set, not from iterating over it. However, I get the error on an iteration of the set, namely:
for( Field unvisited : unvisitedFields ) {
Since I got time issues, a work-around for the issue would suffice but if I'm using bad practice, I'd love to know what a better approach to solving this problem would be. Full code of method below, unvisitedFields is initialized as a class variable but has same parameters as visitedFields. Reason for it being a class variable is because I fill it at the top of my class, together with a 2D array.
public void calculcateSPath(Field curLocation , Field target ) {
Set<Field> visitedFields = new HashSet<>();
ArrayList<Field> shortestPath = new ArrayList<>();
shortestPath.add( target );
curLocation .setDistance( 0 );
unvisitedFields.remove( curLocation );
visitedFields.add( curLocation );
// until all fields have a corresponding value to field, it continues searching.
while( unvisitedFields.isEmpty() == false ) {
// iterate through the Set containing all unvisited fields.
for( Field unvisited : unvisitedFields ) {
//iterate through the Set containing all visited fields.
for( Field posNeighbor : visitedFields ) {
// if the unvisited field has a visited field as neighbor
if( unvisited.allNeighbors().containsValue( posNeighbor )) {
// check if the wall between them is down
if(( unvisited.getNeighbor( Direction.up ).equals( posNeighbor ) && posNeighbor.drawDown() == false )
|| ( unvisited.getNeighbor( Direction.right ).equals( posNeighbor ) && unvisited.drawRight() == false )
|| ( unvisited.getNeighbor( Direction.down ).equals( posNeighbor ) && unvisited.drawDown() == false )
|| ( unvisited.getNeighbor( Direction.left ).equals( posNeighbor ) && posNeighbor.drawRight() == false )) {
visitedFields.add( posNeighbor );
// if so, check if the current distance is smaller than the previous distance.
if( unvisited.getDistance() > ( posNeighbor.getDistance()+1 ) ) {
// assign the new shorter distance and the connection point
unvisited.setDistance( posNeighbor.getDistance() + 1 );
unvisited.setVisitedNeighbors( 1 );
unvisited.setPrevious( posNeighbor );
}
// if not, add a count to the visited neighbors
} else {
unvisited.setVisitedNeighbors( 1 );
}
//if all neighbors have been visited, remove the field from the unvisited list and add to visited.
if( unvisited.getVisitedNeighbors() == unvisited.allNeighbors().size() ) {
unvisitedFields.remove( unvisited );
visitedFields.add( posNeighbor );
}
}
}
}
}
} // ends calculateSPath()
From the API:
The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
This means that if you want to modify the collection while iterating over it you must use the iterator.remove() method. Rather than using a for each loop, try something like this:
Collection items = ...
Iterator itr = items.iterator();
while(itr.hasNext()) {
Object o = itr.next();
boolean condition = ...
if(condition) {
itr.remove();
}
}
Or if you can (and would prefer to) make the modification after the iteration is complete you can do something like this:
Collection items = ...
Collection itemsToRemove = ...
for (Object item : items) {
boolean condition = ...
if (condition) {
itemsToRemove.add(item);
}
}
items.removeAll(itemsToRemove);
If your collection is of type List, then you can get a ListIterator by invoking listIterator(). A ListIterator augments Iterator by adding methods which allow traversing the list bidirectionally and allows modifying the collection by adding and removing items, or replacing the current item.