Remove / add objects and avoid ConcurrentModificationException

Programming Questions

clankill3r

Remove / add objects and avoid ConcurrentModificationException

in Programming Questions • 7 months ago

I have a node layout which make together a map.

On that map i use pathfinding to find routes.

The format i used to load was not perfect so every node is on top of another node, for example in the image B, C and D will be on the same position.

My goal is to keep only one of those 3 and relink the links.

This is what the Node class looks like.

class Node implements Comparable<Node> {
int id;
float lon;
float lat;
// A*
float f = 0;
float g = 0;
float h = 0;
Node parent;
HashSet<Node> links = new HashSet<Node>();
Node() {
}
Node(float lon, float lat) {
this.id = idCount++;
this.lon = lon;
this.lat = lat;
}
Node(int id, float lon, float lat) {
this.id = id;
this.lon = lon;
this.lat = lat;
}
void linkToNode(Node n) {
links.add(n);
}
void reset() {
f = g = h = 0;
parent = null;
}
int compareTo(Node n) {
if(f < n.f) return -1;
if(f == n.f) return 0;
return 1;
}
}

So to reform what i want:

I want B and C removed and A and E connected to D (or anything like that).

I either have a bug, or i get a ConcurrentModificationException or a IllegalStateException.

Here i have 3 attempts (i have more attempts but those where the best / closest i guess).

There is one ArrayList called nodes which hold all nodes. So the overlapping ones have to be removed from there, except one. And then every node has a hashSet called links, the ones that get removed from nodes shouldn't be present anymore in links.

I hope this is enough to help.

If not i will upload the files required to run my code later.

void mergeOverlappingNodes() {
for(int i = nodes.size()-1; i >= 0; i--) {
Node n = nodes.get(i);
for(Node linkedNode : n.links) {
if ( (n.lon == linkedNode.lon) && (n.lat == linkedNode.lat)) {
nodes.remove(linkedNode);
i--;
for(Node linkedNodeFromTheOneToRemove : linkedNode.links) {
linkedNodeFromTheOneToRemove.links.remove(linkedNode);
linkedNodeFromTheOneToRemove.links.add(n);
}
}
}
}
}

void mergeOverlappingNodes() {
Iterator<Node> itr = nodes.iterator();
while(itr.hasNext()) {
Node n = itr.next();
boolean remove = false;
// check if the node can be removed
for(Node linkedNode : n.links) {
if ( (n.lon == linkedNode.lon) && (n.lat == linkedNode.lat)) {
remove = true;
break;
}
}
for(Node linkedNode : n.links) { //ConcurrentModificationException
linkedNode.links.remove(n);
}
for(Node linkedNode1 : n.links) {
for(Node linkedNode2 : n.links) {
linkedNode1.links.add(linkedNode2);
}
}
/*
for(Node aLinkedNodeFromTheOneToRemove : linkedNode.links) {
//if(aLinkedNodeFromTheOneToRemove == n) println("true");
aLinkedNodeFromTheOneToRemove.links.remove(linkedNode);
aLinkedNodeFromTheOneToRemove.links.add(n);
}
*/
//linkedNode.links.add(n);
if(remove) itr.remove();
}
}

One of the firsts, which has no error but a bug..

void mergeOverlappingNodesOld() {
Node theNode, otherNode;
for (int i = nodes.size()-1; i >= 0; i--) {
theNode = nodes.get(i);
ArrayList<Node> nodesOnTheSamePosition = new ArrayList<Node>();
// in this loop we find all nodes on the same position
// and add them to the ArrayList: nodesOnSamePosition
for (int j = nodes.size()-1; j >= 0; j--) {
otherNode = nodes.get(j);
if (theNode == otherNode) continue;
if ( (theNode.lon == otherNode.lon) && (theNode.lat == otherNode.lat)) {
nodesOnTheSamePosition.add(otherNode);
}
}
// now relink and remove
for(Node aNodeOnTheSamePosition : nodesOnTheSamePosition) {
for(Node linkedNode : aNodeOnTheSamePosition.links) {
theNode.links.add(linkedNode);
}
nodes.remove(aNodeOnTheSamePosition);
theNode.links.remove(aNodeOnTheSamePosition);
}
// added in attempt to bug fix
// now added above which in theory should work
/*
for(Node aNodeOnTheSamePosition : nodesOnTheSamePosition) {
theNode.links.remove(aNodeOnTheSamePosition);
}
*/
// since nodes.size() is changed now we have to decrement i
i -= nodesOnTheSamePosition.size();
}
/*
Node node1, node2;
HashSet<Node> nodesToRemove = new HashSet<Node>();
//HashSet<Node> nodesNotToRemove = new HashSet<Node>();
for (int i = nodes.size()-1; i >= 0; i--) {
node1 = nodes.get(i);
for (int j = nodes.size()-1; j >= 0; j--) {
node2 = nodes.get(j);
if (node1 == node2) continue;
if (nodesToRemove.contains(node1)) continue;
if ( (node1.lon == node2.lon) && (node1.lat == node2.lat)) {
HashSet<Node> links = new HashSet<Node>(node1.links);
for (Node n : links) {
n.links.remove(node1);
n.links.add(node2);
// we have to remove them later else things go wrong
nodesToRemove.add(node1);
//nodesNotToRemove.add(node2);
}
}
}
}
// println(nodesToRemove.size());
Iterator<Node> itr = nodesToRemove.iterator();
while (itr.hasNext ()) {
Node nodeToRemove = itr.next();
//if(nodesNotToRemove.contains(nodeToRemove)) continue;
nodes.remove(nodeToRemove);
}
*/
// check if correct
/*
for (Node n1 : nodes) {
for (Node n2 : nodes) {
if (n1 == n2) continue;
if ( (n1.lon == n2.lon) && (n1.lat == n2.lat)) {
println("my code is wrong...");
}
}
}
*/
}

Replies(2)

GoToLoop

Re: Remove / add objects and avoid ConcurrentModificationException

7 months ago

Your code is too complex for me to grasp it on a quick look!

Anyways, I was successful at removing elements from an ArrayList
when iterating over it in a backwards loop, w/o using any auxilliary Iterator!

I made it so that an object instance itself would tell my loop that it's fit for removing!

Here's a sample of it:

  for ( int b = bullets.size(); b != 0; )
    if ( bullets.get(--b).run() )   bullets.remove(b);

For more details, take a look at these posts:
http://forum.processing.org/topic/array-usage-objects-in-general
http://forum.processing.org/topic/arraylist-confusion-changing-the-variables-of-an-extracted-object-with-get

Who knows you can grab some solution from those posts?!

clankill3r

Re: Remove / add objects and avoid ConcurrentModificationException

7 months ago

I finally got it. I never had so many attempts to try one thing.

This one is totally different from the above ones.

here the solution:

void mergeOverlappingNodes() {
HashSet<Node> remove = new HashSet<Node>();
ArrayList<Node> newNodes = new ArrayList<Node>();
for(Node n : nodes) {
// maybe we allready handled this node
// if so continue to the next
if(remove.contains(n)) continue;
ArrayList<Node> replace = new ArrayList<Node>();
// check if any of the links is overlapping
// if so add it to the combine ArrayList
for(Node linkedNode : n.links) {
if ( (n.lon == linkedNode.lon) && (n.lat == linkedNode.lat)) {
replace.add(linkedNode);
}
}
if(replace.size() > 0) {
// we have a reason to replace!
// add n aswell since it aslo has to be combined and removed
replace.add(n);
// make a new node with the same position
Node replaceNode = new Node(n.lon, n.lat);
// from the ones we are going to combine we check the links
// and link it to the new created node
// and from the new created node we link
// to the other links if it's not one of the nodes
// we combine
for(Node aNodeToReplace : replace) {
for(Node linkedNode : aNodeToReplace.links) {
// make sure we dont link to the one
if(replace.contains(linkedNode) == false) {
replaceNode.linkToNode(linkedNode);
linkedNode.linkToNode(replaceNode);
// make sure we remove the old link
// to one we replaced
linkedNode.links.remove(aNodeToReplace);
}
}
remove.add(aNodeToReplace);
}
// add it to the ArrayList so we can add it to nodes later
newNodes.add(replaceNode);
}
}
// remove the ones where we made a new node for
for(Node n : remove) {
nodes.remove(n);
}
// add the new ones
for(Node n : newNodes) {
nodes.add(n);
}
}

Top Reply