/*tabelle hash a indirizzamento aperto
l'ispezione di una tabella hash a indirizzamento aperto permette la ricerca all'interno della tabella della posizione a cui si vuole inserire l'elemento.
SE E' VUOTA l'elemento si inserisce all'interno
SE E' PIENA  allora si alloca della nuova memoria in coda o lo si inserisce semplicemente in coda

si ridefinizsce il tipo di TInfo  in quanto c'è necessita della mappatura dei campi usati all'interno della hash table
il campo è una voce INT used che associa 1 se il campo è stato gia usato, 0 invece se non e stato utilizzato, per monitorare l'impiego dei bucket

 nella implementazione del meccanismo di inserimento della hash table a indirizzamento aperto causa un aumento del numero delle collisioni, quindi per ovviare a cio si necessita
di un uamento della taglia della memoria allocata. Per permettere l'inserimento di tutti gli elementi dobbiamo avere un coefficiente di carico strettamente inferiore
a 1 in quanto:
-se superiore non permette l'inclusione di tutti gli elementi in quanto non è presente memoria allocata
-le prestazioni migliorano in quanto si avvicinano a una complessità costante
Il coefficiente di carico OTTIMALE deve essere compreso tra 0.5 e 0.75

L'USO di questa tabella viene preferito quando la singola informazione da memorizzare nella hash table è piccola

*/

#include "HTheader_aperto.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

THT HTCreate(int n){
    THT* ht=malloc(sizeof(THT));
    assert(ht!=NULL);
    ht->bucket=malloc(sizeof(TInfo)*n);
    ht->used=malloc(sizeof(int)*n);
    assert(ht->bucket!=NULL && ht->used!=NULL);
    ht->n_used=0;
    ht->n_bucket=n;
    for(int i=0;i<n;i++){
        ht->used[i]=0;
    }
    return ht;
}

void HTDestroy(THT*ht){
    free(ht->used);
    free(ht->bucket);
    free(ht);
}

TValue HTSearch(THT*ht,TKey key){
    unsigned h=keyHash(key)%ht->n_bucket;
    TInfo info ={key};
    while(ht->used[h] && !infoEqual(info, ht->n_bucket[h])){
        h=(h+1)%ht->n_bucket;
    }
    return(ht->used[h])? &ht->bucket[h].v: NULL;
}

void HTinsert(THT*ht, TKey key, TValue value){
    TValue *p=HTSearch(ht, key);
    if(p!=NULL){
        *p=value;
        return;
    }
    //devo procedere al ridimensionamento in mancanza di spazio??
    if(ht->n_used+1>= (ht->n_bucket*GROW_FACTOR)){
        HTresize(ht,GROW_FACTOR*ht->n_bucket+1);
        unsigned int h=keyHash(key)%ht->n_used;
        while(ht->used[h])
            h=(h+1)%ht->n_bucket;
        ht->bucket[h].v=value;
        ht->bucket[h].k=key;
        ht->used[h]=1;
        ht->n_used++;
    }

}
//complessita computazionale
//T(n1)+T(n2)=T(n)
void HTresize (THT *ht, int n){
    TInfo* bucket=ht->bucket;
    int* used=ht->used;
    int n_buckets=ht->n_bucket;
    ht->bucket=malloc(sizeof(TInfo)*n);
    ht->used=malloc(sizeof(int)*n);
    assert(ht->bucket!=NULL && ht->used!=NULL);
    ht->n_bucket=n;
    for(int i=0;i<n;i++){
        ht->used[i]=0;
    }
    ht->n_used=0;

    for(int i=0;i<n_buckets;i++){
        if(ht->used[i]==1)
            HTinsert(ht,bucket[i].k, bucket[i].v);
    }
    free(bucket);
    free(used);
}


//complessita computazionale lineare
void HTdelete(THT*ht, TKey key){
    unsigned int h=keyHash(key)%ht->n_bucket;
    //scandisco la tabella finoa che non trovo l'elemento
    TInfo info={key};
    while(ht->used[h] &&!infoEqual(info,ht->bucket[h]))
        h=(h+1)%ht->n_bucket;
    if(!ht->used[h])            //se non lo trova non fa modifiche
        return;
    unsigned int hole=h;        //libero l'elemento
    ht->used[h]=0;
    ht->n_used--;
                                //scansiono la tabella
    h=(h+1)%ht->n_bucket;       //mi posiziono alla pos. successiva
    while(ht->used[h]){
        //verifico se l'elemento trovato è spostabile o meno
        //ottengo la chiave dell'elemento e l'hashing della chiave
        unsigned int h1=keyHash(ht->bucket[h].k)%ht->n_bucket;
        //valutazione del possibile spostamento della chiave
        if(((h>hole) &&(h1<=hole || h1>h))||(h<hole && h1>h && h1<=hole))
        {
            //cambio l'elemento e i parametri ad esso associati
           ht->bucket[hole]=ht->bucket[h] ;
           ht->used[hole]=1;
           hole=h;
           ht->used[hole]=0;
        }
        //reitero il procedimento per poter modificare il buco successivo creato
        h=(h+1)%ht->n_bucket;
    }


}

//ricerca quadratica
/*
 h(k), |h(k)+c1+c2|m,|h(k)+c1+c2+2c1+2c2|m,...
 * se ipotizzo c1=c2=1/2:
 * h(k), |h(k)+1|m,|h(k)+3|m,...
 *
 * ****problematica: possibile mancanza di confronto tra elementi che vengono saltati
 * ***vantaggio: facilita il caso in cui gli elementi hanno tutti valori di hashing molto simili
 *
 * DOPPIO HASHING
 * determino due funzioni di hashing in base alle quali definisco un valore per determinare
 * l'hashing dell'elemento (combinazione lineare delle due hashing)
 * h1(k),|h1(k)+h2(k)|m, |h1(k) +2h2(k)|m,...
 *
 *