Какая структуру выбрать для массива, где неважен порядок, а определяется только элементами?

Question

[Clean Coder]

Например, моделируем дорогу:

class Road {
City city1, city2;
}

Но тогда Road(Spb, Msk) и Road(Msk. Spb), моделирующих одну и ту же трассу, будут двумя разными объектами. Как тогда лучше быть?

Answer 1

[tsarevfs]

Есть несколько вариантов для хранения неориентированных графов.
1. Хранить любую из дорог, а при доступе к ним проверять наличие какой-то из 2
2. Хранить всегда только дорогу из города с меньшим номером в город с большим.
3. Хранить 2 дороги всегда.

В зависимости от задачи бывает удобнее использовать один из этих способов.

Answer 2

[antonwx]

Вам надо не создавать новый объект, а делать метод-селектор, который будет проверять существование дороги и если она существует - возвращать существующую, если нет - то создавать новую. В данном случае можно реализовать проверку так:

Set<Road> roads = new HashSet<Road>();
Road getRoad(c1, c2){
for(Road r:roads) if((r.city1.equals(c1) && r.city2.equals(c2)) || (r.city2.equals(c1) && r.city1.equals(c2))) return r;
Road r = new Road(c1, c2);
roads.add(r);
return r;
}

Если городов будет больше, имеет смысл использовать сеты вместо перечислений городов в отдельных переменных.
P.s. писал с мобильника, могут быть ошибки

Answer 3

[Алексей Черемисин]

Да хоть, если даже дорога проходит через 10 городов - используйте TreeSet().

SortedSet road1 = TreeSet<City>();
road1.add("Mos");
road1.add("Spb");

SortedSet road2 = TreeSet<City>();
road2.add("Spb");
road2.add("Mos");

assert road1.equals(road2);