#include <stdio.h>
#include <stdlib.h>

typedef struct cell
{
    int key;
    int status;
} Cell;

enum { FREE, OCCUPIED };

void afisare(Cell *T, int m)
{
    printf("\n\nTabela de dispersie este \n");
    for (int i = 0; i < m; i++)
    {
        if(T[i].status == OCCUPIED)
            printf("T[%d]=%d\n",i,T[i]);
        else
            printf("T[%d]= --\n",i);
    }
}

void insert_key(int k, Cell *T, int m, int (*hash_func)(int k, int m, int i))
{
    int i;
    for(i=0;i<m;i++)
    {
        int h=hash_func(k,m,i);///retinem valoarea(pozitia) returnata de :linear/quadric probing sau double hashing
        if(T[h].status==FREE)
        {
            T[h].key=k;
            T[h].status=OCCUPIED;
            return;
        }
    }
}

void delete_key(int k, Cell* T, int m, int (*hash_func)(int k, int m, int i)){

    int i;
    for (i=0;i<m;i++){
        int h = hash_func(k, m, i);
        if(T[h].key ==k)
        {
        T[h].status = FREE;
        return;
    }
    }

}

int h_prime(int k, int m)
{
  return 0;
}

//returneaza pozitia la care se va verifica tabela de dispersie folosind verificarea liniara
int linear_probing(int k, int m, int i)
{
  return (k+i)%m;
}

int quadratic_probing(int k, int m, int i)
{
  return (k+i+i*i)%m;
}

int double_hashing(int k, int m, int i)
{
    int nr=1;
    int j;
    for(j=0; j<k; j++)
        nr = nr*2;

    return (k + i*nr)%m;
    return 0;

}

void set_table_free(Cell *T, int m)
{
    //initializam tabela
    int i;
    for (i = 0; i<m; i++)
    {
        T[i].status = FREE;
    }
}

int main()
{
    int m = 7;
    Cell *T = (Cell*) malloc(m*sizeof(Cell)); //tabela de dispersie - se aloca

    //test linear probing
    set_table_free(T, m);
    int vals[] = {19, 36, 5, 21, 4, 26, 14, 17};
    for(int i=0; i<sizeof(vals)/sizeof(int); i++)
      insert_key(vals[i], T, m, linear_probing);
    afisare(T, m);
    //21, 36, 26, 14, 4, 19, 5

    //test quadratic probing
    set_table_free(T, m);
    for(int i=0; i<sizeof(vals)/sizeof(int); i++)
      insert_key(vals[i], T, m, quadratic_probing);
    afisare(T, m);
    //k + i + i*i mod m: 19, 36, 5, 4, 21, 26, 14

    //test double hashing
    set_table_free(T, m);
    for(int i=0; i<sizeof(vals)/sizeof(int); i++)
      insert_key(vals[i], T, m, double_hashing);
    afisare(T, m);
    //k + i*2^k mod m: 21, 36, 5, 14, 4, 19, 26


    //test hash function
    insert_key(100000, T, m, double_hashing);
    afisare(T, m);
    insert_key(-3, T, m, linear_probing);
    afisare(T, m);
    free(T);
    return 0;
}