#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include "numbers.h"
#include "bintree.h"

static int compareUnsigned(const void *a, const void *b)
{
    unsigned int va = *(const unsigned int *)a;
    unsigned int vb = *(const unsigned int *)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}

// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
// Returns NULL on errors. Use your implementation of the binary search tree to check for possible duplicates while
// creating random numbers.
unsigned int *createNumbers(unsigned int len)
{
    if (len < 2) return NULL;

    unsigned int *arr = (unsigned int *)malloc(len * sizeof(unsigned int));
    if (arr == NULL) return NULL;

    TreeNode *root = NULL;
    /* create len-1 unique values in range [1, 2*len] */
    srand((unsigned int)time(NULL));

    while (treeSize(root) < len - 1) {
        unsigned int v = (unsigned int)(rand() % (2 * len)) + 1;
        int isDup = 0;
        TreeNode *newRoot = addToTree(root, &v, sizeof(unsigned int), compareUnsigned, &isDup);
        if (newRoot == NULL && root != NULL) { // allocation failed
            clearTree(root);
            free(arr);
            return NULL;
        }
        root = newRoot;
        /* if duplicate, addToTree left tree unchanged; loop continues */
    }

    /* extract values from tree (in-order) into arr[0..len-2] */
    unsigned int idx = 0;
    void *data = nextTreeData(root); // initializes iterator
    while (data != NULL && idx < len - 1) {
        arr[idx++] = *(unsigned int *)data;
        data = nextTreeData(NULL);
    }

    if (idx != len - 1) {
        clearTree(root);
        free(arr);
        return NULL;
    }

    /* pick a random existing index and duplicate it */
    unsigned int dupIndex = (unsigned int)(rand() % (len - 1));
    arr[len - 1] = arr[dupIndex];

    /* free tree memory */
    clearTree(root);

    /* shuffle array */
    for (unsigned int i = len - 1; i > 0; --i) {
        unsigned int j = (unsigned int)(rand() % (i + 1));
        unsigned int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    return arr;
}

// Returns only the only number in numbers which is present twice. Returns zero on errors.
unsigned int getDuplicate(const unsigned int numbers[], unsigned int len)
{
    if (numbers == NULL || len < 2) return 0;

    TreeNode *root = NULL;
    for (unsigned int i = 0; i < len; ++i) {
        unsigned int v = numbers[i];
        int isDup = 0;
        TreeNode *newRoot = addToTree(root, &v, sizeof(unsigned int), compareUnsigned, &isDup);
        if (newRoot == NULL && root != NULL) { // allocation failed
            clearTree(root);
            return 0;
        }
        root = newRoot;
        if (isDup) {
            clearTree(root);
            return v;
        }
    }

    clearTree(root);
    return 0;
}