package carte;

import ville.Ville;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;

public class GrapheGeometrique implements TableInterface<Arc>{
  private Map<Ville, Collection<Arc>> table;
  public GrapheGeometrique() {
    table = new LinkedHashMap<Ville, Collection<Arc>>();
  }
  public boolean contient(Ville v) {
    return table.containsKey(v);
  }
  public int taille() {
    return table.size();
  }
  public Collection<Ville> sommets() {
    return table.keySet();
  }
  public void ajouterVille(Ville v) {
      if (! contient(v))
	  table.put(v, new LinkedList<Arc>());
  }
  public void ajouterVoisin(Ville v, Arc arc) {
    Collection<Arc> c = table.get(v);
    if (c == null)
      throw new IllegalArgumentException("Ville inconnue");
    c.add(arc);
  }
  public Collection<Arc> voisins(Ville s){
      Collection<Arc> c = table.get(s);
      if (c == null)
	  throw new IllegalArgumentException("Ville inconnue");
      return c;
  }

  public void euclidien(double distEssence) {
    for (Ville s : sommets())
      for (Ville t : sommets())
        if (!s.equals(t) && s.distance(t) < distEssence)
	    ajouterVoisin(s,new Arc(s,t,0));
  }

  Arc premierArc(Collection<Arc> c) {
    for (Arc a:c)
      return a;
    return null;
  }

  public Ville terminus(Ville s) {
    Ville terminus = s;
    while (premierArc(voisins(terminus))!=null) 
      terminus=premierArc(voisins(terminus)).destination;
	// compression du chemin pour derniere question
    	while (!s.equals(terminus)) {
	    table.get(s).clear();
	    ajouterVoisin(s, new Arc(s, terminus, 2));
	    s=premierArc(voisins(s)).destination;
	}
    	// fin du code pour derniere question
    return terminus;
  }

  public void fusion(Ville s,Ville t) {
    Ville terminuss = terminus(s);
    Ville terminust = terminus(t);
    if (!terminuss.equals(terminust))
	ajouterVoisin(terminuss,new Arc(terminuss, terminust, 2));
  }

  public GrapheGeometrique composantesConnexes() {
    GrapheGeometrique nouveau = new GrapheGeometrique();
    // on construit l'ensemble des sommets du nouveau graphe
    for (Ville s : sommets())
      nouveau.ajouterVille(s);
    // on fusionne les composantes du nouveau graphe
    for (Ville s : sommets())
      for (Arc a : voisins(s))
        nouveau.fusion(s, a.destination);
    return nouveau;
  }

  public void colorieComposantesConnexes() {
    // on calcule d'abord les composantes connexes
    GrapheGeometrique cc = composantesConnexes();
    // on associe ensuite une couleur a chaque terminus
    HashMap<Ville,Integer> couleurs = new HashMap<Ville,Integer>();
    int coul = 0;
    for (Ville s : sommets()) {
      Ville p = cc.terminus(s);
      if (couleurs.get(p) == null)
        couleurs.put(p, coul++);
    }
    // enfin, on colorie les arcs du graphe initial
    for (Ville s : sommets()) {
      int couleur = couleurs.get(cc.terminus(s));
      for (Arc a : voisins(s))
        a.couleur=couleur;
    }
  }

}