/* 
* Code example for CP264 Data Structures II
* chained hash table
* HBF 
*/
#include <stdio.h>
#include <malloc.h>
#define SIZE 20

/* linked hash node */
typedef struct hashnode {
  int key;
  int value;
  struct hashnode *next;
} hashnode;

typedef struct hashtable {
  hashnode **hnp;    // pointer pointing to the array of hash node pointers 
  int size;          // hash table size, maximum number of different indexes
  int count;         // number of data elements in the hash table
} hashtable;

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

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

//create hash by dynamic created array
hashtable *new_hashtable(int size) {
  // allocate space for hashtable structure
  hashtable *ht = (hashtable*) malloc(sizeof(hashtable));  
  // allocate memory to hold the array of hashnode pointers
  ht->hnp = (hashnode**) malloc(sizeof(hashnode**)*size);  
      
  // initialize each pointers of array to NULL;   
  int i;
  for (i=0; i<size; i++) 
    *(ht->hnp+i) =  NULL;   //ht->hnp[i] = NULL; 

  // set the size property
  ht->size = size;
  
  // set the count property  
  ht->count = 0;   

  return ht;
}

/*
 search data element from hash table by key.  
*/
hashnode *search(hashtable *ht, int key) { 
  int i = hash(key);
  hashnode *p = *(ht->hnp + i); //hashnode *p = ht->hnp[i]; 
  if (p != NULL) { 
    while ( p != NULL) {
      if (key == p->key )  // return the first data element matching the key
        return p;
      p = p->next;
    }
  }  
  return NULL;
}

/*
 insert hash node into hash table 
*/
void insert(hashtable *ht, hashnode *np) { 
  int key = np->key;
  int i = hash(key);  
  hashnode *p = *(ht->hnp + i), *pp = NULL;  // pp for previous pointer

  if (p == NULL) {       // empty linked list
    *(ht->hnp + i) = np; // set new node as the leading node
  } 
  else {  
    while (p && key > p->key ) {  // ordered by key value for search 
     pp = p;  
     p = p->next;
  }
  
  if (pp == NULL)
    *(ht->hnp + i) = np;    
  else 
    pp->next = np;
     
  np->next = p;  
  }
  
  ht->count++;
}


/*
 * delete hash table element by matched key, return 0 if not existing, else 1 if deleted
*/
int delete(hashtable *ht, int key) {
  int i = hash(key);
  hashnode *p = *(ht->hnp + i), *pp = NULL;  

  if (p != NULL) {
    while (p && key > p->key) {
      pp = p;
      p = p->next;
    }
    
    if (p && key == p->key) {
      if (pp) 
        pp->next = p->next;  
      else 
        *(ht->hnp + i) = NULL;  
      
      free(p);
      ht->count--;
      return 1;
    }  
  }
  return 0;
}

void display(hashtable *ht) {
  int i = 0;
  hashnode *p;
  printf("size:  %d\n", ht->size);
  printf("count: %d\n", ht->count);
  printf("hash data:\nindex: list of the data of the same hash index");
  for (i = 0; i < ht->size; i++) {
  p = *(ht->hnp + i);
  if (p)
    printf("\n%2d: ", i);
  while (p) {
     printf("(%d,%d) ", p->key, p->value);
     p = p->next;
  }
  }
  printf("\n");
}

void clean(hashtable *ht) {
  if (ht == NULL) return;
  hashnode *p, *temp;
  int i;
  for (i = 0; i < ht->size; i++) {
    p = *(ht->hnp + i);
    while (p) {
      temp = p;  
      p = p->next;
      free(temp);
    }
	i++;
  }
  free(ht->hnp);
}

int main() {
  hashtable *ht = new_hashtable(SIZE);
  insert(ht, new_hashnode(1, 20));
  insert(ht, new_hashnode(2, 70));
  insert(ht, new_hashnode(42, 80));
  insert(ht, new_hashnode(2, 25));
  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));
  
  printf("hash table after insertion\n");
  display(ht);
  
  int key = 37;
  printf("\nsearch data by key %d\n", key);
  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);
  }

  printf("delete data by key %d\n", key);
  delete(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;
}

/*
hash table after insertion
size:  20
count: 10
hash data:
index: list of the data of the same hash index
 1: (1,20)
 2: (2,25) (2,70) (42,80)
 4: (4,25)
12: (12,44)
13: (13,78)
14: (14,32)
17: (17,11) (37,97)

search data by key 37
Find data element: (37, 97)
delete data by key 37
Find data element: (11605096, 11610960)
size:  20
count: 9
hash data:
index: list of the data of the same hash index
 1: (1,20)
 2: (2,25) (2,70) (42,80)
 4: (4,25)
12: (12,44)
13: (13,78)
14: (14,32)
17: (17,11)
*/