Sorted sets and comparators

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(开发者_Python百科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!

---

Please ensure NOT to change 'Comparable' value of element after adding to the TreeSet. If you change the value after adding to the TreeSet, TreeSet cannot maintain the new order.

I think your PathTileInfo is correct, although equals() override is not necessary in this case.

---

TreeSet by default orders the elements you add using natural ordering and this is what is happening in your case. Are you telling TreeSet to use your custom comparator when creating it?