package Dizionario;
import java.math.BigInteger;
public class DizHashHD implements Dizionario, Hash {
    private DizRecord[] diz;    // tabella hash che rappresenta il dizionario
    private int count;          // num. elementi del dizionario
    private int tot_accessi;    // num. totale accessi alla tabella hash

    //post: costruisce un dizionario vuoto di dimensione INITIAL_CAPACITY
    public DizHashHD() {
        clear();
    }


    // post: ritorna il numero di elementi nel dizionario
    public int size() {
	return count;
    }


    // post: ritorna true sse il dizionario e' vuoto
    public boolean isEmpty() {
        return count == 0;
    }


    // post: svuota il dizionario e lo riporta alla dimensione INITIAL_CAPACITY
    public void clear() {
	diz = new DizRecord[Hash.INITIAL_CAPACITY]; // devo usare necessariamente new! 
        count = 0;
        tot_accessi = 0;
    }       


    // pre: key >= 0 
    // post: prima funzione hash dell'hashing doppio
    private int hash1(int key) {
	return key % diz.length;
    }


    // pre: key >=0
    // post: seconda funzione hash dell'hashing doppio
    private int hash2(int key) {
	return (key % (diz.length -1)) + 1;
    }

    // pre: i>=0; base1 determinato dal metodo hash1 e 
    //      base2 determinato dal metodo hash2
    // post: ritorna l'indice dell'array associato a key
    private int scansione(int base1, int base2, int i) {
        return ((base1 + i*base2) % diz.length);
    }


    // post: ritorna il fattore di carico del dizionario
    public double loadFactor() {
	return (double)count/diz.length;
    }


   // post: ritorna il numero totale di accessi alla tabella hash 
    public int getStatistics() {
        return tot_accessi;
    }


    // post: ritorna la capacita' attuale della tabella hash
    public int getCapacity() {
	return diz.length;
    }


    // post: se il load factor della tabella hash e' minore di RESIZE_TRIGGER
    //       non fa nulla e ritorna false; altrimenti aumenta la capacita' 
    //       della tabella usando il fattore RESIZE_FACTOR e cercando il numero primo
    //       successivo. Ritorna true se per tutte le coppie presenti in tabella il 
    //       riassegnamento delle nuove posizioni va a buon fine. 
    public boolean rehash() {

	if (loadFactor() < Hash.RESIZE_TRIGGER)
	    return false;

	DizRecord[] copy = new DizRecord[diz.length];
        System.arraycopy(diz,0,copy,0,diz.length);
        BigInteger prime = BigInteger.valueOf((long)(diz.length*Hash.RESIZE_FACTOR));    
        int newcapacity = (prime.nextProbablePrime()).intValue();
        diz = new DizRecord[newcapacity];
        count = 0;  // insert conta di nuovo gli elementi inseriti   
        boolean ok=true;
        for (int i = 0; i<copy.length && ok;i++) 
            if (copy[i] != null && !copy[i].canc)
	       ok = insert(copy[i].key, copy[i].elem); 
        
	return ok;
    }
    

   // pre:  key>=0, ob diverso da null
   // post: aggiunge la coppia (key,ob) nel dizionario se non e' pieno e
   //       se key non e' presente. Ritorna true se l'inserimento e' 
   //       andato a buon fine; ritorna false altrimenti
    public boolean insert(int key, Object ob) {

	if (count == diz.length)
	    return false;

        int base1 = hash1(key);
	int base2 = hash2(key);
	int pos = 0;
	int first_canc = -1;
	int i = 0;
	boolean ok = false;
	while (i < diz.length && !ok) {
	    pos = scansione(base1, base2, i);
	    tot_accessi++;
            if (diz[pos] != null && diz[pos].canc && first_canc == -1)
		first_canc = pos;  // memorizzo la prima posizione con chiave cancellata

	    if (diz[pos] == null || (diz[pos].key == key && !diz[pos].canc))
	       ok = true;
            else
               i++;
	}

	if ((i == diz.length && first_canc == -1) || // errore di scansione: ci deve essere una cella libera!
	    (diz[pos] != null && diz[pos].key == key && !diz[pos].canc)) // chiave trovata
	    return false;

	// chiave non trovata: sono uscita per i == diz.length o per diz[pos] == null
        // posso distinguere il da farsi con first_canc

	if (first_canc != -1) {  // ho attraversato un elemento cancellato?
	  // mi sono fermata per null o fine scansione: inserisco nella prima cancellata 
	    diz[first_canc].key = key;
	    diz[first_canc].canc = false;
	    diz[first_canc].elem = ob;
	}
	else // mi sono fermata per null senza aver attraversato un elemento cancellato
	    diz[pos] = new DizRecord(key,ob); 

	count++;
	return true;
       
    }


   // Pre:  key diverso da null
   // post: cancella dal dizionario la coppia con chiave key. Ritorna 
   //       true se l'operazione e' andata a buon fine; false altrimenti
    public boolean delete(int key) {

	int pos = findPos(key);
	if (pos != -1) {
	    diz[pos].canc = true;
	    count--;
	    return true;
	}
	else
	    return false;
    }
    

    // pre: key diverso da null
    // post: ritorna l'indice della chiave key nel dizionario. Ritorna -1
    //       se key non e' presente nel dizionario
    private int findPos(int key) {
	int base1 = hash1(key);
	int base2 = hash2(key);
	int pos = 0;
	int i = 0;
	boolean ok = false;
	while (i < diz.length && !ok) {
	    pos = scansione(base1, base2, i);
	    tot_accessi++;
            if (diz[pos] == null || (diz[pos].key==key && !diz[pos].canc))
	       ok = true; 
	    else
	       i++;
	}

	if (i == diz.length || diz[pos] == null)  // chiave non trovata
	    return -1;
	else  // chiave trovata
	    return pos;
    }


    // pre:  key diverso da null
    // post: se key e' presente nel dizionario ritorna l'elemento ad essa
    //       associato. Ritorna null altrimenti.
    public Object search(int key) {
	int pos = findPos(key);
	if (pos != -1)
	    return diz[pos].elem;
	else
	    return null;
    }

   
    // post: ritorna una stringa che rappresenta tutte le coppie 
    //       presenti nel dizionario separate da uno spazio.
    //       Ciascuna coppia e' descritta da "pos:(k,e)" dove
    //       pos e' la posizione occupata dalla chiave in tabella
    public String toString() {
        String s = "";
	for (int i = 0; i < diz.length; i++) 
            if (diz[i] != null && !diz[i].canc)
	       s = s + i + ":(" + diz[i].key + "," + 
                   diz[i].elem.toString() + ") ";
	return s;
    }




} // fine classe DizHashHD