package iad;

import iad.*;
import java.util.*;
import java.lang.Integer;

public class Kruskal {
	/**
	 *Atributs privés
	 */
	private Labyrinthe labyrinthe;
	private Vector vertex;
	private Vector tarjan; 
	private Random hasard;
	/**
	 *Constructeur
	 *param largeur et longueur du labyrinthe 
	 */
	 public Kruskal (int largeur, int longueur) {
	 	labyrinthe = new Labyrinthe(largeur, longueur);
	 	tarjan = new Vector(largeur*longueur);
	 	Vector initial = new Vector(largeur*longueur);
	 	for (int j=0; j<longueur; j++) {
	 		for (int i=0; i<largeur; i++) {
	 			Tarjan t = new Tarjan(labyrinthe.getCellule(i,j));
	 			tarjan.add(t);
	 			initial.add(labyrinthe.getCellule(i,j));
	 		}
	 	}
	 	melange(initial);
	 	
	 	// On initialise les bords
	 	init();
	}
	/**
	 *Initialisation, on ferme à clé les bords
	 */
	 public void init() {
	 	// Au sud
	 	int longueur = labyrinthe.getLongueur();
	 	int largeur = labyrinthe.getLargeur();
	 	for (int i=0; i<largeur-1; i++) {
	 		labyrinthe.getCellule(i, longueur-1).setEtat(3);
	 	}
	 	// A l'est
	 	for (int i=1; i<longueur-1; i++) {
	 		labyrinthe.getCellule(largeur-1, i).setEtat(12);
	 	}
	 	// Au sud-est
	 	labyrinthe.getCellule(largeur-1, longueur-1).setEtat(15);
	 	// Au nord-est
	 	labyrinthe.getCellule(largeur-1, 0).setEtat(4);
	}	 	
	/**
	 *Melange du vertex
	 *param vertex non mélangé
	 */
	public void melange(Vector initial) {
		int s = initial.size();
		vertex = new Vector(s);
		for (int i=0; i < s-1; i++) {
			int h = randomInt(s-i-1);
			vertex.addElement((Cellule)initial.elementAt(h));			
			initial.removeElementAt(h);
		}
		vertex.addElement((Cellule)initial.elementAt(0));
	}	
	/**
	 *Retourne un entier aléatoire compris entre 0 et n
	 *param entier n
	 */
	public int randomInt(int n) {
		hasard = new Random(Calendar.getInstance().getTimeInMillis());
		int r = (hasard.nextInt() % n);
		if (r < 0) {
			r = -r;
		}
		return r;
	}
	/** 
	 *Algorithme de Kruskal
	 */
	 public Labyrinthe algorithme() {	 
	 	
	 	while (vertex.size() != 0) {	 
	 					 		
	 		// On se place au hasard sur une cellule
	 		Cellule ctmp = (Cellule)(vertex.elementAt(0));
	 		int itmp = ctmp.getIdentificateur();
			int etat = ctmp.getEtat();
			
			// On supprime la cellule du vertex
			vertex.removeElement(ctmp);
			
			// On recherche l'ensemble de Tarjan associé à cette cellule
			Tarjan ttmp = null;
			for (int i=0; i<tarjan.size(); i++) {
				Tarjan temp = (Tarjan) tarjan.elementAt(i);
	 			if (temp.isPresent(ctmp)) {
	 				ttmp = temp;
	 			}
	 		}
	 		
	 		// Si on trouve une porte Est fermée
	 		if ((etat == 0 || etat == 1 || etat == 3) && (itmp%labyrinthe.getLargeur() < labyrinthe.getLargeur())) {
	 			Cellule est = labyrinthe.getCellule(itmp%labyrinthe.getLargeur() + 1, itmp/labyrinthe.getLargeur()); 
	 					
	 			// On compare les identificateurs
	 			if (ttmp.isPresent(est)) { 	 				
	 				// On ferme la porte à clé
	 				switch (etat) {
	 					case 0: ctmp.setEtat(12);
	 						break;	 						
	 					case 1: ctmp.setEtat(13);
	 						break;	 						
	 					case 3: ctmp.setEtat(15);
	 						break;
	 				}
	 			}
	 			else {	// On ouvre la porte commune ...
	 				
	 				switch (etat) {
	 					case 0: ctmp.setEtat(4);
	 						break;
	 					case 1: ctmp.setEtat(5);
	 						break;	 						
	 					case 3: ctmp.setEtat(7);
	 						break;
	 				}
	 				// puis on met à jour les identificateurs
	 				// On recherche l'ensemble comprenant est
	 				for (int i=0 ; i<tarjan.size(); i++) {
	 					
	 					Tarjan test  = (Tarjan) tarjan.elementAt(i);
	 					if (test.isPresent(est)) {
	 						
	 						// union
	 						if (! ttmp.comparaison(est)) { 
	 							ttmp.union(test);
	 							// suppression des deux ensembles de vertex
	 							tarjan.removeElement(test);	
	 						} 
	 					}
	 				}
	 			}
	 		}	
	 		etat = ctmp.getEtat(); 		
	 		// Si on trouve une porte Sud fermée
	 		if ((etat == 0 || etat == 4 || etat == 12) && (itmp/labyrinthe.getLargeur() < labyrinthe.getLongueur())){
	 			Cellule sud = labyrinthe.getCellule(itmp%labyrinthe.getLargeur(), itmp/labyrinthe.getLargeur() + 1); 
	 			// On compare les identificateurs
	 			if (ttmp.isPresent(sud)) { 	 				
	 				// On ferme la porte à clé
	 				switch (etat) {
	 					case 0:	ctmp.setEtat(3);
	 						break;
	 					case 4: ctmp.setEtat(7);
	 						break;
	 					case 12: ctmp.setEtat(15);
	 						break;	
	 				}	 				
	 			}	 			 			
	 			else {	// On ouvre la porte commune...
	 				switch (etat) {
	 					case 0:	ctmp.setEtat(1);
	 						break;
	 					case 4: ctmp.setEtat(5);
	 						break;
	 					case 12: ctmp.setEtat(13);
	 						break;
	 				}
	 				// puis on met à jour les identificateurs
	 				// On recherche l'ensemble comprenant sud
	 				for (int j=0 ; j<tarjan.size(); j++) {
	 					Tarjan tsud  = (Tarjan) tarjan.elementAt(j);
	 					if (tsud.isPresent(sud)) {
	 						
	 						// union
	 						if (!ttmp.comparaison(sud)) {
	 							ttmp.union(tsud);
	 							// suppression des deux ensembles de vertex
	 							tarjan.removeElement(tsud);
	 						}								
	 					}
	 				}
	 			}
	 	 	}
	 	 }
	 	 return this.labyrinthe;
	}
	/**
	 *Fonction pricipale de génération de labyrinthe
	 *param largeur et hauteur, par défaut 20*10
	 */
	public static void main(String[] args) {
		int x=10;
		int y=10;
		/**
		 *Lecture des paramêtres entrés
		 */
		if (args.length > 0) {
			try {
				x = Integer.parseInt(args[0]);
			}
			catch (NumberFormatException e) {
				System.out.println("Le premier argument n'est pas un nombre");
			}
		}
		if (args.length > 1) {
			try {
				y = Integer.parseInt(args[1]);
			}
			catch (NumberFormatException e) {
				System.out.println("Le premier argument n'est pas un nombre");
			}
		}
		Kruskal kruskal = new Kruskal(x,y);
		Labyrinthe l = kruskal.algorithme();	
		System.out.println(l.toString());
	}
}