fork download 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. struct DOCUMENT {
  6.    int id;
  7.    char* body;
  8.    struct DOCUMENT* next;
  9. };
  10.  
  11. struct IDS {
  12.    int id;
  13.    struct IDS* next;
  14. };
  15.  
  16. struct WORDS {
  17.    char* word;
  18.    struct WORDS* next;
  19. };
  20.  
  21. struct WORDIDSS {
  22.    char* word;
  23.    struct IDS* ids;
  24.    struct WORDIDSS* next;
  25. };
  26.  
  27. char* STRING_new(char* w) {
  28.    int len = strlen(w) + 1;
  29.    char* s = malloc(sizeof(char) * len);
  30.    memcpy(s, w, len);
  31.    return s;
  32. }
  33.  
  34. void STRING_destroy(char* s) {
  35.    free(s);
  36. }
  37.  
  38. struct IDS* IDS_new(int id) {
  39.    struct IDS* s = malloc(sizeof(struct IDS));
  40.    s->id = id;
  41.    s->next = NULL;
  42.    return s;
  43. }
  44.  
  45. void IDS_destroy(struct IDS** s) {
  46.    struct IDS* a;
  47.    while (*s != NULL) {
  48.       a = *s;
  49.       *s = (*s)->next;
  50.       free(a);
  51.    }
  52. }
  53.  
  54. void IDS_add(struct IDS** s, int id) {
  55.    struct IDS* a = *s;
  56.    struct IDS* n = IDS_new(id);
  57.    if (a == NULL) {
  58.       *s = n;
  59.    } else {
  60.       while (a->next != NULL) {
  61.          a = a->next;
  62.       }
  63.       a->next = n;
  64.    }
  65. }
  66.  
  67. struct WORDS* WORDS_new(char* word) {
  68.    struct WORDS* s = malloc(sizeof(struct WORDS));
  69.    s->word = STRING_new(word);
  70.    s->next = NULL;
  71.    return s;
  72. }
  73.  
  74. void WORDS_destroy(struct WORDS** s) {
  75.    struct WORDS* a;
  76.    while (*s != NULL) {
  77.       a = *s;
  78.       *s = (*s)->next;
  79.       STRING_destroy(a->word);
  80.       free(a);
  81.    }
  82. }
  83.  
  84. void WORDS_add(struct WORDS** s, char* word) {
  85.    struct WORDS* n = WORDS_new(word);
  86.    struct WORDS* a = *s;
  87.    if (a == NULL) {
  88.       *s = n;
  89.    } else {
  90.       while (a->next != NULL) {
  91.          a = a->next;
  92.       }
  93.       a->next = n;
  94.    }
  95. }
  96.  
  97. struct WORDIDSS* WORDIDSS_new(char* word, int id) {
  98.    struct WORDIDSS* s = malloc(sizeof(struct WORDIDSS));
  99.    s->word = STRING_new(word);
  100.    s->ids = IDS_new(id);
  101.    s->next = NULL;
  102.    return s;
  103. }
  104.  
  105. void WORDIDSS_destroy(struct WORDIDSS** s) {
  106.    struct WORDIDSS* a;
  107.    while (*s != NULL) {
  108.       a = *s;
  109.       *s = (*s)->next;
  110.       STRING_destroy(a->word);
  111.       IDS_destroy(&a->ids);
  112.       free(a);
  113.    }
  114. }
  115.  
  116. void WORDIDSS_add(struct WORDIDSS** s, char* word, int id) {
  117.    struct WORDIDSS* a = *s;
  118.    if (a == NULL) {
  119.       *s = WORDIDSS_new(word, id);
  120.    } else {
  121.       while (1) {
  122.          if (strcmp(a->word, word) == 0) {
  123.             IDS_add(&a->ids, id);
  124.             break;
  125.          }
  126.          if (a->next == NULL) {
  127.             a->next = WORDIDSS_new(word, id);
  128.             break;
  129.          }
  130.          a = a->next;
  131.       }
  132.    }
  133. }
  134.  
  135. void WORDIDSS_add_words(struct WORDIDSS** s, struct WORDS* words, int id) {
  136.    while (words != NULL) {
  137.       WORDIDSS_add(s, words->word, id);
  138.       words = words->next;
  139.    }
  140. }
  141.  
  142. struct IDS* WORDIDSS_get(struct WORDIDSS* s, char* word) {
  143.    while (s != NULL) {
  144.       if (strcmp(s->word, word) == 0) {
  145.          return s->ids;
  146.       }
  147.       s = s->next;
  148.    }
  149.    return NULL;
  150. }
  151.  
  152. int WORDIDSS_count(struct WORDIDSS* s) {
  153.    int i = 0;
  154.    while (s != NULL) {
  155.       i++;
  156.       s = s->next;
  157.    }
  158.    return i;
  159. }
  160.  
  161. struct IDS* IDS_and(struct IDS* a, struct IDS* b) {
  162.    struct IDS* c = NULL;
  163.    while (a != NULL) {
  164.       if (b == NULL) {
  165.          break;
  166.       }
  167.       if (a->id < b->id) {
  168.          a = a->next;
  169.       } else if (a->id > b->id) {
  170.          b = b->next;
  171.       } else {
  172.          IDS_add(&c, a->id);
  173.          a = a->next;
  174.          b = b->next;
  175.       }
  176.    }
  177.    return c;
  178. }
  179.  
  180. /* return new instance */
  181. struct IDS* IDS_unique(struct IDS* s) {
  182.    struct IDS* n = NULL;
  183.    int id;
  184.  
  185.    if (s != NULL) {
  186.       IDS_add(&n, s->id);
  187.       id = s->id;
  188.       s = s->next;
  189.       while (s != NULL) {
  190.          if (s->id != id) {
  191.             IDS_add(&n, s->id);
  192.             id = s->id;
  193.          }
  194.          s = s->next;
  195.       }
  196.    }
  197.    return n;
  198. }
  199.  
  200. void IDS_print(struct IDS* s) {
  201.    while (s != NULL) {
  202.       printf("%d\n", s->id);
  203.       s = s->next;
  204.    }
  205. }
  206.  
  207. int IDS_count(struct IDS* s) {
  208.    int i = 0;
  209.    while (s != NULL) {
  210.       i++;
  211.       s = s->next;
  212.    }
  213.    return i;
  214. }
  215.  
  216. struct DOCUMENT* DOCUMENT_new(int id, char* body, struct DOCUMENT* next) {
  217.    struct DOCUMENT* s = malloc(sizeof(struct DOCUMENT));
  218.    s->id = id;
  219.    s->body = body;
  220.    s->next = next;
  221.    return s;
  222. }
  223.  
  224. void DOCUMENT_destroy(struct DOCUMENT** s) {
  225.    struct DOCUMENT* a;
  226.    while (*s != NULL) {
  227.       a = *s;
  228.       *s = (*s)->next;
  229.       STRING_destroy(a->body);
  230.       free(a);
  231.    }
  232. }
  233.  
  234. void DOCUMENT_add(struct DOCUMENT** s, int id, char* body) {
  235.    struct DOCUMENT* n = DOCUMENT_new(id, STRING_new(body), NULL);
  236.    struct DOCUMENT* a = *s;
  237.    if (a == NULL) {
  238.       *s = n;
  239.    } else {
  240.       while (a->next != NULL) {
  241.          a = a->next;
  242.       }
  243.       a->next = n;
  244.    }
  245. }
  246.  
  247. struct DOCUMENT* DOCUMENT_get(struct DOCUMENT* s, int id) {
  248.    while (s != NULL) {
  249.       if (s->id == id) {
  250.          return s;
  251.       }
  252.       s = s->next;
  253.    }
  254.    return NULL;
  255. }
  256.  
  257. struct DOCUMENT* createDocs(char* filename) {
  258.    char row[65536];
  259.    FILE* f = NULL;
  260.    struct DOCUMENT* docs = NULL;
  261.    int i;
  262.  
  263.    f = fopen(filename, "r");
  264.    i = 0;
  265.    while (fgets(row, 65536, f) != NULL) {
  266.       row[strlen(row) - 1] = '\0';
  267.       DOCUMENT_add(&docs, i, row);
  268.       i++;
  269.    }
  270.    fclose(f);
  271.  
  272.    return docs;
  273. }
  274.  
  275. struct WORDIDSS* createWiss(struct DOCUMENT* docs, int rowSize, char* dlm) {
  276.    struct WORDIDSS* wiss = NULL;
  277.    char* row = malloc(sizeof(char) * rowSize);
  278.    char* w;
  279.    while (docs != NULL) {
  280.       strcpy(row, docs->body);
  281.       w = strtok(row, dlm);
  282.       while (w != NULL) {
  283.          WORDIDSS_add(&wiss, w, docs->id);
  284.          w = strtok(NULL, dlm);
  285.       }
  286.       docs = docs->next;
  287.    }
  288.    free(row);
  289.    return wiss;
  290. }
  291.  
  292. struct WORDS* inputQuery(int rowSize, char* dlm) {
  293.    struct WORDS* ws = NULL;
  294.    char* row = malloc(sizeof(char) * rowSize);
  295.    char* w;
  296.    printf("Enter Query:");
  297.    fgets(row, 65536, stdin);
  298.    w = strtok(row, dlm);
  299.    while (w != NULL) {
  300.       WORDS_add(&ws, w);
  301.       w = strtok(NULL, dlm);
  302.    }
  303.    free(row);
  304.    return ws;
  305. }
  306.  
  307. /* return new instance */
  308. struct IDS* andsearch(struct WORDS* ws, struct WORDIDSS* wiss) {
  309.    struct IDS* a = NULL;
  310.    struct IDS* b = NULL;
  311.    struct IDS* c = NULL;
  312.  
  313.    if (ws != NULL) {
  314.       a = WORDIDSS_get(wiss, ws->word);
  315.       while (a != NULL) {
  316.          IDS_add(&b, a->id);
  317.          a = a->next;
  318.       }
  319.       ws = ws->next;
  320.       while (ws != NULL) {
  321.          c = b;
  322.          b = IDS_and(b, WORDIDSS_get(wiss, ws->word));
  323.          IDS_destroy(&c);
  324.          ws = ws->next;
  325.       }
  326.    }
  327.    return b;
  328. }
  329.  
  330. void printinfo(struct IDS* ids, struct DOCUMENT* docs) {
  331.    struct DOCUMENT* doc;
  332.    while (ids != NULL) {
  333.       doc = DOCUMENT_get(docs, ids->id);
  334.       printf("%d\n", ids->id);
  335.       printf("%s\n", doc->body);
  336.       printf("\n");
  337.       ids = ids->next;
  338.    }
  339. }
  340.  
  341. void theme1(struct WORDIDSS* wiss) {
  342.    struct IDS* john = WORDIDSS_get(wiss, "john");
  343.    struct IDS* and = WORDIDSS_get(wiss, "and");
  344.    struct IDS* said = WORDIDSS_get(wiss, "said");
  345.  
  346.    printf("Total number of words in the index = %d\n", WORDIDSS_count(wiss));
  347.    printf("john = %d\n", IDS_count(john));
  348.    printf("and = %d\n", IDS_count(and));
  349.    printf("said = %d\n", IDS_count(said));
  350. }
  351.  
  352. void theme2(struct WORDIDSS* wiss, struct DOCUMENT* docs, int rowSize, char* dlm) {
  353.    struct WORDS* ws = inputQuery(rowSize, dlm);
  354.    struct IDS* ids = andsearch(ws, wiss);
  355.    struct IDS* uni = IDS_unique(ids);
  356.    if (IDS_count(uni) < 1) {
  357.       printf("words not found\n");
  358.    } else {
  359.       printinfo(uni, docs);
  360.    }
  361.    free(uni);
  362.    free(ids);
  363.    free(ws);
  364. }
  365.  
  366.  
  367. int main(int argc, char* argv[]) {
  368.    struct DOCUMENT* docs = NULL;
  369.    struct WORDIDSS* wiss = NULL;
  370.    const char* dlm = " \t\n";
  371.    const int rowSize = 65536;
  372.  
  373.    char* filename;
  374.  
  375.    if (argc < 3) {
  376.       return;
  377.    }
  378.    if (strcmp(argv[1], "-f") != 0) {
  379.       return;
  380.    }
  381.  
  382.    filename = argv[2];
  383.    docs = createDocs(filename);
  384.    wiss = createWiss(docs, rowSize, dlm);
  385.  
  386.    theme1(wiss);
  387.    theme2(wiss, docs, rowSize, dlm);
  388.  
  389.    WORDIDSS_destroy(&wiss);
  390.    DOCUMENT_destroy(&docs);
  391.  
  392.    return EXIT_SUCCESS;
  393. }
  394.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/v5LvH1
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!