//-----------------------------------------------------------------------------
// Dictionary.c
// Michelle Pham
// mpham14
// 12/05/19
// CSE 15
// .c file for the Dictionary ADT
//-----------------------------------------------------------------------------
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<string.h>
#include"Dictionary.h"

// Private Types and Functions ------------------------------------------------

// NodeObj type
typedef struct NodeObj{
   char* key;
   char* value;
   struct NodeObj* next;
} NodeObj;

// Node type
typedef NodeObj* Node;

// DictrionaryObj type
typedef struct DictionaryObj{
   Node* table;    // array of linked lists
   int numPairs;   // number of pairs in this Dictionary
} DictionaryObj;

// newNode()
// constructor for the Node type
Node newNode(char* k, char* v) {
   Node N = malloc(sizeof(NodeObj));
   N->key = k;
   N->value = v;
   N->next = NULL;
   return N;
}

// freeNode()
// destructor for the Node type
void freeNode(Node* pN){
   if( pN!=NULL && *pN!=NULL ){
      free(*pN);
      *pN = NULL;
   }
}

// freeAllNodes()
// uses recursion to free all the Nodes in list headed by H
void freeAllNodes(Node H){
   if( H!=NULL ){
      freeAllNodes(H->next);
      freeNode(&H);
   }
}

// countChars()
// Returns the number of characters in the (key, value) pairs.
int countChars(Node D){
   int count = 0;
   if( D!=NULL ){
      count += countChars(D->next);
      count += strlen(D->key)+strlen(D->value)+2;
   }
   return count;
}

const int tableSize=101; // or some prime other than 101

// rotate_left()
// rotate the bits in an unsigned int
unsigned int rotate_left(unsigned int value, int shift) {
   int sizeInBits = 8*sizeof(unsigned int);
   shift = shift & (sizeInBits - 1);
   if ( shift == 0 )
   return value;
   return (value << shift) | (value >> (sizeInBits - shift));
}

// pre_hash()
// turn a string into an unsigned int
unsigned int pre_hash(char* input) {
   unsigned int result = 0xBAE86554;
   while (*input) {
   result ^= *input++;
   result = rotate_left(result, 5);
   }
   return result;
}

// hash()
// turns a string into an int in the range 0 to tableSize-1
int hash(char* key){
    return pre_hash(key)%tableSize;
}

// findKey()
// Returns the Node containing key k, or returns NULL if no such Node exists
Node findKey(Dictionary D, char* k) {
   int i = hash(k);
   Node N = D->table[i];
   while(N!=NULL){
      if(strcmp(N->key, k) == 0){
         return N;
      }
      N = N->next;
   }
   return NULL;
}

// Constructors-Destructors ---------------------------------------------------

// newDictionary()
// Constructor for the Dictionary ADT
Dictionary newDictionary(){
   Dictionary D = malloc(sizeof(DictionaryObj));
   D->table = calloc(tableSize, sizeof(Node));
   D->numPairs = 0;

   return D;
}

// freeDictionary()
// Destructor for the Dictionary ADT.
void freeDictionary(Dictionary* pD){
   if( pD!=NULL && *pD!=NULL ){
      makeEmpty(*pD);
      free((*pD)->table);
      free(*pD);
      *pD = NULL;
   }
}

// ADT operations -------------------------------------------------------------

// size()
// Return the number of (key, value) pairs in Dictionary D.
int size(Dictionary D){
   if(D==NULL) {
      fprintf(stderr, "Dictionary Error: size() called on NULL Dictionary reference\n");
      exit(EXIT_FAILURE);
   }
   return D->numPairs;
}

// lookup()
// If D contains a pair whose key matches argument k, then return the
// corresponding value, otherwise return NULL.
char* lookup(Dictionary D, char* k) {
   Node N;
   if(D==NULL) {
      fprintf(stderr, "Dictionary Error: lookup() called on NULL Dictionary reference\n");
      exit(EXIT_FAILURE);
   }

   N = findKey(D, k);
   if(N!=NULL) {
      return N->value;
   }
   else {
      return NULL;
   }
}

// insert()
// Insert the pair (k,v) into D.
// Pre: lookup(D, k)==NULL (D does not contain a pair whose first member is k.)
void insert(Dictionary D, char* k, char* v){
   Node N;
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling insert() on NULL Dictionary reference\n");
      exit(EXIT_FAILURE);
   }

   if( findKey(D, k)!=NULL ){
      fprintf(stderr, "Dictionary Error: cannot insert() duplicate key: \"%s\"\n", k);
      exit(EXIT_FAILURE);
   }

   int i = hash(k);

   N = newNode(k, v);
   N->next = D->table[i];
   D->table[i] = N;

   (D->numPairs)++;
}

// delete()
// Remove pair whose first member is the argument k from D.
// Pre: lookup(D,k)!=NULL (D contains a pair whose first member is k.)
void delete(Dictionary D, char* k){
   Node N, P, S;
   //int x;
   if( D==NULL ){
      fprintf(stderr, "Dictionary Error: calling delete() on NULL Dictionary reference\n");
      exit(EXIT_FAILURE);
   }

   int i = hash(k);
   N = findKey(D, k);

   if( N==NULL ){
      fprintf(stderr, "Dictionary Error: cannot delete() non-existent key: \"%s\"\n", k);
      exit(EXIT_FAILURE);
   }

   if(D->table[i] == N){  // Node is at the beginning
      S = D->table[i];
      D->table[i] = D->table[i]->next;
   }
   else{                  // Node is anywhere else
      P = D->table[i];
      while(P->next != N){
         P = P->next;
      }
      S = P->next;
      P->next = S->next;
   }
   S->next = NULL;
   freeNode(&S);
   (D->numPairs)--;
}

// makeEmpty()
// Reset D to the empty state, the empty set of pairs.
void makeEmpty(Dictionary D){
   if(D==NULL) {
      fprintf(stderr, "Dictionary Error: calling makeEmpty() on NULL Dictionary reference\n");
      exit(EXIT_FAILURE);
   }
   for(int k = 0; k < tableSize; k++){
      freeAllNodes(D->table[k]);
      D->table[k] = NULL;
   }
   D->numPairs = 0;
}

// Other Operations -----------------------------------------------------------

// DictionaryToString()
// Determines a text representation of the current state of Dictionary D. Each
// (key, value) pair is represented as the chars in key, followed by a space,
// followed by the chars in value, followed by a newline '\n' char. The pairs
// occur in alphabetical order by key. The function returns a pointer to a char
// array, allocated from heap memory, containing the text representation
// described above, followed by a terminating null '\0' char. It is the
// responsibility of the calling function to free this memory.
char* DictionaryToString(Dictionary D){
   if( D==NULL ){
      fprintf(stderr,
         "Dictionary Error: calling DictionaryToString() on NULL Dictionary "\
         "reference\n");
      exit(EXIT_FAILURE);
   }

   char* str;
   int n = 0;
   Node N;

   for(int k = 0; k < tableSize; k++) {
      if(D->table[k]!=NULL){
         n += countChars(D->table[k]);
      }
   }

   str = calloc(n+1, sizeof(char));

   for(int k = 0; k < tableSize; k++) {
      if(D->table[k]!=NULL){
         N = D->table[k];
         while(N != NULL){
            strcat(str, N->key);
            strcat(str, " ");
            strcat(str, N->value);
            strcat(str, "\n");
            N = N->next;
         }
      }
   }
   str[n] = '\0';
   return str;

}