/* 
* Code example for CP264 Data Structures II
* array hash table with linear probing for collision handling
* HBF 
*/
#include <stdio.h>
#include <malloc.h>
#define SIZE 20

typedef struct hashnode {
  int key;
  int value;
} hashnode;

typedef struct hashtable {
  hashnode **hnp; // pointer pointing to the first element of an array of hashnode pointers 
  int size;       // the maximum of number of array elements
  int count;      // number of data elements in the hash table
} hashtable;

hashnode *new_hashnode(int key, int value) {
  hashnode *hn = (hashnode*) malloc(sizeof(hashnode));
  hn->key = key;  
  hn->value = value;
  return hn;
}

/*
 * hash function to hash a key to an index value
*/
int hash(int key) {
  return key % SIZE;
}

//create hash table dynamically
hashtable *new_hashtable(int size) {
  //dynamically create an array to hold hashnode pointers	
  hashtable *ht = (hashtable*) malloc(sizeof(hashtable));
  ht->hnp = (hashnode**) malloc(sizeof(hashnode*)*size);
  int i;
  for (i=0; i<size; i++) 
	ht->hnp[i] =  NULL;
    //*(ht->hnp+i) =  NULL;
  
  ht->size = size;
  ht->count = 0;
  return ht;
}

hashnode *search(hashtable *ht, int key) { 
  int i = hash(key);
  while (ht->hnp[i] != NULL) {
    if (ht->hnp[i]->key == key && ht->hnp[i]->key != -1)
      return ht->hnp[i];

    ++i;
    if (i >= ht->size)
      i %= ht->size; //wrap around the table
  }
  return NULL;
}

void insert(hashtable *ht, hashnode *hn) {
  if (ht->count >= ht->size) return; // hash table is full (overflow), can not insert
  int i = hash(hn->key);

  //move in array until an empty or deleted cell
  while (ht->hnp[i] != NULL && ht->hnp[i]->key != -1) {
    ++i;
    if (i >= ht->size)
      i %= ht->size; // wrap around the table
  }
  ht->hnp[i] = hn;
  ht->count++;
}

/* delete the first encounter key element */
int delete(hashtable *ht, int key) {
  if (ht->count == 0) return 0;  // empty (underflow), can not insert
 
  int i = hash(key);

  //move in array until an empty
  while (ht->hnp[i] != NULL) {
    if (ht->hnp[i]->key == key && ht->hnp[i]->key != -1) {
      ht->hnp[i]->key = -1;
	  ht->count--;
      return 1;
    }
    ++i;
    if (i >= ht->size)
      i %= ht->size; //wrap around the table
  }
  return 0;
}

void display(hashtable *ht) {
  int i = 0;
  int len = ht->size;
  printf("size:  %d\n", ht->size);
  printf("count: %d\n", ht->count);
  printf("hash data:\nindex: (key, data)\n");
  for (i = 0; i < len; i++) {
    if (ht->hnp[i] != NULL && ht->hnp[i]->key != -1)
      printf("%2d: (%d, %d)\n", i, ht->hnp[i]->key, ht->hnp[i]->value);
  }
  printf("\n");
}

void clean(hashtable *ht) {
  if (ht == NULL) return;
  int i;
  for (i = 0; i < ht->size; i++) {
    if (ht->hnp[i] != NULL)
	  free(ht->hnp[i]);
  }
  free(ht->hnp);
}

int main() {
  //use static array to create array of hashnode pointers and initialized to be NULL 
  hashtable ht = {0}; 
  hashnode *htarray[SIZE] = {0}; // create statically hashnode pointer array and initialize all elements to NULL
  ht.hnp = &htarray[0];          // set the array pointer  
  ht.size = SIZE;                // set the size   
  ht.count = 0;
   
  //insert key, data into hash table
  insert(&ht,  new_hashnode(1, 20));
  insert(&ht, new_hashnode(2, 70));
  insert(&ht, new_hashnode(42, 80));
  insert(&ht, new_hashnode(4, 25));
  insert(&ht, new_hashnode(12, 44));
  insert(&ht, new_hashnode(14, 32));
  insert(&ht, new_hashnode(17, 11));
  insert(&ht, new_hashnode(13, 78));
  insert(&ht, new_hashnode(37, 97));
  display(&ht);
  //insert by key
  int key = 37;
  hashnode *hn = search(&ht, key);
  if (hn != NULL) {
    printf("Find data element: (%d, %d)\n", hn->key, hn->value);
  } else {
    printf("Not found element with key %d\n", key);
  }
  //insert by key
  if (delete(&ht, key)) 
	 printf("element with key %d is deleted\n", key); 
  
  hn = search(&ht, key);
  if (hn != NULL) {
    printf("Find data element: (%d, %d)\n", hn->key, hn->value);
  } else {
    printf("Not found element with key %d\n", key);
  }

  display(&ht);
  clean(&ht);    
  return 0;
}

/*
size:  20
count: 9
hash data:
index: (key, data)
 1: (1, 20)
 2: (2, 70)
 3: (42, 80)
 4: (4, 25)
12: (12, 44)
13: (13, 78)
14: (14, 32)
17: (17, 11)
18: (37, 97)

Find data element: (37, 97)
element with key 37 is deleted
Not found element with key 37
size:  20
count: 8
hash data:
index: (key, data)
 1: (1, 20)
 2: (2, 70)
 3: (42, 80)
 4: (4, 25)
12: (12, 44)
13: (13, 78)
14: (14, 32)
17: (17, 11)

*/