/** Auteur : Samuele Giraudo.
 *  Creation : 01/09/10
 *  Modifications : 05/09/10 09/09/10 16/10/10 01/11/10 */

import java.io.FileWriter;
import java.io.FileReader;
import java.util.StringTokenizer;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Iterator;
import java.lang.Math;


public class GrapheLstAdj implements Graphe {

    // ATTRIBUTS.
    private int masque_espece;
    private int nombre_sommets;
    private List<List<DonneesSuccesseur>> successeurs;


    // CONSTRUCTEURS.

    public GrapheLstAdj(int masque_espece, int nombre_sommets) {
        assert masque_espece == 0x00 || masque_espece == 0x10 || masque_espece == 0x01 || masque_espece == 0x11;
        assert nombre_sommets >= 0;

        this.masque_espece = masque_espece;
        this.nombre_sommets = nombre_sommets;
        this.successeurs = new ArrayList<List<DonneesSuccesseur>>();
        for (int i = 0 ; i < nombre_sommets ; ++i)
            this.successeurs.add(new LinkedList<DonneesSuccesseur>());
    }

    public GrapheLstAdj(String nom_fichier_dot) {
        assert nom_fichier_dot != null;

        try{
            this.masque_espece = 0;
            this.nombre_sommets = 0;
            List<Arc> liste_arcs = new LinkedList<Arc>();
            FileReader fichier_dot = new FileReader(nom_fichier_dot);
            char[] tab = new char[32768];
            fichier_dot.read(tab);
            String contenu = new String(tab);
            if (contenu.charAt(0) == 'd')
                this.masque_espece |= Graphe.ORIENTE;
            StringTokenizer tk = new StringTokenizer(contenu, " \b\t\r\n{}\"abcdefghijklmnopqrstuvwxyz->=[]", false);
            while (tk.hasMoreTokens()) {
                try {
                    boolean termine = false;
                    double[] valeurs = new double[3];
                    int nb_val = 0;
                    while (!termine && nb_val <= 2) {
                        String t = tk.nextToken();
                        if (t.charAt(0) == ';')
                            termine = true;
                        else if (t.charAt(t.length() - 1) == ';') {
                            valeurs[nb_val] = Double.parseDouble(t.substring(0, t.length() - 1));
                            termine = true;
                        }
                        else
                            valeurs[nb_val] = Double.parseDouble(t.substring(0, t.length()));
                        ++nb_val;
                    }
                    if (nb_val == 1)
                        this.nombre_sommets = Math.max(this.nombre_sommets, (int) valeurs[0] + 1);
                    else if (nb_val == 2) {
                        Sommet s1 = new Sommet((int) valeurs[0]);
                        Sommet s2 = new Sommet((int) valeurs[1]);
                        liste_arcs.add(new Arc(this.masque_espece, s1, s2, 0));
                        this.nombre_sommets = Math.max(this.nombre_sommets, s1.cle() + 1);
                        this.nombre_sommets = Math.max(this.nombre_sommets, s2.cle() + 1);
                    }
                    else if (nb_val == 3) {
                        this.masque_espece |= Graphe.PONDERE;
                        Sommet s1 = new Sommet((int) valeurs[0]);
                        Sommet s2 = new Sommet((int) valeurs[1]);
                        liste_arcs.add(new Arc(this.masque_espece | Arc.PONDERE, s1, s2, valeurs[2]));
                        this.nombre_sommets = Math.max(this.nombre_sommets, s1.cle() + 1);
                        this.nombre_sommets = Math.max(this.nombre_sommets, s2.cle() + 1);
                    }
                }
                catch (NumberFormatException nfe) {
                    break;
                }
            }
            this.successeurs = new ArrayList<List<DonneesSuccesseur>>();
            for (int i = 0 ; i < nombre_sommets ; ++i)
                this.successeurs.add(new LinkedList<DonneesSuccesseur>());
            Iterator it = liste_arcs.iterator();
            while (it.hasNext())
                this.ajouterArc((Arc) it.next());
        }
        catch (Exception ex){
            System.out.println(ex.toString());
        }
    }


    // METHODES.

    public int masqueEspece() {
        return this.masque_espece;
    }

    public boolean estOriente() {
        return (this.masque_espece & Graphe.ORIENTE) != 0;
    }

    public boolean estPondere() {
        return (this.masque_espece & Graphe.PONDERE) != 0;
    }

    public int nombreSommets() {
        return this.nombre_sommets;
    }

    public int nombreArcs() {
        int nb = 0;
        for (int i = 0 ; i < this.nombreSommets() ; ++i)
            nb += this.successeurs.get(i).size();
        if (this.estOriente())
            return nb;
        else
            return nb / 2;
    }

    public boolean existeArc(Arc a) {
        assert a != null;
        assert a.masqueEspece() == this.masqueEspece();
        assert a.depart().cle() < this.nombreSommets();
        assert a.arrivee().cle() < this.nombreSommets();

        return this.successeurs.get(a.depart().cle()).contains(new DonneesSuccesseur(a.arrivee(), a.poids()));
    }

    public void ajouterArc(Arc a) {
        assert a != null;
        assert a.masqueEspece() == this.masqueEspece();
        assert a.depart().cle() < this.nombreSommets();
        assert a.arrivee().cle() < this.nombreSommets();

        if (!this.existeArc(a)) {
            this.successeurs.get(a.depart().cle()).add(new DonneesSuccesseur(a.arrivee(), a.poids()));
            if (!this.estOriente())
                this.successeurs.get(a.arrivee().cle()).add(new DonneesSuccesseur(a.depart(), a.poids()));
        }
    }

    public void supprimerArc(Arc a) {
        assert a != null;
        assert a.masqueEspece() == this.masqueEspece();
        assert a.depart().cle() < this.nombreSommets();
        assert a.arrivee().cle() < this.nombreSommets();

        this.successeurs.get(a.depart().cle()).remove(new DonneesSuccesseur(a.arrivee(), a.poids()));
        if (!this.estOriente())
            this.successeurs.get(a.arrivee().cle()).remove(new DonneesSuccesseur(a.depart(), a.poids()));
    }

    public String toString() {
        String res = "";
        if (this.estOriente())
            res += "di";
        res += "graph G {\n";
        for (int i = 0 ; i < this.nombre_sommets ; ++i)
            res += "    " + i + ";\n";
        for (int i = 0 ; i < this.nombre_sommets ; ++i) {
            List liste = this.successeurs.get(i);
            for (int j = 0 ; j < liste.size() ; ++j) {
                DonneesSuccesseur ds = (DonneesSuccesseur) liste.get(j);
                if (this.estOriente())
                    res += "    " + i + " -> " + ds.sommet().cle();
                else {
                    if (i < ds.sommet().cle())
                        res += "    " + i + " -- " + ds.sommet().cle();
                }
                if (this.estPondere())
                    if (this.estOriente() || i < ds.sommet().cle())
                        res += " [label=\"" + ds.poids() + "\"]";
                if (this.estOriente() || i < ds.sommet().cle())
                    res += ";\n";
            }
        }
        res += "}\n";
        return res;
    }

    public void afficher() {
        System.out.println(this.toString());
    }

    public void versImage(String nom_fichier) {
        assert nom_fichier != null;
        assert !nom_fichier.equals("");

        try {
            FileWriter fichier_dot = new FileWriter(nom_fichier + ".dot");
            fichier_dot.write(this.toString());
            fichier_dot.flush();
            Process p = Runtime.getRuntime().exec("dot " + nom_fichier + ".dot -Tpng -o " + nom_fichier + ".png");
            p.waitFor();
        }
        catch(Exception ex) {
            System.out.println("Erreur d'execution de dot");
        }
    }

    /**
     *******************************************************************
     * Ajout relatif a la Fiche 2 : Algorithme d'Euler.
     *******************************************************************
     */

    /**
     * Retourne le nombre de sommets de degre impair. (Fiche 2, ex 1.1).
     */
    public int nombreSommetsDegreImpair() {
        assert !this.estOriente();

        int nb = 0;
        for (int i = 0 ; i < this.nombreSommets() ; ++i)
            if (this.successeurs.get(i).size() % 2 == 1)
                ++nb;
        return nb;
    }

    /**
     * Retourne `true` ssi le graphe admet une chaine eulerienne (Fiche 2, ex 1.2).
     */
    public boolean admetChaineEulerienne() {
        assert !this.estOriente();

        int nb = this.nombreSommetsDegreImpair();
        return nb == 0 || nb == 2;
    }

    /**
     * Retourne une chaine entre les sommets x et y d'un graphe
     * et supprime les aretes empruntees (Fiche 2, ex 2.1).
     */
    public List<Sommet> supprimerChaine(Sommet x, Sommet y) {
        assert !this.estOriente();
        assert x != null;
        assert x.cle() <= this.nombreSommets();
        assert y != null;
        assert y.cle() <= this.nombreSommets();

        List<Sommet> liste = new ArrayList<Sommet>();
        liste.add(x);
        Sommet z = x;
        Sommet zz = null;
        do {
            zz = this.successeurs.get(z.cle()).get(0).sommet();
            liste.add(zz);
            this.supprimerArc(new Arc(0, z, zz, 0));
            z = zz;
        } while (!zz.equals(y));
        return liste;
    }

    /**
     * Retourne un cycle partant en x d'un graphe dont tous
     * les sommets sont de degres superieurs a 2 et supprime les aretes
     * empruntees (Fiche 2, ex 2.2).
     */
    public List<Sommet> supprimerCycle(Sommet x) {
        assert !this.estOriente();
        assert x != null;
        assert x.cle() <= this.nombreSommets();

        return this.supprimerChaine(x, x);
    }

    /**
     * Retourne un cycle eulerien partant de x dans un graphe dont tous
     * les sommets sont de degres superieurs a 2 et supprime les aretes
     * empruntees.
     */
    public List<Sommet> cycleEulerien(Sommet x) {
        assert !this.estOriente();
        assert x != null;
        assert x.cle() <= this.nombreSommets();

        List<Sommet> res = new ArrayList<Sommet>();
        if (this.successeurs.get(x.cle()).size() == 0) {
            res.add(x);
            return res;
        }
        else {
            List<Sommet> cycle = this.supprimerCycle(x);
            Iterator it = cycle.iterator();
            while (it.hasNext()) {
                List<Sommet> petit_cycle = this.cycleEulerien((Sommet) it.next());
                res.addAll(petit_cycle);
            }
            return res;
        }
    }

    /**
     * Retourne une chaine eulerienne partant d'un sommet de degre impair
     * et arrivant dans un autre sommet de degre impair. Le graphe est
     * connexe et possede exactement 2 sommets de degres impairs.
     */
    public List<Sommet> chaineEulerienne() {
        assert !this.estOriente();

        List<Sommet> res = new ArrayList<Sommet>();

        /** Recheche des deux sommets de degre impair. */
        Sommet x = null, y = null;
        for (int i = 0 ; i < this.nombreSommets() ; ++i) {
            if (this.successeurs.get(i).size() % 2 != 0) {
                if (x == null)
                    x = new Sommet(i);
                else
                    y = new Sommet(i);
            }
        }

        List<Sommet> chaine = this.supprimerChaine(x, y);
        Iterator it = chaine.iterator();
        while (it.hasNext()) {
            List<Sommet> petit_cycle = this.cycleEulerien((Sommet) it.next());
            res.addAll(petit_cycle);
        }
        return res;
    }

    /**
     * Retourne une liste de sommets qui modelise un cycle ou chaine eulerienne.
     * (Fiche 2, ex 2.3).
     */
    public List<Sommet> chaineCyleEulerien() {
        switch (nombreSommetsDegreImpair()) {
        case 0 :
            System.out.println("Le graphe possede un cycle eulerien.");
            return this.cycleEulerien(new Sommet(0));
        case 2 :
            System.out.println("Le graphe possede une chaine eulerienne.");
            return this.chaineEulerienne();
        default :
            System.out.println("Le graphe ne possede pas de chaine eulerienne.");
            return new ArrayList<Sommet>();
        }
    }

    /**
     *******************************************************************
     * Fin ajout relatif a la Fiche 2 : Algorithme d'Euler.
     *******************************************************************
     */


    private class DonneesSuccesseur {

        private Sommet sommet;
        private double poids;

        public DonneesSuccesseur(Sommet sommet, double poids) {
            assert poids >= 0;

            this.sommet = sommet;
            this.poids = poids;
        }

        public Sommet sommet() {
            return this.sommet;
        }

        public double poids() {
            return this.poids;
        }

        public boolean equals(Object obj) {
            assert obj != null;

            if (!(obj instanceof DonneesSuccesseur))
                return false;
            DonneesSuccesseur ds = (DonneesSuccesseur) obj;
            return this.poids() == ds.poids() && this.sommet().equals(ds.sommet());
        }
    }

}