Сортированные наборы и компараторы - PullRequest
Новая
       20

Сортированные наборы и компараторы

2 голосов
/ 08 января 2011

Я работаю с TreeSet, предназначенным для хранения местоположений поиска пути, используемых во время выполнения алгоритма A *.

В основном, пока не появятся «открытые» элементы (которые еще предстоит исчерпывающе посетить)Соседи каждого открытого элемента учитываются и добавляются к SortedSet, который позволяет упорядочить их по их стоимости и эвристической стоимости.Это означает, что у меня есть класс, подобный: 

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;
  }
}

Таким образом, сначала учитывается общая стоимость, а затем, поскольку необходимо общее упорядочение (согласованность с равными), упорядочение по координате x, y

Это должно работать, но просто не работает, если во время выполнения алгоритма я перебираю TreeSet, как в 

for (PathTileInfo t : openSet)
  System.out.print("("+t.x+","+t.y+","+(t.cost+t.hCost)+") ");

Я получаю результаты, в которых правильное упорядочениене хранится, например:

(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)

Есть ли что-то тонкое, что мне не хватает?Спасибо!

Ответы [ 2 ]

1 голос
/ 08 января 2011

Убедитесь, что НЕ изменили 'Сопоставимое' значение элемента после добавления к TreeSet. Если вы измените значение после добавления к TreeSet, TreeSet не сможет поддерживать новый порядок.

Я думаю, что ваш PathTileInfo правильный, хотя в этом случае переопределение equals() не требуется.

0 голосов
/ 08 января 2011

TreeSet по умолчанию упорядочивает добавляемые элементы, используя естественное упорядочение, и это то, что происходит в вашем случае.Вы говорите TreeSet использовать ваш собственный компаратор при его создании?

...