This will be slow.
add operation will eventually require
N is number of existing cities in the collection. This will be slower and slower as more cities are added.
I can't think of a way to lazy-evaluate the distance. It seems to me all-pair distances must be calculated up front. Maybe someone can offer better suggestions.
SortedMap Seems wrong. It doesn't allow duplicate keys (two
doubles having same value). However, the chances of two pairs of cities with same distance seems remote to me ...
public class CityCollection
private List<City> cities;
// Cache distances when cities added, because expensive to calculate
private Map<Pair<City, City>, double> distances;
// sorted by pairwise distances
private SortedMap<double, Pair<City, City>> sortedByDistances;
public void add(City city)
if (cities.contains(city)) return;
for (City oldCity : cities)
Pair<City, City> pair = new Pair<City, City>(oldCity, city);
double distnace = getDistance(oldCity, city);
// this is possibly very very slow, or very very fast...
public static double getDistance(City origin, City destination)
Query q = new Query(
// .. wait for query to finish
// implement your other methods here