Sorted sets and comparators
- by Jack
Hello, I'm working with a TreeSetthat is meant to store pathfind locations used during the execution of a A* algorithm.
Basically until there are "open" elements (still to be exhaustively visited) the neighbours of every open element are taken into consideration and added to a SortedSetthat keeps them ordered by their cost and heuristic cost. This means that I have a class like:
public class PathTileInfo implements Comparable<PathTileInfo>
{
int cost;
int hCost;
final int x, y;
@Override
public int compareTo(PathTileInfo t2) {
int c = cost + hCost;
int c2 = t2.cost + t2.hCost;
int costComp = c < c2 ? -1 : (c > c2 ? 1: 0);
return costComp != 0 ? costComp : (x < t2.x || y < t2.y ? -1 : (x > t2.x || y > t2.y ? 1 : 0));
}
@Override
public boolean equals(Object o2) {
if (o2 instanceof PathTileInfo) {
PathTileInfo i = (PathTileInfo)o2;
return i.cost + i.hCost == cost + hCost && x == i.x && y == i.y;
}
return false;
}
}
In this way first the total cost is considered, then, since a total ordering is needed (consistency with equals) a ordering according to the x,y coordinate is taken into account.
This should work but simply it doesn't, if I iterate over the TreeSet during the algorithm execution like in
for (PathTileInfo t : openSet)
System.out.print("("+t.x+","+t.y+","+(t.cost+t.hCost)+") ");
I get results in which the right ordering is not kept, eg:
(7,7,6) (7,6,7) (6,8,6) (6,6,7) (5,8,7) (5,7,7) (6,7,6) (6,6,7) (6,5,7) (5,7,7) (5,5,8) (4,7,7) (4,6,8) (4,5,8)
is there something subtle I am missing?
Thanks!
