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

#define TABLESIZE 37
#define PRIME     13

enum Marker {EMPTY,USED,DELETED};

typedef struct _slot{
    int key;
    enum Marker indicator;
} HashSlot;

int HashInsert(int key, HashSlot hashTable[]);
int HashDelete(int key, HashSlot hashTable[]);


int hash1(int key);
int hash2(int key);

int main()
{
    int opt;
    int i;
    int key;
    int comparison;
    HashSlot hashTable[TABLESIZE];

    for(i=0;i<TABLESIZE;i++){
        hashTable[i].indicator = EMPTY;
        hashTable[i].key = 0;
    }

    printf("============= Hash Table ============\n");
    printf("|1. Insert a key to the hash table  |\n");
    printf("|2. Delete a key from the hash table|\n");
    printf("|3. Print the hash table            |\n");
    printf("|4. Quit                            |\n");
    printf("=====================================\n");
    printf("Enter selection: ");
    scanf("%d",&opt);
    while(opt>=1 && opt <=3){
        switch(opt){
        case 1:
            printf("Enter a key to be inserted:\n");
            scanf("%d",&key);
            comparison = HashInsert(key,hashTable);
            if(comparison <0)
                printf("Duplicate key\n");
            else if(comparison < TABLESIZE)
                printf("Insert: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Key Comparisons: %d. Table is full.\n",comparison);
            break;
        case 2:
            printf("Enter a key to be deleted:\n");
            scanf("%d",&key);
            comparison = HashDelete(key,hashTable);
            if(comparison <0)
                printf("%d does not exist.\n", key);
            else if(comparison <= TABLESIZE)
                printf("Delete: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Error\n");
            break;
        case 3:
            for(i=0;i<TABLESIZE;i++) printf("%d: %d %c\n",i, hashTable[i].key,hashTable[i].indicator==DELETED?'*':' ');
            break;
        }
        printf("Enter selection: ");
        scanf("%d",&opt);
    }
    return 0;
}

int hash1(int key)
{
    return (key % TABLESIZE);
}

int hash2(int key)
{
    return (key % PRIME) + 1;
}


int HashInsert(int key, HashSlot hashTable[])
{
   int hash_1 = hash1(key), hash_2 = hash2(key), newIndex = 0, comparisons = 0;
   int storedIndex = -1, i=0, internalCheck = 0, found = 0;

   newIndex = (hash_1+i++*hash_2) % TABLESIZE;

   // if slot is empty, it will insert immediately without checking for duplicates
   if (hashTable[newIndex].indicator == EMPTY) {
     hashTable[newIndex].key = key;
     hashTable[newIndex].indicator = USED;
     return comparisons;
   }

   while (comparisons < TABLESIZE && internalCheck < TABLESIZE) {
     //internalCheck because the maximum number of iterations should not exceed table size
     internalCheck++;
     //if current slot is DELETED and no previous deleted slot has been found
     //store the current index into storedIndex and set found to true
     //in a sense storing the first deleted slot found for future use

     //if current slot is USED and slot's key == key, return -1
     // else increase comparison
     if (hashTable[newIndex].indicator == DELETED && !found) {
        storedIndex = newIndex;
        found = 1;
     } else if (hashTable[newIndex].indicator == USED) { //
       if (hashTable[newIndex].key == key) {
         return -1;
       } else {
         comparisons++;
       }
     }

     //set new index from hash functions for next iteration
     newIndex = (hash_1+i++*hash_2) % TABLESIZE;
     if (hashTable[newIndex].indicator == EMPTY) {
       if (storedIndex == -1) {
         hashTable[newIndex].key = key;
         hashTable[newIndex].indicator = USED;
         return comparisons--;
       }
     }
   }

   //if storedIndex exists, then set the index to key and USED
   if (storedIndex != -1) {
     hashTable[storedIndex].key = key;
     hashTable[storedIndex].indicator = USED;
   }
   return comparisons;
}

int HashDelete(int key, HashSlot hashTable[])
{
   //Write your code here
   int hash_1 = hash1(key);
   int hash_2 = hash2(key);
   int newIndex = 0;
   int comparisons = 0;
   int internalCheck = 0;
   int i=0;

   while (comparisons < TABLESIZE && internalCheck <= TABLESIZE) {
     internalCheck++;
     newIndex = (hash_1+i++*hash_2) % TABLESIZE;

     if (hashTable[newIndex].indicator == USED) {
       comparisons++;
       if (hashTable[newIndex].key == key) {
         hashTable[newIndex].indicator = DELETED;
         return comparisons;
       }
     }
   }

   return -1;
}