Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define NAMELEN 64
- #define BUFSIZE 100
- #define PLAYCOUNT 0
- #define ARTISTID 1
- struct play {
- int user_id;
- int artist_id;
- int playcount;
- struct play *next;
- };
- struct artist {
- int artist_id;
- char artist_name[NAMELEN];
- int playcount;
- int alt_id;
- struct artist *next;
- };
- void print_play(struct play *p);
- void print_plays(struct play *p);
- struct play *create_play(int id, int artist_id, int playcount);
- struct play *parse_play(char *line);
- struct play *read_plays(char *file_name);
- struct play *add_play(struct play *head, struct play *newp);
- struct play *filter_user(int user_id, struct play *head);
- int count_plays(struct play *head);
- void free_plays(struct play *p);
- void free_play(struct play *p);
- void print_artist(struct artist *p);
- void print_artists(struct artist *p);
- struct artist *create_artist(int artist_id, char *name);
- struct artist *read_artists(char *fname);
- struct artist *add_artist(struct artist *head, struct artist *newp);
- void free_artists(struct artist *p);
- void free_artist(struct artist *p);
- struct artist *parse_artist(char *line);
- struct play *sort_plays(struct play *head);
- struct play *merge_sort(struct play *x, struct play *y);
- struct play *find_middle(struct play *x);
- struct artist *sort_artists(struct artist *artist, int criterion);
- struct artist *merge_sort_artists(struct artist *x, struct artist *y, int criterion);
- struct artist *find_middle_artists(struct artist *x);
- struct artist *update_counts(struct artist *a, struct play *p);
- void print_play(struct play *p) {
- if(p==NULL) {
- printf("NULL\n");
- return;
- }
- printf("user: %d artist: %d count: %d\n", p->user_id, p->artist_id, p->playcount);
- }
- void print_artist(struct artist *p) {
- if(p==NULL) {
- printf("NULL\n");
- return;
- }
- printf("%s (%d) [%d]\n", p->artist_name, p->artist_id, p->playcount);
- }
- struct play *create_play(int id, int artist_id, int playcount) {
- struct play *newp = (struct play *)malloc(sizeof(struct play));
- if(newp!=NULL) {
- newp->user_id = id;
- newp->artist_id = artist_id;
- newp->playcount = playcount;
- return newp;
- } else {
- printf("Error: play memory allocation failure\n");
- free(newp);
- exit(0);
- }
- return NULL;
- }
- struct artist *create_artist(int artist_id, char *name) {
- struct artist *newp = (struct artist *)malloc(sizeof(struct artist));
- if(newp!=NULL) {
- newp->artist_id = artist_id;
- strcpy(newp->artist_name, name);
- return newp;
- } else {
- printf("Error: artist memory allocation failure\n");
- free(newp);
- exit(0);
- }
- return NULL;
- }
- struct play *parse_play(char *line) {
- int u, a, c;
- if(sscanf(line, "%d %d %d\n", &u, &a, &c) == 3) {
- return create_play(u, a, c);
- } else {
- return NULL;
- }
- }
- struct artist *parse_artist(char *line) {
- char name[NAMELEN]; int a;
- if(sscanf(line, "%d\t%65[^\t\n]\n", &a, name) == 2) {
- return create_artist(a, name);
- } else {
- return NULL;
- }
- }
- void free_play(struct play *p) {
- free(p);
- }
- void free_artist(struct artist *p) {
- free(p);
- }
- struct play *add_play(struct play *head, struct play *newp) {
- if(newp==NULL) return head;
- newp->next = head;
- return newp;
- }
- struct artist *add_artist(struct artist *head, struct artist *newp) {
- if(newp==NULL) return head;
- newp->next = head;
- return newp;
- }
- void print_plays(struct play *p) {
- while(p != NULL) {
- print_play(p);
- p = p->next;
- }
- }
- void print_artists(struct artist *p) {
- while(p != NULL) {
- print_artist(p);
- p = p->next;
- }
- }
- struct play *read_plays(char *file_name) {
- FILE *fp = fopen(file_name, "r");
- char line[BUFSIZE];
- struct play *head = NULL;
- if(fp == NULL) {
- printf("Error: File not found\n");
- return NULL;
- } else {
- while(!feof(fp)) {
- if(fgets(line, BUFSIZE, fp) != NULL) head = add_play(head, parse_play(line));
- }
- fclose(fp);
- return head;
- }
- }
- struct artist *read_artists(char *fname) {
- FILE *fp = fopen(fname, "r");
- char line[BUFSIZE];
- struct artist *head = NULL;
- if(fp == NULL) {
- printf("Error: File not found\n");
- return NULL;
- } else {
- while(!feof(fp)) {
- if(fgets(line, BUFSIZE, fp) != NULL) head = add_artist(head, parse_artist(line));
- }
- fclose(fp);
- return head;
- }
- }
- int count_plays(struct play *head) {
- int count = 0;
- while(head != NULL) {
- count+=head->playcount;
- head = head->next;
- }
- return count;
- }
- struct play *filter_user(int user_id, struct play *head) {
- struct play *filtered = NULL;
- struct play *tempHead = head;
- while(head!=NULL) {
- if(head->user_id==user_id) {
- if(filtered==NULL) {
- filtered = create_play(head->user_id, head->artist_id, head->playcount);
- } else {
- struct play *newp = create_play(head->user_id, head->artist_id, head->playcount);
- filtered = add_play(filtered, newp);
- }
- }
- head = head->next;
- }
- free_plays(tempHead);
- return filtered;
- }
- void free_plays(struct play *p) {
- while(p != NULL) {
- free(p);
- p = p->next;
- }
- }
- void free_artists(struct artist *p) {
- while(p != NULL) {
- free(p);
- p = p->next;
- }
- }
- struct play *merge_sort(struct play *x, struct play *y) {
- struct play *tmp = NULL;
- struct play *curr = NULL;
- struct play *head = NULL;
- if(x == NULL) {
- return y;
- } else if(y == NULL) {
- return x;
- }
- while(x != NULL && y != NULL) {
- // Swap x and y if x is smaller than y.
- if(x->artist_id > y->artist_id) {
- tmp = y;
- y = x;
- x = tmp;
- }
- if(head == NULL) { // First element?
- head = x;
- curr = x;
- } else {
- curr->next = x;
- curr = curr->next;
- }
- x = x->next;
- }
- // Either x or y is empty.
- if( x == NULL) {
- curr->next = y;
- } else {
- curr->next = x;
- }
- return head;
- }
- struct artist *merge_sort_artists(struct artist *x, struct artist *y, int criterion) {
- struct artist *tmp = NULL;
- struct artist *curr = NULL;
- struct artist *head = NULL;
- if(x == NULL) {
- return y;
- } else if(y == NULL) {
- return x;
- }
- while(x != NULL && y != NULL) {
- // Swap x and y if x is smaller than y.
- if(criterion==PLAYCOUNT) {
- if(x->playcount < y->playcount) {
- tmp = y;
- y = x;
- x = tmp;
- }
- } else if(criterion==ARTISTID) {
- if(x->artist_id > y->artist_id) {
- tmp = y;
- y = x;
- x = tmp;
- }
- }
- if(head == NULL) { // First element?
- head = x;
- curr = x;
- } else {
- curr->next = x;
- curr = curr->next;
- }
- x = x->next;
- }
- // Either x or y is empty.
- if( x == NULL) {
- curr->next = y;
- } else {
- curr->next = x;
- }
- return head;
- }
- struct play *find_middle(struct play *x) {
- struct play *slow = x;
- struct play *fast = x;
- while(fast->next != NULL && fast->next->next != NULL) {
- slow = slow->next;
- fast = fast->next->next;
- }
- return slow;
- }
- struct artist *find_middle_artists(struct artist *x) {
- struct artist *slow = x;
- struct artist *fast = x;
- while(fast->next != NULL && fast->next->next != NULL) {
- slow = slow->next;
- fast = fast->next->next;
- }
- return slow;
- }
- struct play *sort_plays(struct play *head) {
- struct play *m = NULL;
- struct play *x = NULL;
- struct play *y = NULL;
- if (head == NULL || head->next == NULL) return head;
- x = head;
- m = find_middle(head);
- y = m->next;
- m->next = NULL;
- return merge_sort(sort_plays(x), sort_plays(y));
- }
- struct artist *sort_artists(struct artist *artist, int criterion) {
- struct artist *m = NULL;
- struct artist *x = NULL;
- struct artist *y = NULL;
- if(artist == NULL || artist->next == NULL) return artist;
- if(criterion!=0 && criterion!=1) {
- printf("Error: Invalid criterion\n");
- return artist;
- }
- x = artist;
- m = find_middle_artists(artist);
- y = m->next;
- m->next = NULL;
- return merge_sort_artists(sort_artists(x, criterion), sort_artists(y, criterion), criterion);
- }
- struct artist *update_counts(struct artist *a, struct play *p) {
- struct artist *head = a;
- while(a!=NULL) {
- while(a->artist_id == p->artist_id) {
- a->playcount += p->playcount;
- p = p->next;
- }
- a = a->next;
- }
- return head;
- }
- void exit_usage() {
- printf("USAGE: query_plays file command\n"
- "\n"
- "where command is one of\n"
- "\n"
- " p <userid> prints plays, optionally limited to user.\n"
- " c <userid> counts plays, optionally limited to user.\n");
- exit(1);
- }
- void test_task1() {
- struct play *test_play = NULL;
- print_play(test_play);
- test_play = create_play(1,2,3);
- print_play(test_play);
- free_play(test_play);
- }
- void test_task2() {
- struct play *a = create_play(1,2,3);
- struct play *b = create_play(4,5,6);
- a = add_play(a, b);
- a = add_play(a, NULL);
- print_plays(a);
- printf("There are %d plays in a.\n", count_plays(a));
- }
- void test_b1(int argc, char **argv) {
- char *filename;
- char *user_filter;
- int mode = 0;
- if(argc>4 || argc<3) {
- printf("Error: Wrong number of arguments.\n");
- return;
- }
- filename = argv[1];
- if(argv[2][0]=='c') {
- mode = 0;
- } else if(argv[2][0]=='p') {
- mode = 1;
- } else {
- exit_usage();
- return;
- }
- user_filter = argv[3];
- struct play *a = read_plays(filename);
- if(user_filter==NULL) {
- if(mode==0) {
- printf("Total play count: %d.\n", count_plays(a));
- } else if(mode==1) {
- print_plays(a);
- }
- } else {
- int filter = atoi(user_filter);
- if(a!=NULL) {
- if(mode==0) {
- a = filter_user(filter, a);
- printf("Total play count for %d: %d.\n", filter, count_plays(a));
- } else if(mode==1) {
- print_plays(a);
- }
- }
- }
- test_task1();
- test_task2();
- }
- int main(int argc, char **argv) {
- if(argc!=4) {
- printf("Error: Wrong number of arguments\n");
- return 0;
- }
- int k = atoi(argv[1]), i;
- struct artist *a = read_artists(argv[2]);
- a = sort_artists(a, ARTISTID);
- struct play *p = read_plays(argv[3]);
- p = sort_plays(p);
- a = update_counts(a, p);
- a = sort_artists(a, PLAYCOUNT);
- for(i=0; i<k; i++) {
- print_artist(a);
- a=a->next;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement