What Java data structure/design pattern best models this object, considering it would perform these methods?

Question

Methods:

1.  getDistance(CityA,CityB) // Returns distance between two cities
2.  getCitiesInRadius(CityA,integer) // Returns cities within a given distance of another city
3.  getCitiesBeyondRadius(CityA,integer) //Returns cities beyond a given distance of another city
4.  getRemoteDestinations(integer) // Returns all city pairs greater than x distance of each other
5.  getLocalDestinations(integer) //Returns all city pairs within x distance of each other

Answer 1

public class Map {
    private Hashmap<String, City> cities;
    public Distance getDistance(CityA,CityB) // Returns distance between two cities
    public List<City> getCitiesInRadius(CityA, Distance) // Returns cities within a given distance of another city
    publi List<City> getCitiesBeyondRadius(CityA,Distance) //Returns cities beyond a given distance of another city
    public List<City> getRemoteDestinations(Distance) // Returns all city pairs greater than x distance of each other
    public List<City> getLocalDestinations(Distance) //Returns all city pairs within x distance of each other
 }

public class City {
    private String name;
    private HashMap<City, Distance> distanceTo;
    //getter/setters etc
}

You'll need to keep track of distances in both directions, not just one. Ie, Abernathy to Gruver, and then Gruver will also have Abernathy's distance.

Answer 2

The simplest implementation would be a two dimensional array if the data is known at compile time. Then you could just use some clever construction of what a City object is to figure out which index to use. This would make it pretty hard to extend though.

Another way to do it is to define a class type of something like Distance which contains two end points which are City objects. The idea would be that the order of the City objects shouldn't matter and that when storing them you make sure you're not double counting anything.

The data structure then could use any combinations of ArrayLists or Hashtables indexed by City objects . My preferred method would probably be to keep just an Arraylist<Distance> objects and define helper methods to determine if the given index is relevant to the question at hand. Of course this is potentially slow but on small data sets it's good enough.

For the ___Destinations methods it might be helpful to borrow a functional programming idea and make a method which returns a temporary list of distances with only the target city involved and then search again. But this is in no way necessary.

Answer 3

If there's a distance between every city, and every city is known in advance, I'd use a 2 dimensional array. For simplicity and speed, I'd use the whole thing, even though you're storing all the distances twice. Then you'll want a 1 dimensional array (ArrayList might work better) to link the indexes in your distance table to actual City objects (which in the simplest case would just be their names as Strings and their table index number). Then add cities to a Map keyed on names to get the their indexes. If you know the number of cities in advance, and even if you don't, a HashMap is probably what you want. Now, given a name, you can find a row/column in the table, scan it for numbers you like, turn desired column/row index into a City object, and return whatever you want from that (name, for instance).

If the vast majority of city pairs do not have distances, skip the 2D array, and create a Connection class that references two cities and contains a distance. Then the City class would contain a list of Connection objects, and you have a graph (as in graph theory). There's lots of ways to work with them.

Answer 4

What about this:

public class City{

   private String name;
   private List<AdjCities> adjCities;

   //getters and setters
}

public class AdjCity{
   private int distance;
   private City targetCity; 

   public void(int distance, City targetCity){
     this.distance= distance;
     this.city = city;
   }
}

So now initialize every city (say, NYC, Boston etc.) then set the adjacent city to NY (say, Boston is connected to NY with distance '300'). So now initialize 'AdjCity' with 'targetCity' (Boston) and distance is 200. And add this to the list of AdjCity objects.

Now you can put this in a collection and from here I think you can proceed if it makes any sense to you.

Thanks

Answer 5

This will be slow.

It seems add operation will eventually require O(N), where 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.

Remark. 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);
            distances.put(pair, distance);
            sortedByDistances.put(distance, pair);
        }
        cities.add(city);
    }

    // this is possibly very very slow, or very very fast...
    public static double getDistance(City origin, City destination)
    {
        Query q = new Query(
            origin.getCentroid().toString(),
            destination.getCentroid().toString(),
            "GreatCircle");
        // .. wait for query to finish
        return q.distance();
    }

    // implement your other methods here
}