#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_linear(int k, Cell *T, int m)
{
    int i;
    for(i = 0; i < m; i++) {
        int h = linear_probing(k, m, i);
        if (T[h].status == FREE) {
            T[h].status = OCCUPIED;
            T[h].key = k;
            break;
        }
    }
}

void insert_key_quadratic(int k, Cell *T, int m)
{
    int i;
    for(i = 0; i < m; i++) {
        int h = quadratic_probing(k, m, i);
        if (T[h].status == FREE) {
            T[h].status = OCCUPIED;
            T[h].key = k;
            break;
        }
    }
}

void insert_key_double_hashing(int k, Cell *T, int m)
{
    int i;
    for(i = 0; i < m; i++) {
        int h = double_hashing(k, m, i);
        if (T[h].status == FREE) {
            T[h].status = OCCUPIED;
            T[h].key = k;
            break;
        }
    }
}


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 % m) + i) % m;
}

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

int double_hashing(int k, int m, int i)
{
  return ((k % m) + i * (5 - (k % 5))) % m;
}

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_linear(vals[i], T, m);
    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_quadratic(vals[i], T, m);
    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_double_hashing(vals[i], T, m);
    afisare(T, m);
    //k + i*2^k mod m: 21, 36, 5, 14, 4, 19, 26


    //test hash function
    insert_key_double_hashing(100000, T, m);
    afisare(T, m);
    insert_key_linear(-3, T, m);
    afisare(T, m);
    free(T);
    return 0;
}