#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUM_LENGTH 1000000
#define SINGLE_THREAD_SRTH 1000
#define MAX_LINE_LENGTH 10

// The great thing about qsort is that by logic there is no data race!
// We don't even need mutexes to protect data.

int *numbers;

// LST_QSORT_IMPL
struct ThreadArgs {
    int low;
    int high;
};

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

// Returns the index of pivot in arr[].
int partition(int low, int high) {
    int pivot = numbers[high]; // Pivot element
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (numbers[j] < pivot) {
            i++;
            swap(&numbers[i], &numbers[j]);
        }
    }

    swap(&numbers[i + 1], &numbers[high]);
    return i + 1;
}

// Used for list less than 1000 in length.
void qsort_nothread(int low, int high) {
    if (low >= high) {
        return;
    }

    int pivot_idx = partition(low, high);
    qsort_nothread(low, pivot_idx - 1);
    qsort_nothread(pivot_idx + 1, high);
}

void *qsort_thread(void *arg) {
    struct ThreadArgs *args = (struct ThreadArgs *)arg;
    // printf("Low: %d, high: %d\n", args->low, args->high);
    if (args->high - args->low <= SINGLE_THREAD_SRTH) {
        qsort_nothread(args->low, args->high);
        return NULL;
    }

    int pivot_idx = partition(args->low, args->high);
    struct ThreadArgs left_thd_arg = {.low = args->low, .high = pivot_idx - 1};
    struct ThreadArgs right_thd_arg = {.low = pivot_idx + 1,
                                       .high = args->high};
    pthread_t left_handle, right_handle;
    pthread_create(&left_handle, NULL, qsort_thread, (void *)&left_thd_arg);
    pthread_create(&right_handle, NULL, qsort_thread, (void *)&right_thd_arg);
    pthread_join(left_handle, NULL);
    pthread_join(right_handle, NULL);
}
// LST_QSORT_IMPL

// LST_MAIN_FUNC
void do_qsort() {
    struct ThreadArgs arg = {.low = 0, .high = NUM_LENGTH - 1};
    qsort_thread(&arg);
}

int main() {
    printf("Start reading file...\n");
    numbers = malloc(sizeof(int) * NUM_LENGTH);
    if (!numbers) {
        printf("Failed to allocate memory");
        return 1;
    }

    FILE *file = fopen("numbers.txt", "r");
    if (!file) {
        printf("Failed to open numbers file");
        return 1;
    }

    int count = 0;
    char line[MAX_LINE_LENGTH];
    while (count < NUM_LENGTH && fgets(line, sizeof(line), file)) {
        // printf("Count: %d\n", count);
        sscanf(line, "%d", &numbers[count]);
        count++;
    }

    fclose(file);
    printf("Start sorting...\n");
    do_qsort();
    printf("Done sorting, writing to file...\n");

    file = fopen("sorted.txt", "w");
    if (!file) {
        printf("Filed to open sorted file");
        return 1;
    }

    count = 0;
    while (count < NUM_LENGTH) {
        fprintf(file, "%d\n", numbers[count]);
        count++;
    }
    fclose(file);
    return 0;
}
// LST_MAIN_FUNC