// Jonas Altrock <ew20b126@technikum-wien.at>
//
// [To overview](../).
//
// [The whole source file `wordstats.c`.](./wordstats.c)
/* compile with `clang -std=c99 -Wall -o sort sort.c` */

// Include C-libraries for input/output, allocation of memory,
// and string manipulation.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ## Task
// Implement a sorting algorithm of your liking (do not use some already
// implemented sorting algorithm from some library) to sort words alphabetically
// (case-insensitive), then print all words sorted alphabetically.
//
// Read an arbitrary number of words (use `scanf`). Each word will consist of at
// most 63 characters and consists of upper-case and lower-case letters (A-Z and
// a-z, no other special characters). The list of words is always terminated by
// a “.” (which is not a valid word and thus should not be stored).
//
// After “.” was entered, print all words that were entered in alphabetical
// order. For this, it should not matter whether the word starts with an upper
// case or lower case letter.
//
// The word must be printed in the same way it was entered. In particular it is
// not allowed to convert upper-case letters to lower case letters. If the same
// word was entered twice, it should also be printed twice.
//
// You can use bubble sort to sort the elements or you can read up on other
// sorting algorithms for practice. In particular, selection sort is easy to
// implement. Quicksort is more complex but it is one of the fastest sorting
// algorithms.
//
// Make sure that you use a stable sorting algorithm (which means that elements
// that are equal do not change the position relative to each other.
// Selection Sort and Bubble Sort are stable).

// ### Solution
// We first declare functions for splitting up the problem into smaller parts.
/* */
// Compare two strings, not regarding upper- or lower-case characters.
int stricmp(const char *a, const char *b);
// Read all words into a table of strings. `table` is an out-parameter, which
// means the function will change it: it is the address of the variable
// which contains the table of words.
int read_words(char ***table);
// Free the dynamic memory of the table of words.
void free_words(char ***table, int words);
// Bubble sort the table.
void bubble_sort(char **table, int words);
// Stable version of quicksort.
void quicksort_stable(char **table, int words);
// In-place version of quicksort.
void quicksort_inplace(char **table, int from, int to);

// ### main()
int main(int argc, char **argv) {
    // Initialize the table of strings and read all the words into it.
    char **table;
    int words = read_words(&table);

    // Switch the sort algorithm with a command-line argument. <em>This is
    // completely unnecessary for this homework exercise</em>.
    // - invoking the program with `sort -b` will use bubble sort,
    // - invoking the program with `sort -i` will use the in-place quicksort,
    // - all other forms of invoking the program will use stable quicksort.
    if (argc > 1 && strcmp(argv[1], "-b") == 0) {
        bubble_sort(table, words);
    } else if (argc > 1 && strcmp(argv[1], "-i") == 0) {
        quicksort_inplace(table, 0, words - 1);
    } else {
        quicksort_stable(table, words);
    }

    // Print out the sorted table of words.
    for (int i = 0; i < words; i++) {
        printf("%s\n", table[i]);
    }

    // Free the dynamic memory.
    free_words(&table, words);
    return 0;
}

// ### swap()
// Swap two entries in the word list.
void swap(char **table, int a, int b) {
    char *tmp = table[a];
    table[a] = table[b];
    table[b] = tmp;
}

// ### bubble_sort()
// Bubble goes from left to right and compares each entry with the
// one following it, then swaps them if they are in the wrong order.
// This way, the elements "bubble up" to their correct position.
void bubble_sort(char **table, int words) {
    // `N - 1` times we need to bubble up, as for `N` elements, we can do
    // `N - 1` pair-wise comparisons.
    for (int i = 0; i < words - 1; i++) {
        // In each iteration, we have `i` correctly bubbled elements,
        // so we only have to sort through `0` to index `N - i`, which again,
        // means `N - i - 1` pair-wise comparisons.
        for (int j = 0; j < words - i - 1; j++) {
            // Swap if the next element is larger.
            int cmp = stricmp(table[j], table[j + 1]);
            if (cmp > 0) {
                swap(table, j, j + 1);
            }
        }
    }
}

// ### quicksort_stable()
// Stable sort a list of words with quicksort. Stable means that two values
// considered equal end up in the same order as in the original array.
void quicksort_stable(char **table, int words) {
    // This quicksort uses `2N*log(N)` extra space, similar to merge sort.
    //
    // The basic idea is to choose a pivot element, then partition all
    // items into things smaller or larger than this pivot, then recursively
    // sort these shorter lists, and finally stitch together the result
    // with concat [smaller] [pivot] [larger]. This is a classic divide
    // and conquer algorithm.
    /* */

    // Nothing to sort if list has less than 2 elements.
    if (words < 2) {
        return;
    }

    // N=2, check if swap is needed.
    if (words == 2) {
        int cmp = stricmp(table[0], table[1]);

        if (cmp > 0) {
            swap(table, 0, 1);
        }

        return;
    }

    // To make quicksort stable, sort everything < into before,
    // everything > into after, and == elements into before,
    // if they come before the pivot, after if they come after.
    // Choosing the last element as pivot makes this a bit easier,
    // because there are no elements that come after the pivot then.

    char *pivot = table[words - 1];
    // `before` and `after` can be maximally `words - 1` values.
    // We know our `N` is small so we do not mind that these temporary
    // arrays of strings are allocated on the local stack.
    char *before[words - 1];
    int beforeWords = 0;
    char *after[words - 1];
    int afterWords = 0;

    // For each word in the table (before the pivot), compare it to the pivot.
    for (int i = 0; i < words - 1; i++) {
        int cmp = stricmp(table[i], pivot);

        // If smaller or equal, sort it into the `before` list.
        if (cmp <= 0) {
            before[beforeWords] = table[i];
            beforeWords += 1;
        } else {
            // Else sort it into the `after` list.
            after[afterWords] = table[i];
            afterWords += 1;
        }
    }

    // Sort the sub-lists.
    quicksort_stable((char **) &before, beforeWords);
    quicksort_stable((char **) &after, afterWords);

    // Now reassign the sorted elements into the original table
    for (int i = 0; i < beforeWords; i++) {
        table[i] = before[i];
    }

    table[beforeWords] = pivot;

    for (int i = 0; i < afterWords; i++) {
        table[beforeWords + 1 + i] = after[i];
    }
}

// ### quicksort_inplace()
// Quicksort but without using additional space for partial arrays.
void quicksort_inplace(char **table, int from, int to) {
    // In-place quicksort swaps elements as many times as necessary to
    // achieve `[ <= ] p [ >= ]` in the original array.
    // Unfortunately, in-place quicksort is not stable.
    /* */

    // If there are <= 1 elements, no sorting is needed.
    if (to - from < 1) {
        return;
    }

    // Exactly two, then check if swap is needed.
    if (to - from == 1) {
        int cmp = stricmp(table[from], table[to]);

        if (cmp > 0) {
            swap(table, from, to);
        }

        return;
    }

    // First we pick a pivot element, choosing the last one.
    int pivot = to;

    // Then we partition the array in-place by keeping track of two pointers,
    // left and right, which start out at the ends of the range we want to
    // partition.
    int left = from;
    int right = pivot - 1;

    // Then we let both pointers move towards each other until they meet and
    // the whole array has been checked.
    while (right >= left) {
        // Each iteration we compare the right-most element of the unconsidered
        // range with the pivot, and either swap it with the pivot or to the
        // start of the unconsidered range.
        int cmp = stricmp(table[right], table[pivot]);

        // Swap < to the start of the range.
        if (cmp < 0) {
            if (left != right) {
                swap(table, left, right);
            }

            left += 1;
            continue;
        }

        // Swap > to the right of the pivot.
        if (cmp > 0) {

            swap(table, right, pivot);
            pivot = right;
            right = pivot - 1;
        }

        // If equal, only reduce unconsidered range.
        if (cmp == 0) {
            right -= 1;
        }
    }

    // In the end we get an array where everything that is < p is left of the
    // pivot, and everything > p is to the right of the pivot.
    // The equal elements will be either left or right from the pivot, depending
    // on the order of swaps. This is unstable sorting.
    //
    // The stability could be restored here by determining the range of equal
    // elements around pivot, then sorting them by a different criterion, say
    // memory address or some property that relates to the original positions.
    quicksort_inplace(table, from, pivot - 1);
    quicksort_inplace(table, pivot + 1, to);
}

// ### read_words()
// Read in words from stdin until we see a `.`.
int read_words(char ***table) {
    int size = 16;
    int words = 0;
    char *buffer = calloc(64, sizeof(char));
    *table = calloc(size, sizeof(char *));

    do {
        // Read in a word
        scanf("%s", buffer);

        // End if it is "."
        if (strcmp(".", buffer) == 0) {
            break;
        }

        // If adding it would overflow, reallocate bigger table.
        if (words == size) {
            size *= 2;
            *table = realloc(*table, size * sizeof(char*));
        }

        (*table)[words] = strdup(buffer);
        words += 1;
    } while(1);

    // Free the dynamic buffer.
    free(buffer);

    return words;
}

// ### free_words()
// Free the dynamic memory allocated by `read_words`.
void free_words(char ***table, int words) {
    // Free all individual words.
    for (int i = 0; i < words; i++) {
        free((*table)[i]);
        (*table)[i] = NULL;
    }

    // Free the table itself.
    free(*table);
    *table = NULL;
}

// ### stricmp()
// Case-insensitive string compare.
int stricmp(const char *a, const char *b) {
    int i = 0;

    // Loop through words until null-termination is reached, so only as long
    // as the shorter string.
    while (a[i] != '\0' || b[i] != '\0') {
        char A = a[i];

        // lowercase A
        if ((A >= 'A' && A <= 'Z')) {
            A += 32;
        }

        char B = b[i];

        // lowercase B
        if ((B >= 'A' && B <= 'Z')) {
            B += 32;
        }

        if (A == B) {
            i += 1;
            continue;
        }

        if (A < B) {
            return -1;
        }

        return 1;
    }

    return 0;
}
