/*******************************************************************************
* David.Pichardie@inria.fr, Copyright (C) 2011. All rights reserved. *
*******************************************************************************/
package org.javascool.proglets.gogleMaps;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import org.javascool.macros.Macros;
class GogleMapCalculChemins {
private static int distance(GogleMapPanel g, String ville1, String ville2) {
if(g.arcs.get(ville1).contains(ville2)) {
Macros.assertion(g.latitudes.containsKey(ville1), ville1 + " n'est pas une ville connue");
Macros.assertion(g.latitudes.containsKey(ville2), ville2 + " n'est pas une ville connue");
return g.distanceEuclidienne(g.longitudes.get(ville1), g.latitudes.get(ville1),
g.longitudes.get(ville2), g.latitudes.get(ville2));
} else {
return Integer.MAX_VALUE;
}
}
private static String PlusProche(List<String> groupe, Map<String, Integer> distMap) {
String res = null;
int distMin = Integer.MAX_VALUE;
for(String ville : groupe) {
int distance = distMap.get(ville);
if(distance < distMin) {
distMin = distance;
res = ville;
}
}
return res;
}
private static void MiseAjourDistance(GogleMapPanel g, String ville0, Map<String, Integer> distMap, Map<String, String> pred) {
int distance_ville0 = distMap.get(ville0);
for(String ville : g.arcs.get(ville0)) {
int nouvelle_distance = distance_ville0 + distance(g, ville0, ville);
if(nouvelle_distance < distMap.get(ville)) {
distMap.put(ville, nouvelle_distance);
pred.put(ville, ville0);
}
}
}
static List<String> plusCourtChemin(GogleMapPanel g, String depart, String arrivee) {
Map<String, Integer> distanceAuDepart = new HashMap<String, Integer>();
List<String> aTraite = new ArrayList<String>(g.latitudes.keySet());
Map<String, String> predecesseur = new HashMap<String, String>();
int nb_ville = aTraite.size();
for(String ville : aTraite) {
if(ville.equals(depart)) {
distanceAuDepart.put(ville, 0);
} else if(g.arcs.get(ville).contains(depart)) {
distanceAuDepart.put(ville, distance(g, ville, depart));
predecesseur.put(ville, depart);
} else {
distanceAuDepart.put(ville, Integer.MAX_VALUE);
}
}
aTraite.remove(depart);
// System.out.println("dist = "+distanceAuDepart);
for(int i = 1; i < nb_ville; i++) {
String prochain = PlusProche(aTraite, distanceAuDepart);
MiseAjourDistance(g, prochain, distanceAuDepart, predecesseur);
aTraite.remove(prochain);
// System.out.println("prochain = "+prochain+" dist = "+distanceAuDepart);
}
// construction du plus court chemin
List<String> chemin = new ArrayList<String>();
String finDuChemin = arrivee;
while(!finDuChemin.equals(depart)) {
Macros.sleep(0);
chemin.add(0, finDuChemin);
finDuChemin = predecesseur.get(finDuChemin);
}
chemin.add(0, depart);
return chemin;
}
}