package puzzle;

import java.awt.Color;
import java.awt.Graphics;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import graphics.DrawingPanel;

/**
 * Cette classe implémente la résolution récursive d'un puzzle coulissant NxN
 * en utilisant une recherche arborescente en largeur d'abord.
 *
 * @author François Schumacker
 *
 */
public class PuzzleSolve {

    private static final int TAILLE_PUZZLE = 3;
    private static final int TAILLE_CASE = 50; // taille pour l'affichage
    private static final int DELAI_AFFICHAGE = 500; // en millisecondes

    /**
     * Cette méthode illustre la résolution d'un puzzle NxN
     *
     * @param args
     */
    public static void main(String[] args) {
        // Création du puzzle
        Puzzle puzzle = new Puzzle(TAILLE_PUZZLE);
        String etatInitial = puzzle.obtenirEtatCourant();

        // Création et intialisation du dictionnaire des états atteints
        // => <etat_courant, etat_prédécesseur>
        Map<String, String> etatsAtteints = new HashMap<>();
        etatsAtteints.put(etatInitial, null);

        // Création de la fenêtre d'affichage
        DrawingPanel panel = new DrawingPanel(TAILLE_PUZZLE * TAILLE_CASE + 1, TAILLE_PUZZLE * TAILLE_CASE + 1);
        panel.setTitle("Puzzle " + TAILLE_PUZZLE + "x" + TAILLE_PUZZLE);
        afficherPuzzle(panel, etatInitial);

        // Recherche d'une solution pour le puzzle
        int nbDeplacements = 0;
        if (!puzzle.estResolu()) { // Pas la peine d'effectuer une recherche !
            // On démarre avec le rang 0 qui contient uniquement l'état initial
            nbDeplacements = resoudrePuzzle(puzzle, 0, etatsAtteints.keySet(), etatsAtteints);
        }

//      /*
//       * Décommenter le morceau de code suivant pour pouvoir tester 'animerLaSolution()'
//       * sur un exemple si 'resoudrePuzzle()' ne fonctionne pas.
//       */
//      etatsAtteints.clear();
//      etatsAtteints.put("CABDGE@FH",null);
//      etatsAtteints.put("CABDGEF@H","CABDGE@FH");
//      etatsAtteints.put("CABD@EFGH","CABDGEF@H");
//      etatsAtteints.put("CAB@DEFGH","CABD@EFGH");
//      etatsAtteints.put("@ABCDEFGH","CAB@DEFGH");
//      etatsAtteints.put("CABG@EDFH","CAB@GEDFH");
//      etatsAtteints.put("CAB@GEDFH","CABDGE@FH");
//      etatsAtteints.put("CABDGEFH@","CABDGEF@H");
//      puzzle.definirEtatCourant("@ABCDEFGH");
//      afficherPuzzle(panel, "CABDGE@FH");
//      nbDeplacements = 4;

        if (nbDeplacements > 0) {
            // Animation de la solution
            panel.setTitle(nbDeplacements + " déplacement(s)");
            System.out.println("Solution trouvée en " + nbDeplacements + " déplacement(s)!");
            animerLaSolution(panel, puzzle.obtenirEtatCourant(), etatsAtteints);
        } else {
            System.out.println("Pas de solution trouvée");
        }

    }

    /**
     * Recherche une solution au puzzle à partir des états d'un rang donné.
     *
     * @param puzzle
     *            Puzzle à résoudre
     * @param rang
     *            Numéro du rang courant (= distance par rapport à la racine de
     *            l'arbre)
     * @param rangCourant
     *            Ensemble des états appartenant au rang courant de l'arbre de
     *            recherche
     * @param etatsAtteints
     *            Dictionnaire des états déjà atteints par le processus de
     *            résolution
     * @return -1 si aucune solution n'a été trouvée, ou le numéro de rang de
     *         l'état final
     */
    public static int resoudrePuzzle(Puzzle puzzle, int rang, Set<String> rangCourant, Map<String,String> etatsAtteints) {
        Set<String> etatsSuivant = new HashSet<>();  //contient tous les rangs suivant;
        String etat = null;
        for(String etatCourant : rangCourant) {
            puzzle.definirEtatCourant(etatCourant);
            for(int i =0 ; i< Puzzle.NB_DIRECTIONS; i++) {
                if(puzzle.deplacerLeTrou(i)==true) {
                    etat = puzzle.obtenirEtatCourant();
                    if (!etatsAtteints.containsKey(etat)) {
                        etatsAtteints.put(etat, etatCourant);
                        if(puzzle.estResolu()) {
                            return rang+1;
                        }else {
                            etatsSuivant.add(etat);
                        }
                    }
                     puzzle.annulerDeplacerLeTrou(i);
                    }
            }

        }
        if(etatsSuivant.isEmpty()) {
            return -1;
        }
        return resoudrePuzzle(puzzle, rang +1 , etatsSuivant, etatsAtteints );


    }

    /**
     * Affiche les étapes succesives de la résolution du puzzle.
     * Cette méthode DOIT être programmée de manière récursive !!!
     *
     * @param panel
     *            Référence vers une fenêtre d'affichage
     * @param etatCourant
     *            L'état courant de la solution
     * @param etatsAtteints
     *            Dictionnaire des états atteints par le processus de résolution
     */
    private static void animerLaSolution(DrawingPanel panel, String etatCourant, Map<String,String> etatsAtteints) {

    }

    /**
     * Dessine le puzzle dans une fenêtre.
     *
     * @param panel
     *            Référence vers une fenêtre d'affichage
     * @param etat
     *            Etat du puzzle à représenter
     */
    public static void afficherPuzzle(DrawingPanel panel, String etat) {
        Graphics g = panel.getGraphics();
        char[] c = new char[1];

        // On efface le contenu de la fenêtre
        g.setColor(Color.BLACK);
        g.fillRect(0, 0, panel.getWidth(), panel.getHeight());

        // On dessine les cases du puzzle
        int index = 0;
        for (int ligne = 0; ligne < TAILLE_PUZZLE; ligne++) {
            for (int colonne = 0; colonne < TAILLE_PUZZLE; colonne++) {
                // On calcule la position du coin supérieur gauche
                int gauche = (colonne * TAILLE_CASE);
                int haut = (ligne * TAILLE_CASE);

                // On obtient le caractère à afficher
                c[0] = etat.charAt(index++);

                // On dessine la case si le caractère est différent de '@'
                if (c[0] != '@') {
                    g.setColor(c[0]%2==0?Color.WHITE:Color.RED);
                    g.fillRect(gauche + 1, haut + 1, TAILLE_CASE - 2, TAILLE_CASE - 2);
                    g.setColor(Color.BLACK);
                    g.drawChars(c, 0, 1, gauche + TAILLE_CASE / 3, haut + TAILLE_CASE * 2 / 3);
                }
            }
        }
        // Ralenti l'affichage pour laisser le temps de percevoir l'animation
        try {
            Thread.sleep(DELAI_AFFICHAGE);
        } catch (InterruptedException ex) {
        }

    }
}