#include <pthread.h>
#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
#include <semaphore.h>

#define N 4

/* 
 * An example dependency graph.
 *
 * A -> B -> C and D -> C
 * B depends on A, C depends on B, and C depends on D
 *
 * Therefore, the only 3 possible outputs are
 *   ABDC
 *   ADBC
 *   DABC
 */
static int dependencies[N][N] = {
    { 0, 0, 0, 0 },
    { 1, 0, 0, 0 },
    { 0, 1, 0, 1 },
    { 0, 0, 0, 0 },
};

static void task_A(void) { printf("A"); }
static void task_B(void) { printf("B"); }
static void task_C(void) { printf("C"); }
static void task_D(void) { printf("D"); }

struct task_descriptor {
    int id;
    void (*my_task) (void);
};

static struct task_descriptor task_descriptor[] = {
    { .id = 0, .my_task = task_A },
    { .id = 1, .my_task = task_B },
    { .id = 2, .my_task = task_C },
    { .id = 3, .my_task = task_D },
};

/* A Fisher-Yates shuffle */
static void 
fisher_yates(uint8_t *deck, uint8_t n)
{
    for (int i = n-1; i > 0; i--) {
        int j = random() % (i+1);
        uint8_t tmp = deck[j];
        deck[j] = deck[i];
        deck[i] = tmp;
    }
}

/*************************************************************
 * Begin of region you can change 
 * Be sure to retain task_thread, however.
 */

static void *
task_thread(void *_td)
{
    struct task_descriptor *td = _td;
    /* Implement this function.
     * Each task needs to ensure that its dependent
     * tasks have executed, then execute `td->my_task`
     *
     * Different task_threads may need to coordinate
     * to achieve this.
     */

    return NULL;
}

int
main()
{

/* End of region you can change 
*************************************************************/
    srand(getpid());

    // Note: shuffling the starting order of these threads
    // is not required to produced nondeterminism.  It
    // merely amplifies it.  Even with this shuffle, the
    // 4 task threads are under the control of the scheduler
    // which provides no guarantees about the order in which
    // they execute. 
    uint8_t start[4] = {0, 1, 2, 3};
    fisher_yates(start, 4);

    pthread_t t[N];
    for (int i = 0; i < N; i++)
        pthread_create(&t[i], NULL, task_thread, 
                       task_descriptor + start[i]);

    for (int i = 0; i < N; i++)
        pthread_join(t[i], NULL);

    printf ("\n");
    return 0;
}