Advertisement
Guest User

Untitled

a guest
Nov 30th, 2015
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.42 KB | None | 0 0
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define NAMELEN 64
  7. #define BUFSIZE 100
  8.  
  9. #define PLAYCOUNT 0
  10. #define ARTISTID 1
  11.  
  12. struct play {
  13.     int user_id;
  14.     int artist_id;
  15.     int playcount;
  16.     struct play *next;
  17. };
  18.  
  19. struct artist {
  20.     int artist_id;
  21.     char artist_name[NAMELEN];
  22.     int playcount;
  23.     int alt_id;
  24.     struct artist *next;
  25. };
  26.  
  27. void print_play(struct play *p);
  28. void print_plays(struct play *p);
  29. struct play *create_play(int id, int artist_id, int playcount);
  30. struct play *parse_play(char *line);
  31. struct play *read_plays(char *file_name);
  32. struct play *add_play(struct play *head, struct play *newp);
  33. struct play *filter_user(int user_id, struct play *head);
  34. int count_plays(struct play *head);
  35. void free_plays(struct play *p);
  36. void free_play(struct play *p);
  37.  
  38. void print_artist(struct artist *p);
  39. void print_artists(struct artist *p);
  40. struct artist *create_artist(int artist_id, char *name);
  41. struct artist *read_artists(char *fname);
  42. struct artist *add_artist(struct artist *head, struct artist *newp);
  43. void free_artists(struct artist *p);
  44. void free_artist(struct artist *p);
  45. struct artist *parse_artist(char *line);
  46.  
  47. struct play *sort_plays(struct play *head);
  48. struct play *merge_sort(struct play *x, struct play *y);
  49. struct play *find_middle(struct play *x);
  50.  
  51. struct artist *sort_artists(struct artist *artist, int criterion);
  52. struct artist *merge_sort_artists(struct artist *x, struct artist *y, int criterion);
  53. struct artist *find_middle_artists(struct artist *x);
  54.  
  55. struct artist *update_counts(struct artist *a, struct play *p);
  56.  
  57. void print_play(struct play *p) {
  58.     if(p==NULL) {
  59.         printf("NULL\n");
  60.         return;
  61.     }
  62.     printf("user: %d artist: %d count: %d\n", p->user_id, p->artist_id, p->playcount);
  63. }
  64.  
  65. void print_artist(struct artist *p) {
  66.     if(p==NULL) {
  67.         printf("NULL\n");
  68.         return;
  69.     }
  70.     printf("%s (%d) [%d]\n", p->artist_name, p->artist_id, p->playcount);
  71. }
  72.  
  73. struct play *create_play(int id, int artist_id, int playcount) {
  74.     struct play *newp = (struct play *)malloc(sizeof(struct play));
  75.  
  76.     if(newp!=NULL) {
  77.         newp->user_id = id;
  78.         newp->artist_id = artist_id;
  79.         newp->playcount = playcount;
  80.  
  81.         return newp;
  82.     } else {
  83.         printf("Error: play memory allocation failure\n");
  84.         free(newp);
  85.         exit(0);
  86.     }
  87.  
  88.     return NULL;
  89. }
  90.  
  91. struct artist *create_artist(int artist_id, char *name) {
  92.     struct artist *newp = (struct artist *)malloc(sizeof(struct artist));
  93.  
  94.     if(newp!=NULL) {
  95.         newp->artist_id = artist_id;
  96.         strcpy(newp->artist_name, name);
  97.  
  98.         return newp;
  99.     } else {
  100.         printf("Error: artist memory allocation failure\n");
  101.         free(newp);
  102.         exit(0);
  103.     }
  104.  
  105.     return NULL;
  106. }
  107.  
  108. struct play *parse_play(char *line) {
  109.     int u, a, c;
  110.  
  111.     if(sscanf(line, "%d %d %d\n", &u, &a, &c) == 3) {
  112.         return create_play(u, a, c);
  113.     } else  {
  114.         return NULL;
  115.     }
  116. }
  117.  
  118. struct artist *parse_artist(char *line) {
  119.     char name[NAMELEN]; int a;
  120.  
  121.     if(sscanf(line, "%d\t%65[^\t\n]\n", &a, name) == 2) {
  122.         return create_artist(a, name);
  123.     } else  {
  124.         return NULL;
  125.     }
  126. }
  127.  
  128. void free_play(struct play *p) {
  129.     free(p);
  130. }
  131.  
  132. void free_artist(struct artist *p) {
  133.     free(p);
  134. }
  135.  
  136. struct play *add_play(struct play *head, struct play *newp) {
  137.     if(newp==NULL) return head;
  138.  
  139.     newp->next = head;
  140.     return newp;
  141. }
  142.  
  143. struct artist *add_artist(struct artist *head, struct artist *newp) {
  144.     if(newp==NULL) return head;
  145.  
  146.     newp->next = head;
  147.     return newp;
  148. }
  149.  
  150. void print_plays(struct play *p) {
  151.     while(p != NULL) {
  152.         print_play(p);
  153.         p = p->next;
  154.     }
  155. }
  156.  
  157. void print_artists(struct artist *p) {
  158.     while(p != NULL) {
  159.         print_artist(p);
  160.         p = p->next;
  161.     }
  162. }
  163.  
  164. struct play *read_plays(char *file_name) {
  165.     FILE *fp = fopen(file_name, "r");
  166.     char line[BUFSIZE];
  167.     struct play *head = NULL;
  168.  
  169.     if(fp == NULL) {
  170.         printf("Error: File not found\n");
  171.         return NULL;
  172.     } else {
  173.         while(!feof(fp)) {
  174.             if(fgets(line, BUFSIZE, fp) != NULL) head = add_play(head, parse_play(line));
  175.         }
  176.  
  177.         fclose(fp);
  178.         return head;
  179.     }
  180. }
  181.  
  182. struct artist *read_artists(char *fname) {
  183.     FILE *fp = fopen(fname, "r");
  184.     char line[BUFSIZE];
  185.     struct artist *head = NULL;
  186.  
  187.     if(fp == NULL) {
  188.         printf("Error: File not found\n");
  189.         return NULL;
  190.     } else {
  191.         while(!feof(fp)) {
  192.             if(fgets(line, BUFSIZE, fp) != NULL) head = add_artist(head, parse_artist(line));
  193.         }
  194.  
  195.         fclose(fp);
  196.         return head;
  197.     }
  198. }
  199.  
  200. int count_plays(struct play *head) {
  201.     int count = 0;
  202.  
  203.     while(head != NULL) {
  204.         count+=head->playcount;
  205.         head = head->next;
  206.     }
  207.     return count;
  208. }
  209.  
  210. struct play *filter_user(int user_id, struct play *head) {
  211.     struct play *filtered = NULL;
  212.     struct play *tempHead = head;
  213.  
  214.     while(head!=NULL) {
  215.         if(head->user_id==user_id) {
  216.             if(filtered==NULL) {
  217.                 filtered = create_play(head->user_id, head->artist_id, head->playcount);
  218.             } else {
  219.                 struct play *newp = create_play(head->user_id, head->artist_id, head->playcount);
  220.                 filtered = add_play(filtered, newp);
  221.             }
  222.         }
  223.  
  224.         head = head->next;
  225.     }
  226.     free_plays(tempHead);
  227.     return filtered;
  228. }
  229.  
  230. void free_plays(struct play *p) {
  231.     while(p != NULL) {
  232.         free(p);
  233.         p = p->next;
  234.     }
  235. }
  236.  
  237. void free_artists(struct artist *p) {
  238.     while(p != NULL) {
  239.         free(p);
  240.         p = p->next;
  241.     }
  242. }
  243.  
  244. struct play *merge_sort(struct play *x, struct play *y) {
  245.     struct play *tmp = NULL;
  246.     struct play *curr = NULL;
  247.     struct play *head = NULL;
  248.  
  249.     if(x == NULL) {
  250.         return y;
  251.     } else if(y == NULL) {
  252.         return x;
  253.     }
  254.  
  255.     while(x != NULL && y != NULL) {
  256.         // Swap x and y if x is smaller than y.
  257.         if(x->artist_id > y->artist_id) {
  258.             tmp = y;
  259.             y = x;
  260.             x = tmp;
  261.         }
  262.  
  263.         if(head == NULL) { // First element?
  264.             head = x;
  265.             curr = x;
  266.         } else {
  267.             curr->next = x;
  268.             curr = curr->next;
  269.         }
  270.         x = x->next;
  271.     }
  272.  
  273.     // Either x or y is empty.
  274.     if( x == NULL) {
  275.         curr->next = y;
  276.     } else {
  277.         curr->next = x;
  278.     }
  279.     return head;
  280. }
  281.  
  282. struct artist *merge_sort_artists(struct artist *x, struct artist *y, int criterion) {
  283.     struct artist *tmp = NULL;
  284.     struct artist *curr = NULL;
  285.     struct artist *head = NULL;
  286.  
  287.     if(x == NULL) {
  288.         return y;
  289.     } else if(y == NULL) {
  290.         return x;
  291.     }
  292.  
  293.     while(x != NULL && y != NULL) {
  294.         // Swap x and y if x is smaller than y.
  295.         if(criterion==PLAYCOUNT) {
  296.             if(x->playcount < y->playcount) {
  297.                 tmp = y;
  298.                 y = x;
  299.                 x = tmp;
  300.             }
  301.         } else if(criterion==ARTISTID) {
  302.             if(x->artist_id > y->artist_id) {
  303.                 tmp = y;
  304.                 y = x;
  305.                 x = tmp;
  306.             }
  307.         }
  308.  
  309.         if(head == NULL) { // First element?
  310.             head = x;
  311.             curr = x;
  312.         } else {
  313.             curr->next = x;
  314.             curr = curr->next;
  315.         }
  316.         x = x->next;
  317.     }
  318.  
  319.     // Either x or y is empty.
  320.     if( x == NULL) {
  321.         curr->next = y;
  322.     } else {
  323.         curr->next = x;
  324.     }
  325.     return head;
  326. }
  327.  
  328. struct play *find_middle(struct play *x) {
  329.     struct play *slow = x;
  330.     struct play *fast = x;
  331.  
  332.     while(fast->next != NULL && fast->next->next != NULL) {
  333.         slow = slow->next;
  334.         fast = fast->next->next;
  335.     }
  336.     return slow;
  337. }
  338.  
  339. struct artist *find_middle_artists(struct artist *x) {
  340.     struct artist *slow = x;
  341.     struct artist *fast = x;
  342.  
  343.     while(fast->next != NULL && fast->next->next != NULL) {
  344.         slow = slow->next;
  345.         fast = fast->next->next;
  346.     }
  347.     return slow;
  348. }
  349.  
  350. struct play *sort_plays(struct play *head) {
  351.     struct play *m = NULL;
  352.     struct play *x = NULL;
  353.     struct play *y = NULL;
  354.  
  355.     if (head == NULL || head->next == NULL) return head;
  356.  
  357.     x = head;
  358.     m = find_middle(head);
  359.     y = m->next;
  360.     m->next = NULL;
  361.  
  362.     return merge_sort(sort_plays(x), sort_plays(y));
  363. }
  364.  
  365. struct artist *sort_artists(struct artist *artist, int criterion) {
  366.     struct artist *m = NULL;
  367.     struct artist *x = NULL;
  368.     struct artist *y = NULL;
  369.  
  370.     if(artist == NULL || artist->next == NULL) return artist;
  371.     if(criterion!=0 && criterion!=1) {
  372.         printf("Error: Invalid criterion\n");
  373.         return artist;
  374.     }
  375.  
  376.     x = artist;
  377.     m = find_middle_artists(artist);
  378.     y = m->next;
  379.     m->next = NULL;
  380.  
  381.     return merge_sort_artists(sort_artists(x, criterion), sort_artists(y, criterion), criterion);
  382. }
  383.  
  384. struct artist *update_counts(struct artist *a, struct play *p) {
  385.     struct artist *head = a;
  386.  
  387.     while(a!=NULL) {
  388.         while(a->artist_id == p->artist_id) {
  389.             a->playcount += p->playcount;
  390.             p = p->next;
  391.         }
  392.  
  393.         a = a->next;
  394.     }
  395.     return head;
  396. }
  397.  
  398. void exit_usage() {
  399.     printf("USAGE: query_plays file command\n"
  400.            "\n"
  401.            "where command is one of\n"
  402.            "\n"
  403.            "   p <userid>  prints plays, optionally limited to user.\n"
  404.            "   c <userid>  counts plays, optionally limited to user.\n");
  405.     exit(1);
  406. }
  407.  
  408. void test_task1() {
  409.     struct play *test_play = NULL;
  410.     print_play(test_play);
  411.     test_play = create_play(1,2,3);
  412.     print_play(test_play);
  413.     free_play(test_play);
  414. }
  415.  
  416. void test_task2() {
  417.     struct play *a = create_play(1,2,3);
  418.     struct play *b = create_play(4,5,6);
  419.     a = add_play(a, b);
  420.     a = add_play(a, NULL);
  421.     print_plays(a);
  422.     printf("There are %d plays in a.\n", count_plays(a));
  423. }
  424.  
  425. void test_b1(int argc, char **argv) {
  426.     char *filename;
  427.     char *user_filter;
  428.     int mode = 0;
  429.  
  430.     if(argc>4 || argc<3) {
  431.         printf("Error: Wrong number of arguments.\n");
  432.         return;
  433.     }
  434.     filename = argv[1];
  435.  
  436.     if(argv[2][0]=='c') {
  437.         mode = 0;
  438.     } else if(argv[2][0]=='p') {
  439.         mode = 1;
  440.     } else {
  441.         exit_usage();
  442.         return;
  443.     }
  444.     user_filter = argv[3];
  445.     struct play *a = read_plays(filename);
  446.  
  447.     if(user_filter==NULL) {
  448.         if(mode==0) {
  449.             printf("Total play count: %d.\n", count_plays(a));
  450.         } else if(mode==1) {
  451.             print_plays(a);
  452.         }
  453.     } else {
  454.         int filter = atoi(user_filter);
  455.         if(a!=NULL) {
  456.             if(mode==0) {
  457.                 a = filter_user(filter, a);
  458.                 printf("Total play count for %d: %d.\n", filter, count_plays(a));
  459.             } else if(mode==1) {
  460.                 print_plays(a);
  461.             }
  462.         }
  463.     }
  464.     test_task1();
  465.     test_task2();
  466. }
  467.  
  468. int main(int argc, char **argv) {
  469.     if(argc!=4) {
  470.         printf("Error: Wrong number of arguments\n");
  471.         return 0;
  472.     }
  473.  
  474.     int k = atoi(argv[1]), i;
  475.  
  476.     struct artist *a = read_artists(argv[2]);
  477.     a = sort_artists(a, ARTISTID);
  478.  
  479.     struct play *p = read_plays(argv[3]);
  480.     p = sort_plays(p);
  481.  
  482.     a = update_counts(a, p);
  483.     a = sort_artists(a, PLAYCOUNT);
  484.  
  485.     for(i=0; i<k; i++) {
  486.         print_artist(a);
  487.         a=a->next;
  488.     }
  489.  
  490.     return 0;
  491. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement