package memoire;

import memoire.exception.*;

/**
 * Compilateur.memoire.TableSymboles.java
 * 
 * Une table de hachage pour un type de cles donne, consiste en une fonction de hachage h
 * et Un tableau de taille N.
 * Lorsqu'on implemente une table des symboles a l'aide d'une table de hachage,
 * le but est d'inserer l'entree ( k , v ) , dans la cellule d'indice i = h(k), ou 
 * la cles k represente la valeur d'un IDENT.
 * 
 * @author Ludovic
 * cree le 5 dec. 07
 */
public class TableSymboles {

	private final static int N = 37; // nombre de case dans le tableau d'entre (nombre premier)
	private final static int P = 31; // nombre premier pour le codage des caracteres
	
	
	public Element[] Table; // tableau de listes chainees
	
	/**
	 * Constructeur de la classe memoire.HashTable.java
	 */
	public TableSymboles(){
		this.Table = new Element[N];
	}
	
	/**
	 * Ajoute un symbole dans la table des symboles.
	 * @param EntreeTableSymbole symbole a ajouter
	 */
	public void ajoute(EntreeTableSymbole ets){
		
		int key = hashValeur(ets.id);
		
		if(Table[key] == null){
			Table[key] = new Element(ets);
		}else{
			Table[key].ajoute(ets);
		}
	}
	
	/**
	 * Supprime un symbole dans la table des symboles.
	 * @param EntreeTableSymbole symbole a supprimer
	 */
	public void supprime(EntreeTableSymbole ets){

		int key = hashValeur(ets.id);
		if(Table[key] != null){
			Table[key].supprime(ets);
		}
		
	}
	
	/**
	 * Modifie un quadruplet dans la table des symboles.
	 * @param Qua q<br /> <i>quadruplet a modifier</i>
	 */
	public boolean modifie(EntreeTableSymbole ets){
		
		int key = hashValeur(ets.id);
		
		Element e = Table[key].recherche(ets);
		if(e == null) return false; // valeur d'erreur !
		
		e.setValeur(ets);
		
		return true;
		
	}
	/**
	 * Verifie l'existance d'un quadruplet dans la table des symboles.
	 *
	 * @param Qua q<br /> <i>quadruplet a rechercher</i>
	 * @return boolean<br /><i>Renvoie vrai si la recherche reussi, faux si l'element n'est 
	 * pas trouve. </i>
	 */
	public boolean exist(EntreeTableSymbole ets){
		
		int key = hashValeur(ets.id);
		
		if(Table[key].recherche(ets) == null) return false;
		
		return true;
		
	}
	/**
	 * Cherche la position d'un quadruplet dans la table des symboles.
	 *
	 * @param Qua q<br /> <i>quadruplet a rechercher</i>
	 * @return String<br /><i>Renvoie le couple de position (l.c) ou l est la
	 * ligne et c la colonne.  </i>
	 */
	public String cherchePos(EntreeTableSymbole ets){
		
		int key = hashValeur(ets.id);
		
		Element e = Table[key].recherche(ets);
		if(e == null) return null; // valeur d'erreur !
		
		int cpt = 0;
		while(e.getPrecedent() != null){
			cpt++; e = e.getPrecedent();
		}
		
		String pos = new String("("+key+"."+cpt+")");
		return pos;	
	}
	
	/**
	 * Renvoi la sorte d'un symbole
	 * @param id identifiant recherche
	 * @return portee portee a partir de laquel chercher
	 */
	public String rechercheSorte(String id, String obj, String portee) throws IdNonDansTableSymboleException {
		
		int key = hashValeur(id);
		
		if(Table[key]==null){
			throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "," + portee + "> non trouve dans la table des symboles !");
		}
			
		String sorte = Table[key].rechercheSorte(id,obj,portee);
		
		if(sorte == null){
			String sup_portee = this.recherchePortee(portee, "meth");
			if(sup_portee==null){
				throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "," + portee + "> non trouve dans la table des symboles !");
			}else{
				return this.rechercheSorte(id, obj, sup_portee);
			}
		}else{
			return sorte;
		}
			
	}
	
	/**
	 * Renvoi la sorte d'un symbole
	 * @param id identifiant recherche
	 * @return portee portee a partir de laquel chercher
	 */
	public String rechercheProfil(String id, String obj, String portee) throws IdNonDansTableSymboleException {
		
		int key = hashValeur(id);
		
		if(Table[key]==null){
			throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "," + portee + "> non trouve dans la table des symboles !");
		}
			
		String profil = Table[key].rechercheProfil(id,obj,portee);
		
		if(profil == null){
			String sup_portee = this.recherchePortee(portee, "meth");
			if(sup_portee==null){
				throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "," + portee + "> non trouve dans la table des symboles !");
			}else{
				return this.rechercheProfil(id, obj, sup_portee);
			}
		}else{
			return profil;
		}
			
	}
	
	/**
	 * Recherche la portee d'un symbole en fonction de son identifiant et de son type d'objet
	 * @param id identifiant recherche
	 * @return obj sorte de l'id
	 */
	public String recherchePortee(String id, String obj) throws IdNonDansTableSymboleException {
		
		int key = hashValeur(id);
		
		if(Table[key]==null){
			throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "> non trouve dans la table des symboles !");
		}
		
		String e = Table[key].recherchePortee(id,obj);
		
		if(e == null){
			throw new IdNonDansTableSymboleException("Objet <" + id + "," + obj + "> non trouve dans la table des symboles !");
		}else{
			return e;
		}
			
	}
	
	/** 
	 * <b>HashTable.hashValeur</b>
	 * <br />
	 * Une fonction de hachage est definie habituellement comme la composition de deux fonctions:
	 * <br /><ul>
	 * <li>Le code de hachage<br />
	 * 		 <i>h1 : clee -> entier</i></li>
	 * <li>La fonction de compression<br />
	 * 		 <i>h2 : entier -> [0,N-1]</i></li></ul>
	 * 
	 * Le resultat est donc : <i>h(k) = h2(h1(k)) = indice de table</i>.
	 * 
	 * @param String k<br />
	 * <i>chaine de caracteres a hacher.<i>
	 * 
	 */
	public static int hashValeur(String k){
		
		if(k == null) return -1; // valeur d'erreur
		
		//h1 : clee -> entier
		
		int h1 = 0;
		int n = k.length();
		
		if(n == 1){
			h1 = k.charAt(0)*P;
		}else{
			
			n = n - 1;
			
			for(int i=0; i<n; i++){
				
				h1 += k.charAt(i)*(P^n);
				n--;
			}
		}
		
		
		//h2 : entier -> [0,N-1]
		int h2 = h1 % N;
		
		return h2;
	}
	
	public String toString(){
		String ret="Table Symbole : \n";
		for(int i=0;i<Table.length;i++){
			if(Table[i]!=null){
				ret+="   ["+i+"] : "+Table[i].toString()+"\n";
			}
		}
		return ret;
	}
	
	/**
	 * HashTable.main test
	 * @return void
	 * @param args
	 */
	public static void main(String[] args) {
		
		String k;
		TableSymboles table = new TableSymboles();
		EntreeTableSymbole q;
		
		System.out.println("Debut du test de hachage");
		
		k="a";
		System.out.println("a :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="b";
		System.out.println("b :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="x";
		System.out.println("x :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="y";
		System.out.println("y :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="Class";
		System.out.println("Class :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="IDENT";
		System.out.println("IDENT :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="popoldesiles";
		System.out.println("popoldesiles :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="d_g_f_a";
		System.out.println("d_g_f_a :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"1","v","e");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		k="y"; // en double pour verifier la pr�-emption de colision
		System.out.println("y2 :" + hashValeur(k));
		q = new EntreeTableSymbole(k,"0","v","B");
		table.ajoute(q);
		System.out.println(table.cherchePos(q));
		
		
				
		System.out.println("fin du test de hachage !");

	}
	
	
	
	
	
	
		
	
}
