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

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

struct IDS {
   int id;
   struct IDS* next;
};

struct WORDS {
   char* word;
   struct WORDS* next;
};

struct WORDIDSS {
   char* word;
   struct IDS* ids;
   struct WORDIDSS* next;
};

char* STRING_new(char* w) {
   int len = strlen(w) + 1;
   char* s = malloc(sizeof(char) * len);
   memcpy(s, w, len);
   return s;
}

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

struct IDS* IDS_new(int id) {
   struct IDS* s = malloc(sizeof(struct IDS));
   s->id = id;
   s->next = NULL;
   return s;
}

void IDS_destroy(struct IDS** s) {
   struct IDS* a;
   while (*s != NULL) {
      a = *s;
      *s = (*s)->next;
      free(a);
   }
}

void IDS_add(struct IDS** s, int id) {
   struct IDS* a = *s;
   struct IDS* n = IDS_new(id);
   if (a == NULL) {
      *s = n;
   } else {
      while (a->next != NULL) {
         a = a->next;
      }
      a->next = n;
   }
}

struct WORDS* WORDS_new(char* word) {
   struct WORDS* s = malloc(sizeof(struct WORDS));
   s->word = STRING_new(word);
   s->next = NULL;
   return s;
}

void WORDS_destroy(struct WORDS** s) {
   struct WORDS* a;
   while (*s != NULL) {
      a = *s;
      *s = (*s)->next;
      STRING_destroy(a->word);
      free(a);
   }
}

void WORDS_add(struct WORDS** s, char* word) {
   struct WORDS* n = WORDS_new(word);
   struct WORDS* a = *s;
   if (a == NULL) {
      *s = n;
   } else {
      while (a->next != NULL) {
         a = a->next;
      }
      a->next = n;
   }
}

struct WORDIDSS* WORDIDSS_new(char* word, int id) {
   struct WORDIDSS* s = malloc(sizeof(struct WORDIDSS));
   s->word = STRING_new(word);
   s->ids = IDS_new(id);
   s->next = NULL;
   return s;
}

void WORDIDSS_destroy(struct WORDIDSS** s) {
   struct WORDIDSS* a;
   while (*s != NULL) {
      a = *s;
      *s = (*s)->next;
      STRING_destroy(a->word);
      IDS_destroy(&a->ids);
      free(a);
   }
}

void WORDIDSS_add(struct WORDIDSS** s, char* word, int id) {
   struct WORDIDSS* a = *s;
   if (a == NULL) {
      *s = WORDIDSS_new(word, id);
   } else {
      while (1) {
         if (strcmp(a->word, word) == 0) {
            IDS_add(&a->ids, id);
            break;
         }
         if (a->next == NULL) {
            a->next = WORDIDSS_new(word, id);
            break;
         }
         a = a->next;
      }
   }
}

void WORDIDSS_add_words(struct WORDIDSS** s, struct WORDS* words, int id) {
   while (words != NULL) {
      WORDIDSS_add(s, words->word, id);
      words = words->next;
   }
}

struct IDS* WORDIDSS_get(struct WORDIDSS* s, char* word) {
   while (s != NULL) {
      if (strcmp(s->word, word) == 0) {
         return s->ids;
      }
      s = s->next;
   }
   return NULL;
}

int WORDIDSS_count(struct WORDIDSS* s) {
   int i = 0;
   while (s != NULL) {
      i++;
      s = s->next;
   }
   return i;
}

struct IDS* IDS_and(struct IDS* a, struct IDS* b) {
   struct IDS* c = NULL;
   while (a != NULL) {
      if (b == NULL) {
         break;
      }
      if (a->id < b->id) {
         a = a->next;
      } else if (a->id > b->id) {
         b = b->next;
      } else {
         IDS_add(&c, a->id);
         a = a->next;
         b = b->next;
      }
   }
   return c;
}

/* return new instance */
struct IDS* IDS_unique(struct IDS* s) {
   struct IDS* n = NULL;
   int id;
   
   if (s != NULL) {
      IDS_add(&n, s->id);
      id = s->id;
      s = s->next;
      while (s != NULL) {
         if (s->id != id) {
            IDS_add(&n, s->id);
            id = s->id;
         }
         s = s->next;
      }
   }
   return n;
}

void IDS_print(struct IDS* s) {
   while (s != NULL) {
      printf("%d\n", s->id);
      s = s->next;
   }
}

int IDS_count(struct IDS* s) {
   int i = 0;
   while (s != NULL) {
      i++;
      s = s->next;
   }
   return i;
}

struct DOCUMENT* DOCUMENT_new(int id, char* body, struct DOCUMENT* next) {
   struct DOCUMENT* s = malloc(sizeof(struct DOCUMENT));
   s->id = id;
   s->body = body;
   s->next = next;
   return s;
}

void DOCUMENT_destroy(struct DOCUMENT** s) {
   struct DOCUMENT* a;
   while (*s != NULL) {
      a = *s;
      *s = (*s)->next;
      STRING_destroy(a->body);
      free(a);
   }
}

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

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

struct DOCUMENT* createDocs(char* filename) {
   char row[65536];
   FILE* f = NULL;
   struct DOCUMENT* docs = NULL;
   int i;
      
   f = fopen(filename, "r");
   i = 0;
   while (fgets(row, 65536, f) != NULL) {
      row[strlen(row) - 1] = '\0';
      DOCUMENT_add(&docs, i, row);
      i++;
   }
   fclose(f);
   
   return docs;
}

struct WORDIDSS* createWiss(struct DOCUMENT* docs, int rowSize, char* dlm) {
   struct WORDIDSS* wiss = NULL;
   char* row = malloc(sizeof(char) * rowSize);
   char* w;
   while (docs != NULL) {
      strcpy(row, docs->body);
      w = strtok(row, dlm);
      while (w != NULL) {
         WORDIDSS_add(&wiss, w, docs->id);
         w = strtok(NULL, dlm);
      }
      docs = docs->next;
   }
   free(row);
   return wiss;
}

struct WORDS* inputQuery(int rowSize, char* dlm) {
   struct WORDS* ws = NULL;
   char* row = malloc(sizeof(char) * rowSize);
   char* w;
   printf("Enter Query:");
   fgets(row, 65536, stdin);
   w = strtok(row, dlm);
   while (w != NULL) {
      WORDS_add(&ws, w);
      w = strtok(NULL, dlm);
   }
   free(row);
   return ws;
}

/* return new instance */
struct IDS* andsearch(struct WORDS* ws, struct WORDIDSS* wiss) {
   struct IDS* a = NULL;
   struct IDS* b = NULL;
   struct IDS* c = NULL;
   
   if (ws != NULL) {
      a = WORDIDSS_get(wiss, ws->word);
      while (a != NULL) {
         IDS_add(&b, a->id);
         a = a->next;
      }
      ws = ws->next;
      while (ws != NULL) {
         c = b;
         b = IDS_and(b, WORDIDSS_get(wiss, ws->word));
         IDS_destroy(&c);
         ws = ws->next;
      }
   }
   return b;
}

void printinfo(struct IDS* ids, struct DOCUMENT* docs) {
   struct DOCUMENT* doc;
   while (ids != NULL) {
      doc = DOCUMENT_get(docs, ids->id);
      printf("%d\n", ids->id);
      printf("%s\n", doc->body);
      printf("\n");
      ids = ids->next;
   }
}

void theme1(struct WORDIDSS* wiss) {
   struct IDS* john = WORDIDSS_get(wiss, "john");
   struct IDS* and = WORDIDSS_get(wiss, "and");
   struct IDS* said = WORDIDSS_get(wiss, "said");
   
   printf("Total number of words in the index = %d\n", WORDIDSS_count(wiss));
   printf("john = %d\n", IDS_count(john));
   printf("and = %d\n", IDS_count(and));
   printf("said = %d\n", IDS_count(said));
}

void theme2(struct WORDIDSS* wiss, struct DOCUMENT* docs, int rowSize, char* dlm) {
   struct WORDS* ws = inputQuery(rowSize, dlm);
   struct IDS* ids = andsearch(ws, wiss);
   struct IDS* uni = IDS_unique(ids);
   if (IDS_count(uni) < 1) {
      printf("words not found\n");
   } else {
      printinfo(uni, docs);
   }
   free(uni);
   free(ids);
   free(ws);
}


int main(int argc, char* argv[]) {
   struct DOCUMENT* docs = NULL;
   struct WORDIDSS* wiss = NULL;
   const char* dlm = " \t\n";
   const int rowSize = 65536;
   
   char* filename;
   
   if (argc < 3) {
      return;
   }
   if (strcmp(argv[1], "-f") != 0) {
      return;
   }
   
   filename = argv[2];
   docs = createDocs(filename);
   wiss = createWiss(docs, rowSize, dlm);

   theme1(wiss);
   theme2(wiss, docs, rowSize, dlm);
   
   WORDIDSS_destroy(&wiss);
   DOCUMENT_destroy(&docs);

   return EXIT_SUCCESS;
}