#include <stdio.h>

// written by andrewt@unsw.ed.au as a COMP1511 lab solution

double grades2labmark(char grades[]);

int
main(int argc, char *argv[]) {
    if (argc == 2) {
        printf("%.1lf\n", grades2labmark(argv[1]));
        return 0;
    } else {
        fprintf(stderr, "Usage: %s <lab-grade>\n", argv[0]);
        return 1;
    }
}

// give a string of COMP1511 grades:  "BCAA..BAA+A+."
// calculate a lab mark on this basis
// A+ -> 1.25
// A -> 1.1
// B -> 0.8
// C -> 0.5
// . -> 0.0
// total mark is capped at

double grades2labmark(char grades[]) {
    double lab_mark = 0;

    int i = 0;
    while (grades[i] != '\0') {
        if (grades[i] == 'A') {
            if (grades[i + 1] == '+') {
                lab_mark += 1.25; // A+
                i++;
            } else {
                lab_mark += 1.1; // A
            }
        } else if (grades[i] == 'B') {
            lab_mark += 0.8;
        } else if (grades[i] == 'C') {
            lab_mark += 0.5;
        } else if (grades[i] == '.') {
        } else {
            fprintf(stderr, "Warning: unexpected character in grade string: '%c'\n", grades[i]);
        }
        i++;
    }

    if (lab_mark > 10) {
        lab_mark = 10;
    }
    return lab_mark;
}

// modified by andrewt@unsw.ed.au as a COMP1511 lab solution
// from work by Mark Sonnenschein & Alex Linker

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

#define MAX_STUDENT_NAME_LENGTH 128
#define MAX_GRADE_STRING_LENGTH 22
#define MAX_LAB_NAME_LENGTH 32
#define MAX_LINE_LENGTH 4096

struct student {
    int              zid;
    char             name[MAX_STUDENT_NAME_LENGTH + 1];
    char             lab_name[MAX_LAB_NAME_LENGTH + 1];
    char             lab_grades[MAX_GRADE_STRING_LENGTH + 1];
    struct student   *next;
};

void print_students_from_lab(struct student *first, char *lab_name);
struct student *read_students_file(char filename[]);
struct student *read_student(FILE *stream);
double grades2labmark(char grades[]);
void free_students(struct student *head);

int main(int argc, char *argv[]) {

    if (argc != 3) {
        fprintf(stderr, "Usage: %s <marks-file> <lab-name>\n", argv[0]);
        return 1;
    }

    struct student *student_list = read_students_file(argv[1]);
    print_students_from_lab(student_list, argv[2]);

    free_students(student_list);
    return EXIT_SUCCESS;
}

void print_students_from_lab(struct student *first, char *lab_name) {
    for (struct student *s = first; s != NULL; s = s->next) {
        if (strcmp(s->lab_name,lab_name) == 0) {
            printf("%d %-30s %-12s %-22s %4.1lf\n", s->zid, s->name, s->lab_name, s->lab_grades, grades2labmark(s->lab_grades) );
        }
    }
}

// read_students_file reads a file where line contains information for 1 student
// it creates a linked of student structs containing the information
// it returns a pointer to the head of the list

struct student *read_students_file(char filename[]) {
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        fprintf(stderr,"warning file %s could not  be opened for reading\n", filename);
        return NULL;
    }

    struct student *first_student = NULL;
    struct student *last_student = NULL;
    struct student *s;
    while ((s = read_student(fp)) != NULL) {
        if (last_student == NULL) {
            first_student = s;
            last_student = s;
        } else {
            last_student->next = s;
            last_student = s;
        }
    }

    fclose(fp);
    return first_student;
}


// read_student mallocs a student struct
// and reads a line in this format:
//
// 5099703 Tsun Bordignon                 thu13-sitar  A+A+CABAB..A.           7.8
//
// stores the values in the struct field
// and returns a pointer to the struct

struct student *read_student(FILE *stream) {
    char line[MAX_LINE_LENGTH];

    struct student *s = malloc(sizeof (struct student));
    assert(s);

    if (fgets(line, MAX_LINE_LENGTH, stream) == NULL) {
        free(s);
        return NULL;
    }

    // truncate string at '\r' or '\n'
    line[strcspn(line, "\r\n")] = '\0';

    char *space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_grades, space_ptr + 1, MAX_GRADE_STRING_LENGTH);
    s->lab_grades[MAX_GRADE_STRING_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_name, space_ptr + 1, MAX_LAB_NAME_LENGTH);
    s->lab_name[MAX_LAB_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strchr(line, ' ');
    assert(space_ptr);
    strncpy(s->name, space_ptr + 1, MAX_STUDENT_NAME_LENGTH);
    s->name[MAX_STUDENT_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    s->zid = atoi(line);
    s->next = NULL;
    return s;
}

// give a string of COMP1511 grades:  "BCAA..BAA+A+."
// calculate a lab mark on this basis
// A+ -> 1.2
// A -> 1
// B -> 0.8
// C -> 0.5
// . -> 0.0
// total mark is capped at

double grades2labmark(char grades[]) {
    double lab_mark = 0;

    int i = 0;
    while (grades[i] != '\0') {
        if (grades[i] == 'A') {
            if (grades[i + 1] == '+') {
                lab_mark += 1.25; // A+
                i++;
            } else {
                lab_mark += 1.1; // A
            }
        } else if (grades[i] == 'B') {
            lab_mark += 0.8;
        } else if (grades[i] == 'C') {
            lab_mark += 0.5;
        } else if (grades[i] == '.') {
        } else {
            fprintf(stderr, "Warning: unexpected character in grade string: '%c'\n", grades[i]);
        }
        i++;
    }

    if (lab_mark > 10) {
        lab_mark = 10;
    }
    return lab_mark;
}

// free memory allocated with malloc for all student
// structs in list

void free_students(struct student *head) {
    struct student *s = head;
    while (s != NULL)  {
        struct student *t = s->next;  // save a copy of s->next
        free(s);
        s = t;
    }
}

// modified by andrewt@unsw.ed.au as a COMP1511 lab solution
// from work by Mark Sonnenschein & Alex Linker

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

#define MAX_STUDENT_NAME_LENGTH 128
#define MAX_GRADE_STRING_LENGTH 22
#define MAX_LAB_NAME_LENGTH 32
#define MAX_LINE_LENGTH 4096

struct student {
    int              zid;
    char             name[MAX_STUDENT_NAME_LENGTH + 1];
    char             lab_name[MAX_LAB_NAME_LENGTH + 1];
    char             lab_grades[MAX_GRADE_STRING_LENGTH + 1];
    struct student   *next;
};

struct student * quicksort_students(struct student *head);
void partition(struct student *pivot, struct student *head, struct student **smaller, struct student **bigger);
int compare_student(struct student *s1, struct student *s2);
struct student *last(struct student *student);
void print_students(struct student *first);
struct student *read_students_file(char filename[]);
struct student *read_student(FILE *stream);
double grades2labmark(char grades[]);
void free_students(struct student *head);

int main(int argc, char *argv[]) {

    if (argc != 2) {
        fprintf(stderr, "Usage: %s <marks-file>\n", argv[0]);
        return 1;
    }

    struct student *student_list = read_students_file(argv[1]);
    student_list = quicksort_students(student_list);
    print_students(student_list);
    free_students(student_list);

    return EXIT_SUCCESS;
}

// return student list rearranged into sorted order
struct student *quicksort_students(struct student *head) {
    struct student *pivot = head;
    struct student *smaller;
    struct student *bigger;

    if (head == NULL) {
        return NULL;
    }

    partition(pivot, head->next, &smaller, &bigger);
    smaller = quicksort_students(smaller);
    bigger = quicksort_students(bigger);

    pivot->next = bigger;
    if (smaller == NULL) {
        return pivot;
    } else {
        last(smaller)->next = pivot;
        return smaller;
    }
}

// partition list of students point to by head,into 2 lists based on pivot
// *smaller is set to the list of student which should be ordered before the pivot student
// *larger is set to the list of student which should be ordered after the pivot student

void partition(struct student *pivot, struct student *head, struct student **smaller, struct student **bigger) {
    if (head == NULL) {
        *smaller = NULL;
        *bigger = NULL;
    } else {
        if (compare_student(pivot, head)) {
            *smaller = head;
            partition(pivot, head->next, &(head->next), bigger);
        } else {
            *bigger = head;
            partition(pivot, head->next, smaller, &(head->next));
        }
    }
}

// return 1 iff student s1 should be sorted before student s2, 0 otherwise
// students are sorted on last name, then first name, then zid

int compare_student(struct student *s1, struct student *s2) {
    char *space1 = strchr(s1->name, ' ');
    char *space2 = strchr(s2->name, ' ');
    assert(space1);
    assert(space2);
    int last_name_order = strcmp(space1 + 1, space2 + 1);
    if (last_name_order > 0) {
        return 1;
    } else if (last_name_order < 0) {
        return 0;
    }
    int first_name_order = strcmp(s1->name, s2->name);
    if (first_name_order > 0) {
        return 1;
    } else if (first_name_order < 0) {
        return 0;
    }
    return s1->zid > s2->zid;
}

// return last in list

struct student *last(struct student *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    return last(head->next);
}

// print all students with their lab_mark

void print_students(struct student *first) {
    for (struct student *s = first; s != NULL; s = s->next) {
        printf("%d %-30s %-12s %-22s %4.1lf\n", s->zid, s->name, s->lab_name, s->lab_grades, grades2labmark(s->lab_grades) );
    }
}

// read_students_file reads a file where line contains information for 1 student
// it creates a linked of student structs containing the information
// it returns a pointer to the head of the list

struct student *read_students_file(char filename[]) {
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        fprintf(stderr,"warning file %s could not  be opened for reading\n", filename);
        return NULL;
    }

    struct student *first_student = NULL;
    struct student *last_student = NULL;
    struct student *s;
    while ((s = read_student(fp)) != NULL) {
        if (last_student == NULL) {
            first_student = s;
            last_student = s;
        } else {
            last_student->next = s;
            last_student = s;
        }
    }

    fclose(fp);
    return first_student;
}


// read_student mallocs a student struct
// and reads a line in this format:
//
// 5099703 Tsun Bordignon                 thu13-sitar  A+A+CABAB..A.           7.8
//
// stores the values in the struct field
// and returns a pointer to the struct

struct student *read_student(FILE *stream) {
    char line[MAX_LINE_LENGTH];

    struct student *s = malloc(sizeof (struct student));
    assert(s);

    if (fgets(line, MAX_LINE_LENGTH, stream) == NULL) {
        free(s);
        return NULL;
    }

    // truncate string at '\r' or '\n'
    line[strcspn(line, "\r\n")] = '\0';

    char *space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_grades, space_ptr + 1, MAX_GRADE_STRING_LENGTH);
    s->lab_grades[MAX_GRADE_STRING_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_name, space_ptr + 1, MAX_LAB_NAME_LENGTH);
    s->lab_name[MAX_LAB_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strchr(line, ' ');
    assert(space_ptr);
    strncpy(s->name, space_ptr + 1, MAX_STUDENT_NAME_LENGTH);
    s->name[MAX_STUDENT_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    s->zid = atoi(line);
    s->next = NULL;
    return s;
}

// give a string of COMP1511 grades:  "BCAA..BAA+A+."
// calculate a lab mark on this basis
// A+ -> 1.2
// A -> 1
// B -> 0.8
// C -> 0.5
// . -> 0.0
// total mark is capped at

double grades2labmark(char grades[]) {
    double lab_mark = 0;

    int i = 0;
    while (grades[i] != '\0') {
        if (grades[i] == 'A') {
            if (grades[i + 1] == '+') {
                lab_mark += 1.25; // A+
                i++;
            } else {
                lab_mark += 1.1; // A
            }
        } else if (grades[i] == 'B') {
            lab_mark += 0.8;
        } else if (grades[i] == 'C') {
            lab_mark += 0.5;
        } else if (grades[i] == '.') {
        } else {
            fprintf(stderr, "Warning: unexpected character in grade string: '%c'\n", grades[i]);
        }
        i++;
    }

    if (lab_mark > 10) {
        lab_mark = 10;
    }
    return lab_mark;
}

// free memory allocated with malloc for all student
// structs in list

void free_students(struct student *head) {
    struct student *s = head;
    while (s != NULL)  {
        struct student *t = s->next;  // save a copy of s->next
        free(s);
        s = t;
    }
}

// Andrew Bennett <andrew.bennett@unsw.edu.au>
// COMP1511 Week 11, 17s1
// Prints the students from a given lab marks file in sorted order, using
// merge sort as a sorting algorithm.

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

#define MAX_STUDENT_NAME_LENGTH 128
#define MAX_GRADE_STRING_LENGTH 22
#define MAX_LAB_NAME_LENGTH 32
#define MAX_LINE_LENGTH 4096

struct student {
    int              zid;
    char             name[MAX_STUDENT_NAME_LENGTH + 1];
    char             lab_name[MAX_LAB_NAME_LENGTH + 1];
    char             lab_grades[MAX_GRADE_STRING_LENGTH + 1];
    struct student   *next;
};

struct student *read_students_file(char filename[]);
struct student *read_student(FILE *stream);
void print_students(struct student *student_list);
double get_lab_marks(char *grades);

// sorting functions -- see verbose comments below
struct student *sort_students(struct student* student_list);
struct student *mergesort(struct student *student_list);
struct student *split_middle(struct student *student_list);
struct student *merge(struct student *first, struct student *second);

// comparison and helper functions for dealing with student names
char *get_last_name(struct student *s);
int compare(struct student *s1, struct student *s2);

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <marks-file> labname\n", argv[0]);
        return 1;
    }

    struct student *student_list = read_students_file(argv[1]);
    if (student_list == NULL) {
        fprintf(stderr, "wat\n");
        return 1;
    }
    student_list = sort_students(student_list);
    print_students(student_list);

    return 0;
}

void print_students(struct student *student_list) {
    struct student *curr = student_list;
    while (curr != NULL) {
        printf("%d %-30s %-12s %-22s %4.1lf\n", curr->zid, curr->name, curr->lab_name, curr->lab_grades, get_lab_marks(curr->lab_grades));
        curr = curr->next;
    }
}

// A pretty generic "wrapper" function; earlier I was testing out a
// bubble sort, so having this meant it was very easy to swap between
// the two.
struct student *sort_students(struct student *student_list) {
    return mergesort(student_list);
}

// Merge sort the student list:
// Split the list in half, literally, by chopping the link between the two halves.
//
// Then, call mergesort on those two lists (thus splitting them in half, and their halves in half, ...),
// and merge the two sorted lists together.
struct student *mergesort(struct student *student_list) {
    struct student *first_half = student_list;
    struct student *second_half = split_middle(student_list);

    // If we only have a single element (the first half is the same as the second half),
    // then it's already sorted, so we don't need to do anything.
    if (first_half == second_half) {
        return first_half;
    }

    // otherwise, mergesort the first half, and the second half,
    // and then merge them together.
    first_half = mergesort(first_half);
    second_half = mergesort(second_half);

    return merge(first_half, second_half);
}

// Split the list into two lists, severing the link at the halfway point.
//
// This works by walking along the linked list using two pointers, a
// "fast" pointer and a "slow" pointer. The "fast" pointer walks along
// the list every loop iteration, and the "slow" pointer only moves along
// every second iteration.
//
// Once the "fast" pointer hits the end, the "slow" pointer will be
// halfway along. We can then cut the link between the middle and middle+1st
// nodes, and return the second half of the list as our split list.
//
// This works out fine, because we merge the lists back together later.

struct student *split_middle(struct student *student_list) {
    struct student *single_step = student_list;
    struct student *double_step = student_list;
    // a variable that alternates between 0 and 1, and determines
    // whether the "slow" pointer should progress forward.
    int toggle = 0;
    while (double_step->next != NULL) {
        if (toggle) {
            single_step = single_step->next;
        }
        // if toggle is 0, !0 = 1.
        // if toggle is 1, !1 = 0.
        // so, this causes the variable to "toggle".
        toggle = !toggle;
        double_step = double_step->next;
    }

    // Now that we've finished the loop, single_step is at the
    // halfway point.

    // If single_step is pointing to the same place as double_step,
    // then we only had a single node to begin with, so return
    // single_step (our "slow" pointer)
    if (single_step == double_step) {
        return single_step;
    }

    // Otherwise, our second half of the list starts at the element
    // after our "slow" pointer, so keep a reference to that, and
    // cut the link between them.
    struct student *next = single_step->next;
    single_step->next = NULL;
    return next;
}

// Merges two sorted lists into a single sorted list.
// Looks at the first element of each list, and moves the smaller element to
// a new list; then moves that list along to the next element, and compares again.
// eg: if the lists are
//
//   1 -> 3 -> 4 -> 10 -> X
//   2 -> 5 -> X
//
// It will start out looking at the 1 and the 2:
//   v (first)
//   1 -> 3 -> 4 -> 10 -> X
//   2 -> 5 -> X
//   ^ (second)
//
// since 1 is smaller than 2, 1 will be added to our new sorted list, and
// "first" will move along to the next node":
//        v (first)
//        3 -> 4 -> 10 -> X
//   2 -> 5 -> X
//   ^ (second)
// sorted list:
//   1 -> X
//
// Once one of the lists is NULL (or rather, once one of the lists has been completely
// merged into the new overall list), it appends the remaining list onto the end, as we
// know that there's nothing else left in the now-exhausted list, and we know that the
// remaining list is in sorted order.
struct student *merge(struct student *first, struct student *second) {
    // the head of our new merged list
    struct student *head = NULL;
    // the node we're currently up to (at the end of) our new merged list
    struct student *upto = NULL;

    // while there are still nodes in *both* lists:
    while (first != NULL && second != NULL) {
        struct student *smallest;
        // avoid code duplication: work out which is smallest, then deal with edge cases
        if (compare(first, second) <= 0) {
            smallest = first;
            first = first->next;
        } else {
            smallest = second;
            second = second->next;
        }
        // deal with the edge cases:
        // if head is NULL, then this is the very first node, so set head to point to it.
        if (head == NULL) {
            head = smallest;
            upto = head;
        } else {
            upto->next = smallest;
            upto = upto->next;
        }
    }

    // at this point, either first is null, second is null, or both are null.
    if (first != NULL) {
        // insert everything from first onwards
        upto->next = first;
    } else if (second != NULL) {
        // insert verything from second onwards
        upto->next = second;
    }
    return head;
}

// Returns a pointer to the student's surname.
// Calls strchr to get a pointer to the space between the names,
// then returns a pointer that points one past that (i.e. to the
// start of the surname)
char *get_last_name(struct student *s) {
    return strchr(s->name, ' ') + 1;
}


// Compares two students, and returns whether the first student should be placed
// before (negative value), or after (positive value) the second student.
// If the students are the same, the function will return 0.
//
// Students are compared based on last name, then first name, then zid.
int compare(struct student *s1, struct student *s2) {
    char *s1_last_name = get_last_name(s1);
    char *s2_last_name = get_last_name(s2);

    // 0 means they're the same, -1 means n1 < n2, +1 means n1 > n2
    int surname_compare = strcmp(s1_last_name, s2_last_name);

    // If the surnames are the same:
    if (surname_compare == 0) {
        // Compare by first name:
        int firstname_compare = strcmp(s1->name, s2->name);
        // If *those* are the same, compare based on zid.
        if (firstname_compare == 0) {
            return s1->zid - s2->zid;
        }
        return firstname_compare;
    }
    return surname_compare;
}

// return the smaller of two given values
double min(double a, double b) {
    if (a < b) {
        return a;
    }
    return b;
}

// calculate lab marks, according to the given scheme.
double get_lab_marks (char *grades) {
    int upto = 0;
    double mark = 0.0;
    while (grades[upto] != '\0') {
        switch (grades[upto]) {
            case 'A':
                mark += 1.1;
                break;
            case 'B':
                mark += 0.8;
                break;
            case 'C':
                mark += 0.5;
                break;
            case '+':
                mark += 0.15;
                break;
        }
        upto += 1;
    }
    // return the smallest of their actual mark, or 10.0 (i.e. cap their lab mark at 10.0).
    return min(mark, 10.0);
}

// DO NOT CHANGE THE CODE BELOW HERE - DO NOT CHANGE read_students_file

// read_students_file reads a file where line contains information for 1 student
// it creates a linked of student structs containing the information
// it returns a pointer to the head of the list

struct student *read_students_file(char filename[]) {
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        fprintf(stderr,"warning file %s could not  be opened for reading\n", filename);
        return NULL;
    }

    struct student *first_student = NULL;
    struct student *last_student = NULL;
    struct student *s;
    while ((s = read_student(fp)) != NULL) {
        if (last_student == NULL) {
            first_student = s;
            last_student = s;
        } else {
            last_student->next = s;
            last_student = s;
        }
    }
    return first_student;
}

// DO NOT CHANGE read_student

// read_student mallocs a student struct
// and reads a line in this format:
//
// 5099703 Tsun Bordignon thu13-sitar A+A+CABAB..A.
//
// stores the values in the struct field
// and returns a pointer to the struct

struct student *read_student(FILE *stream) {
    char line[MAX_LINE_LENGTH];

    struct student *s = malloc(sizeof (struct student));
    assert(s);

    if (fgets(line, MAX_LINE_LENGTH, stream) == NULL) {
        free(s);
        return NULL;
    }

    char *newline_ptr = strchr(line, '\n');
    assert(newline_ptr);
    *newline_ptr = '\0';

    char *space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_grades, space_ptr + 1, MAX_GRADE_STRING_LENGTH);
    s->lab_grades[MAX_GRADE_STRING_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strrchr(line, ' ');
    assert(space_ptr);
    strncpy(s->lab_name, space_ptr + 1, MAX_LAB_NAME_LENGTH);
    s->lab_name[MAX_LAB_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    space_ptr = strchr(line, ' ');
    assert(space_ptr);
    strncpy(s->name, space_ptr + 1, MAX_STUDENT_NAME_LENGTH);
    s->name[MAX_STUDENT_NAME_LENGTH] = '\0';
    *space_ptr = '\0';

    s->zid = atoi(line);
    s->next = NULL;
    return s;
}