Metodi:
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
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
}
Dovrai tenere traccia delle distanze in entrambe le direzioni, non solo una. Vale a dire, Abernathy a Gruver, e poi Gruver avrà anche la distanza di Abernathy.
L'implementazione più semplice sarebbe una matrice bidimensionale se i dati sono noti al momento della compilazione. Quindi potresti semplicemente usare una costruzione intelligente di ciò che un oggetto City deve determinare quale indice usare. Questo renderebbe piuttosto difficile estendere però.
Un altro modo per farlo è definire un tipo di classe di qualcosa come Distance che contiene due punti finali che sono oggetti City . L'idea sarebbe che l'ordine degli oggetti City non dovrebbe avere importanza e che quando li memorizzi ti assicuri di non contare il doppio.
La struttura dei dati potrebbe quindi utilizzare qualsiasi combinazione di ArrayList s o Hashtable s indicizzati da City oggetti. Il mio metodo preferito sarebbe probabilmente quello di mantenere solo un Arraylist<Distance> oggetti e definire metodi di supporto per determinare se l'indice dato è rilevante per la domanda in questione. Ovviamente questo è potenzialmente lento, ma su insiemi di dati di piccole dimensioni è abbastanza buono.
Per i metodi
Se c'è una distanza tra ogni città, e ogni città è conosciuta in anticipo, userei un array bidimensionale. Per semplicità e velocità, userei il tutto, anche se stai memorizzando tutte le distanze due volte. Quindi vorrai un array 1 dimensionale (ArrayList potrebbe funzionare meglio) per collegare gli indici nella tabella delle distanze agli oggetti City reali (che nel caso più semplice sarebbero solo i loro nomi come stringhe e il loro numero di indice della tabella). Quindi aggiungi città a una mappa digitata sui nomi per ottenere i loro indici. Se conosci il numero di città in anticipo e anche se non lo fai, probabilmente una HashMap è ciò che desideri. Ora, dato un nome, puoi trovare una riga / colonna nella tabella, scansionarla per i numeri che ti piacciono, trasformare l'indice di colonna / riga desiderato in un oggetto City e restituire quello che vuoi da quel nome (nome, per esempio).
Se la stragrande maggioranza delle coppie di città non ha distanze, salta l'array 2D e crea una classe Connection che faccia riferimento a due città e contenga una distanza. Quindi la classe City dovrebbe contenere un elenco di oggetti Connection e si dispone di un grafico (come nella teoria dei grafi). Ci sono molti modi per lavorare con loro.
Che dire di questo:
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;
}
}
Quindi inizializza tutte le città (ad esempio, New York, Boston, ecc.) quindi imposta la città adiacente a New York (per esempio, Boston è collegata a NY con la distanza '300'). Quindi ora inizializza 'AdjCity' con 'targetCity' (Boston) e la distanza è 200. E aggiungi questo alla lista di oggetti AdjCity.
Ora puoi metterlo in una collezione e da qui penso che puoi procedere se ha senso per te.
Grazie
Questo sarà lento.
Sembra che l'operazione add richiederà eventualmente O(N) , dove N è il numero di città esistenti nella raccolta. Questo sarà più lento e lento con l'aggiunta di più città.
Non riesco a pensare a un modo pigro per valutare la distanza. Mi sembra che le distanze all-pair debbano essere calcolate in anticipo. Forse qualcuno può offrire suggerimenti migliori.
Commento. SortedMap Sembra sbagliato. Non consente chiavi duplicate (due doubles con lo stesso valore). Tuttavia, le possibilità di due coppie di città con la stessa distanza sembra remota per 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
}
Leggi altre domande sui tag java data-structures