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

typedef struct DOCUMENT {
   int id;
   char* body;
   struct DOCUMENT* next;
} DOCUMENT;

typedef struct ArrayList {
   int count;
   int size;
   int* data;
} ArrayList;

typedef struct WordList {
   char* word;
   ArrayList* list;
   struct WordList* next;
} WordList;

typedef struct Hashtable {
   int size;
   int count;
   WordList** table;
} Hashtable;

void String_destroy(char* s) {
   free(s);
}

char* String_new(char* cs) {
   int len = strlen(cs) + 1;
   char* s = malloc(sizeof(char) * len);
   if (s != NULL) {
      memcpy(s, cs, len);
   }
   return s;
}

void DOCUMENT_destroy(DOCUMENT* s) {
   if (s->body != NULL) {
      String_destroy(s->body);
   }
   if (s->next != NULL) {
      DOCUMENT_destroy(s->next);
   }
   free(s);
}

DOCUMENT* DOCUMENT_new(int id, char* body) {
   DOCUMENT* s = malloc(sizeof(DOCUMENT));
   if (s != NULL) {
      s->body = NULL;
      s->next = NULL;
      
      s->body = String_new(body);
      if (s->body != NULL) {
         s->id = id;
         return s;
      }
      DOCUMENT_destroy(s);
   }
   return NULL;
}

int DOCUMENT_add(DOCUMENT** s, int id, char* body) {
   DOCUMENT* n = DOCUMENT_new(id, body);
   DOCUMENT* a = *s;
   if (n != NULL) {
      if (a == NULL) {
         *s = n;
      } else {
         while (a->next != NULL) {
            a = a->next;
         }
         a->next = n;
      }
      return 1;
   }
   return 0;
}

char* DOCUMENT_find(DOCUMENT* s, int id) {
   while (s != NULL) {
      if (s->id == id) {
         return s->body;
      }
      s = s->next;
   }
   return NULL;
}

void ArrayList_destroy(ArrayList* s) {
   free(s->data);
   free(s);
}

ArrayList* ArrayList_new(void) {
   ArrayList* s = malloc(sizeof(ArrayList));
   s = malloc(sizeof(ArrayList));
   if (s != NULL) {
      s->data = NULL;
      
      s->count = 0;
      s->size = 4;
      s->data = malloc(sizeof(int) * s->size);
      if (s->data != NULL) {
         return s;
      }
   }
   ArrayList_destroy(s);
   return NULL;
}

int ArrayList_add(ArrayList* s, int value) {
   int* data;
   if (s->count >= s->size) {
      s->size = s->size * 2;
      data = realloc(s->data, sizeof(int) * s->size);
      if (data == NULL) {
         return 0;
      }
      s->data = data;
   }
   s->data[s->count] = value;
   s->count = s->count + 1;
   return 1;
}

void ArrayList_print(ArrayList* s) {
   int i;
   for (i = 0; i < s->count; i++) {
      printf("%d\n", s->data[i]);
   }
}

void ArrayList_clear(ArrayList* s) {
   s->count = 0;
}

void ArrayList_intersect(ArrayList* s, ArrayList* m) {
   int i = 0;
   int j = 0;
   int n = 0;
   while (i < s->count) {
      if (j >= m->count) {
         break;
      }
      if (s->data[i] < m->data[j]) {
         i++;
      } else if (s->data[i] > m->data[j]) {
         j++;
      } else {
         s->data[n] = s->data[i];
         i++;
         j++;
         n++;
      }
   }
   s->count = n;
}

void ArrayList_distinct(ArrayList* s) {
   int i;
   int j;
   int c = s->count;
   int* data = s->data;
   for (i = 1; i < c; i++) {
      if (data[i - 1] == data[i]) {
         for (j = i + 1; j < c; j++) {
            if (data[j - 1] != data[j]) {
               data[i] = data[j];
               i = i + 1;
            }
         }
         s->count = i;
         return;
      }
   }
}

void WordList_destroy(WordList* s) {
   if (s->word != NULL) {
      String_destroy(s->word);
   }
   if (s->list != NULL) {
      ArrayList_destroy(s->list);
   }
   if (s->next != NULL) {
      WordList_destroy(s->next);
   }
   free(s);
}

WordList* WordList_new(char* word, int id, WordList* next) {
   WordList* s = malloc(sizeof(WordList));
   if (s != NULL) {
      s->word = NULL;
      s->list = NULL;
      s->next = next;
      
      s->word = String_new(word);
      if (s->word != NULL) {
         s->list = ArrayList_new();
         if (s->list != NULL) {
            if (ArrayList_add(s->list, id)) {
               return s;
            }
         }
      }
   }
   WordList_destroy(s);
   return NULL;
}

void Hashtable_destroy(Hashtable* s) {
   free(s->table);
   free(s);
}

Hashtable* Hashtable_new(void) {
   int i;
   Hashtable* s = malloc(sizeof(Hashtable));
   if (s != NULL) {
      s->table = NULL;
      
      s->count = 0;
      s->size = 65521;
      s->table = malloc(sizeof(WordList*) * s->size);
      if (s->table != NULL) {
         for (i = 0; i < s->size; i++) {
            s->table[i] = NULL;
         }
         return s;
      }
   }
   Hashtable_destroy(s);
   return NULL;
}

unsigned int Hashtable_hash(Hashtable* s, char* c)
{
   unsigned int hashval;
   for (hashval = 0; *c != '\0'; c++)
      hashval = *c + (31 * hashval);
   return hashval % s->size;
}

ArrayList* Hashtable_find(Hashtable* s, char* word) {
   unsigned int hash = Hashtable_hash(s, word);
   WordList* a = s->table[hash];
   while (a != NULL) {
      if (strcmp(a->word, word) == 0) {
         return a->list;
      }
      a = a->next;
   }
   return NULL;
}

int Hashtable_insert(Hashtable* s, char* word, int id) {
   unsigned int hash = Hashtable_hash(s, word);
   WordList* n = WordList_new(word, id, s->table[hash]);
   if (n != NULL) {
      s->table[hash] = n;
      return 1;
   }
   return 0;
}

int Hashtable_add(Hashtable* s, char* word, int id) {
   ArrayList* a = Hashtable_find(s, word);
   if (a != NULL) {
      if (ArrayList_add(a, id)) {
         return 1;
      }
   } else {
      if (Hashtable_insert(s, word, id)) {
         s->count = s->count + 1;
         return 1;
      }
   }
   return 0;
}

DOCUMENT* use_file(FILE* f) {
   char row[65536];
   DOCUMENT* d = NULL;
   int i = 0;
   while (fgets(row, 65536, f) != NULL) {
      row[strlen(row) - 1] = '\0';
      if (!DOCUMENT_add(&d, i, row)) {
         if (d != NULL) {
            DOCUMENT_destroy(d);
         }
         return NULL;
      }
      i = i + 1;
   }
   return d;
}

DOCUMENT* create_document(char* filename) {
   DOCUMENT* d = NULL;
   FILE* f = fopen(filename, "r");
   if (f != NULL) {
      d = use_file(f);
      fclose(f);
   }
   return d;
}

int add_words(int id, char* words, Hashtable* hash) {
   char ws[65536];
   char* w;
   strcpy(ws, words);
   w = strtok(ws, " \t\n");
   while (w != NULL) {
      if (!Hashtable_add(hash, w, id)) {
         return 0;
      }
      w = strtok(NULL, " \t\n");
   }
   return 1;
}

Hashtable* create_hashtable(DOCUMENT* docs) {
   Hashtable* h = Hashtable_new();
   if (h != NULL) {
      while (docs != NULL) {
         if (!add_words(docs->id, docs->body, h)) {
            Hashtable_destroy(h);
            return NULL;
         }
         docs = docs->next;
      }
   }
   return h;
}

ArrayList* execute_query(Hashtable* h) {
   char row[65536];
   char* w;
   int i;
   ArrayList* a = ArrayList_new();
   ArrayList* b;
   if (a != NULL) {
      printf("Enter Query:");
      fgets(row, 65536, stdin);
      w = strtok(row, " \t\n");
      if (w != NULL) {
         b = Hashtable_find(h, w);
         if (b != NULL) {
            for (i = 0; i < b->count; i++) {
               if (!ArrayList_add(a, b->data[i])) {
                  ArrayList_destroy(a);
                  return NULL;
               }
            }
            while (1) {
               w = strtok(NULL, " \t\n");
               if (w == NULL) {
                  break;
               }
               b = Hashtable_find(h, w);
               if (b == NULL) {
                  ArrayList_clear(a);
                  break;
               }
               ArrayList_intersect(a, b);
            }
            ArrayList_distinct(a);
         }
      }
   }
   return a;
}

int main(int argc, char* argv[]) {
   int i;
   ArrayList* list = NULL;
   Hashtable* hash = NULL;
   DOCUMENT* doc = NULL;
   char* filename;
   
   if (argc < 3) {
      return 1;
   }
   if (strcmp(argv[1], "-f") != 0) {
      return 1;
   }
   
   filename = argv[2];
   
   doc = create_document(filename);
   if (doc != NULL) {
      hash = create_hashtable(doc);
      if (hash != NULL) {
         printf("Total number of words in the index = %d\n", hash->count);
         printf("john = %d\n", Hashtable_find(hash, "john")->count);
         printf("and = %d\n", Hashtable_find(hash, "and")->count);
         printf("said = %d\n", Hashtable_find(hash, "said")->count);
         list = execute_query(hash);
         if (list != NULL) {
            if (list->count < 1) {
               printf("words not found\n");
            } else {
               for (i = 0; i < list->count; i++) {
                  printf("%d\n", list->data[i]);
                  printf("%s\n", DOCUMENT_find(doc, list->data[i]));
                  printf("\n");
               }
            }
         }
      }
   }
   
   if (list != NULL) {
      ArrayList_destroy(list);
   }
   if (hash != NULL) {
      Hashtable_destroy(hash);
   }
   if (doc != NULL) {
      DOCUMENT_destroy(doc);
   }
   
   return 0;
}