package parcours;

import java.util.Collection;

import grapheX.Arc;

public class Parcours {

  // exercice 1

  public static void dfsRec(GrapheEdition g, Mot u,
      Etiquettes<Mot, Etat> rencontres) {
    rencontres.setValue(u, Etat.EN_COURS);
    System.out.print(u + " ");
    for (Arc<Mot> a : g.voisins(u)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT)
        dfsRec(g, v, rencontres);
    }
    // rencontres.setValue(u, Etat.TRAITE);
    // le marquage postfixe n'est pas nécessaire pour contrôler une simple dfs
  }

  // exercice 2

  public static void arbreCouvrantDFS(GrapheEdition g, Mot pere,
      Etiquettes<Mot, Etat> rencontres, Etiquettes<Mot, Arc<Mot>> arcPeres) {
    rencontres.setValue(pere, Etat.EN_COURS);
    for (Arc<Mot> a : g.voisins(pere)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT) {
        arcPeres.setValue(v, a);
        arbreCouvrantDFS(g, v, rencontres, arcPeres);
      }
    }
    // rencontres.setValue(pere, Etat.TRAITE); // facultatif
  }

  public static void foretDFS(GrapheEdition g, Etiquettes<Mot, Arc<Mot>> arcPere) {
    Etiquettes<Mot, Etat> rencontres = new Etiquettes<Mot, Etat>(
        Etat.PAS_ATTEINT);
    for (Mot u : g.sommets())
      if (rencontres.getValue(u) == Etat.PAS_ATTEINT)
        arbreCouvrantDFS(g, u, rencontres, arcPere);
  }

  public static void colorierArc(Etiquettes<Arc<Mot>, Integer> couleurArcs,
      Arc<Mot> a, int c) {
    couleurArcs.setValue(a, c);
    couleurArcs.setValue(new Arc<Mot>(a.destination(), a.origine()), c);
  }

  public static void colorierChemin(GrapheEdition g, Mot v, int c,
      Etiquettes<Mot, Arc<Mot>> arcPeres, Etiquettes<Mot, Integer> couleurMots,
      Etiquettes<Arc<Mot>, Integer> couleurArcs) {
    Arc<Mot> a = arcPeres.getValue(v);
    if (a != null) {
      colorierArc(couleurArcs, a, c);
      colorierChemin(g, a.origine(), c, arcPeres, couleurMots, couleurArcs);
    }
    couleurMots.setValue(v, c);
  }

  // exercice 3

  public static int dfsNum(GrapheEdition g, Mot u, int num,
      Etiquettes<Mot, Etat> rencontres, Etiquettes<Mot, Integer> numeros) {
    rencontres.setValue(u, Etat.EN_COURS);
    ++num;
    System.out.print(u + ":" + num + " ");
    numeros.setValue(u, num);
    for (Arc<Mot> a : g.voisins(u)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT)
        num = dfsNum(g, v, num, rencontres, numeros);
    }
    // rencontres.setValue(u, Etat.TRAITE); // facultatif
    return num;
  }

  public static Etiquettes<Mot, Integer> dfsNum(GrapheEdition g) {
    Etiquettes<Mot, Integer> m = new Etiquettes<Mot, Integer>(0);
    Etiquettes<Mot, Etat> rencontres = new Etiquettes<Mot, Etat>(
        Etat.PAS_ATTEINT);
    int num = 0;
    for (Mot u : g.sommets())
      if (rencontres.getValue(u) == Etat.PAS_ATTEINT) {
        num = dfsNum(g, u, num, rencontres, m);
        System.out.println();
      }
    return m;
  }

  // exercice 4

  public static void dfsDepths(GrapheEdition g, Mot pere, int profondeur,
      Etiquettes<Mot, Etat> rencontres, Etiquettes<Mot, Integer> profMots,
      Etiquettes<Arc<Mot>, Integer> profArcs) {
    rencontres.setValue(pere, Etat.EN_COURS);
    profMots.setValue(pere, profondeur);
    profondeur++;
    for (Arc<Mot> a : g.voisins(pere)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT) {
        profArcs.setValue(a, profondeur);
        dfsDepths(g, v, profondeur, rencontres, profMots, profArcs);
      }
    }
    // rencontres.setValue(pere, Etat.TRAITE); // facultatif
  }

  public static void foretDepths(GrapheEdition g,
      Etiquettes<Mot, Integer> profMot, Etiquettes<Arc<Mot>, Integer> profArc) {
    Etiquettes<Mot, Etat> rencontres = new Etiquettes<Mot, Etat>(
        Etat.PAS_ATTEINT);
    for (Mot u : g.sommets())
      if (rencontres.getValue(u) == Etat.PAS_ATTEINT)
        dfsDepths(g, u, 0, rencontres, profMot, profArc);

  }

  // exercice 5

  static boolean estPere(Etiquettes<Mot, Arc<Mot>> arcPere, Mot u, Mot v) {
    Arc<Mot> pere = arcPere.getValue(u);
    return pere != null && pere.origine().equals(v);
  }

  // Attention, la recherche de cycle doit normalement distinguer EN_COURS de
  // TRAITE et donc utiliser 3 états, mais on peut montrer que pour un graphe
  // non orienté, on ne peut pas arriver sur un sommet qui serait marqué
  // TRAITE sans avoir déjà détecté un cycle.
  // Le test sur estPere permet d'ignorer les cycles triviaux.
  public static Arc<Mot> dfsCycle(GrapheEdition g, Mot u,
      Etiquettes<Mot, Arc<Mot>> arcPeres, Etiquettes<Mot, Etat> rencontres) {
    rencontres.setValue(u, Etat.EN_COURS);
    for (Arc<Mot> a : g.voisins(u)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT) {
        arcPeres.setValue(v, a);
        // return dfsCycle(g, v, arcPeres, rencontres); // FAUX 
        // il faut tester la valeur de retour
        Arc<Mot> aa = dfsCycle(g, v, arcPeres, rencontres);
        if (aa != null) {
          System.out.print(" <- " + v);
          return aa;
        }
        // si aa==null, on continue sur les autres voisins
      } else if (/* rencontres.getValue(v) == Etat.EN_COURS && */ !estPere(arcPeres, u, v)) {
        System.out.print(v);
        return a;
      }
    }
    return null;
  }

  // exercice 6

  // avec une astuce
  public static void colorierCycle(Arc<Mot> a, int c1, int c2,
      Etiquettes<Mot, Arc<Mot>> arcPeres, Etiquettes<Mot, Integer> couleurMots,
      Etiquettes<Arc<Mot>, Integer> couleurArcs) {
    Mot debut = a.destination();
    do {
      couleurArcs.setValue(a, c1);
      Mot m = a.origine();
      if (m.equals(debut))
        c1 = c2; // astuce
      couleurMots.setValue(m, c1);
      a = arcPeres.getValue(m);
    } while (a != null);
  }

  // exercice 7

  public static final int ABSENT = -1;

  // rem. sommets n'est pas utile
  static public Etiquettes<Arc<Mot>, Typologie> typologie(GrapheEdition g,
      Collection<Mot> sommets) {
    Etiquettes<Arc<Mot>, Typologie> typos = new Etiquettes<Arc<Mot>, Typologie>(
        Typologie.INCONNUE);
    Etiquettes<Arc<Mot>, Integer> depthsArcs = new Etiquettes<Arc<Mot>, Integer>(
        ABSENT);
    Etiquettes<Mot, Integer> depthsMots = new Etiquettes<Mot, Integer>(ABSENT);
    foretDepths(g, depthsMots, depthsArcs);
    // ...
    for (Mot u : g.sommets())
      for (Arc<Mot> a : g.voisins(u))
        if (depthsArcs.getValue(a) != ABSENT)
          typos.setValue(a, Typologie.LIAISON);
        else {
          int p_o = depthsMots.getValue(a.origine());
          int p_d = depthsMots.getValue(a.destination());
          if (p_o < p_d - 1)
            typos.setValue(a, Typologie.AVANT);
          else if (p_o > p_d)
            typos.setValue(a, Typologie.ARRIERE);
          else
            typos.setValue(a, Typologie.TRANSVERSE);
        }
    return typos;
  }

  // exercice 8

  // Dans un graphe non orienté, on ne peut pas avoir d'arc (o,d) avec
  // p(o) = p(d). En effet, l'arc (d,o) existe aussi et
  // - soit on a visité o en premier et d est dans le sous-arbre dfs de racine
  //   o, donc p(o) < p(d),
  // - soit on a visité d en premier et, réciproquement, p(d) < p(o).
  //
  // De manière plus détaillée (ici on doit utiliser les 3 états) :
  //
  // Un arc de liaison (o,d) correspond à un arc de l'arbre dfs, par
  // définition d est encore dans l'état PAS_ATTEINT, (o,d) est l'arc père de d
  // et p(d) = p(o)+1,
  //
  // Un arc arrière (o,d) ferme un cycle découvert lors du parcours, d est
  // déjà dans l'état EN_COURS, ce qui est équivalent à p(o) > p(d) ;
  // - le sens "d EN_COURS" => p(o) > p(d) est trivial
  // - le sens p(o) > p(d) => "d EN_COURS" se montre par l'absurde, d ne peut
  // ni être dans l'état PAS_ATTEINT, (o,d) serait alors un arc de liaison,
  // ni être dans l'état TRAITE car "d TRAITE" => "o TRAITE" par l'arc (d,o).
  // Ce dernier point est spécifique au cas non orienté.
  //
  // Un arc avant (o,d) a pour destination un sommet d déjà marqué TRAITE dans
  // l'exploration d'une autre branche et le cas "d TRAITE" est équivalent à
  // p(o) < p(d) par la négation de tout ce qui précède et l'exclusion du
  // cas p(o) = p(d).
  // En particulier, (d,o) a été vu comme un arc arrière et d est dans le
  // sous-arbre dfs de racine o. Pour un graphe simple, on a même p(o) < p(d)-1.
  //
  public static void typologieRec(GrapheEdition g, Mot u,
      Etiquettes<Mot, Etat> rencontres, Etiquettes<Arc<Mot>, Typologie> typos) {
    rencontres.setValue(u, Etat.EN_COURS);
    for (Arc<Mot> a : g.voisins(u)) {
      Mot v = a.destination();
      if (rencontres.getValue(v) == Etat.PAS_ATTEINT) {
        typos.setValue(a, Typologie.LIAISON);
        typologieRec(g, v, rencontres, typos);
      } else if (rencontres.getValue(v) == Etat.EN_COURS) {
        typos.setValue(a, Typologie.ARRIERE);
      } else { // TRAITE
        typos.setValue(a, Typologie.AVANT);
      }
    }
    rencontres.setValue(u, Etat.TRAITE);
  }
}