#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <unistd.h>
#include <fcntl.h>
#include <math.h>
#include <string.h>

#include "float_vec.h"
#include "barrier.h"
#include "utils.h"


// stackoverflow assisted with pointer arithmetic.
// I knew I had to subtract a from b, but didn't know that
// I had to cast to int* from void*
int
compare_function(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

void
qsort_floats(floats* xs)
{
    // TODO: call qsort to sort the array
    // see "man 3 qsort" for details
    qsort(xs->data, xs->size, sizeof(float), compare_function);
}

floats*
sample(float* data, long size, int P)
{
    // TODO: sample the input data, per the algorithm decription
    int array_size = 3 * (P - 1);
    float sorted_array[array_size];
    (void) sorted_array; // suppress unused warning

    floats* samps = make_floats(0);
    floats_push(samps, 0);

    for (int i = 0; i < P - 1; i++) {
        floats* temp = make_floats(0);
        for (int j = 0; j < 3; j++) {
            floats_push(temp, data[random() % size]);
        }
        qsort (temp->data, 3, sizeof(float), compare_function);
        floats_push(samps, temp->data[1]);
    }

    floats_push(samps, INFINITY);

    qsort(samps->data, P + 1, sizeof(float), compare_function);


    return samps;
}

void
sort_worker(int pnum, float* data, long size, int P, floats* samps, long* sizes, barrier* bb)
{
    floats* xs = make_floats(0);
    // TODO: select the floats to be sorted by this worker
    float low = samps->data[pnum];
    float high = samps->data[pnum + 1];

    for (int i = 0; i < size; i++) {
        if (data[i] >= low && data[i] < high) {
            floats_push(xs, data[i]);
        }
    }

    sizes[pnum] = xs->size;

    printf("%d: start %.04f, count %ld\n", pnum, samps->data[pnum], xs->size);

    // TODO: some other stuff

    qsort_floats(xs);

    // TODO: probably more stuff
    barrier_wait(bb);

    int start = 0;
    int end = 0;

    for (int i = 0; i < pnum; i++) {
        start += sizes[i];
        end += sizes[i];
    }
    end += sizes[pnum];
    int index = 0;
    for (int i = start; i < end; i++) {
        data[i] = xs->data[index];
        index++;
    }

    free_floats(xs);
}

void
run_sort_workers(float* data, long size, int P, floats* samps, long* sizes, barrier* bb)
{
    pid_t kids[P];
    (void) kids; // suppress unused warning

    // TODO: spawn P processes, each running sort_worker

    for (int i = 0; i < P; i++) {
        // parent process
        if ((kids[i] = fork())) {
        }
        else {
            // child process
            sort_worker(i, data, size, P, samps, sizes, bb);
            exit(0);
        }
    }
    for (int i = 0; i < P; i++) {
        int rv = waitpid(kids[i], 0, 0);
        check_rv(rv);
    }
}

void
sample_sort(float* data, long size, int P, long* sizes, barrier* bb)
{
    floats* samps = sample(data, size, P);
    run_sort_workers(data, size, P, samps, sizes, bb);
    free_floats(samps);
}

int
main(int argc, char* argv[])
{
    if (argc != 3) {
        printf("Usage:\n");
        printf("\t%s P data.dat\n", argv[0]);
        return 1;
    }

    const int P = atoi(argv[1]);
    const char* fname = argv[2];

    seed_rng();

    int rv;
    struct stat st;
    rv = stat(fname, &st);
    check_rv(rv);

    const int fsize = st.st_size;
    if (fsize < 8) {
        printf("File too small.\n");
        return 1;
    }

    int fd = open(fname, O_RDWR);
    check_rv(fd);

    void* file = mmap(NULL, fsize, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); // TODO: load the file with mmap.
    (void) file; // suppress unused warning.

    // TODO: These should probably be from the input file.
    long count;
    memcpy(&count, file, sizeof(long));
    float* data = file + sizeof(long);

    long sizes_bytes = P * sizeof(long);
    long* sizes = mmap(0, sizes_bytes, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0); // TODO: This should be shared

    barrier* bb = make_barrier(P);

    sample_sort(data, count, P, sizes, bb);

    free_barrier(bb);

    // TODO: munmap your mmaps
    check_rv(munmap(file, fsize));
    check_rv(munmap(sizes, sizes_bytes));

    return 0;
}