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

// Hilfsfunktion für qsort und den Binärbaum: Vergleich von unsigned int
static int compareUnsignedInt(const void *a, const void *b)
{
    const unsigned int *ua = (const unsigned int *)a;
    const unsigned int *ub = (const unsigned int *)b;

    if (*ua < *ub)
        return -1;
    else if (*ua > *ub)
        return 1;
    else
        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 *numbers = malloc(len * sizeof(unsigned int));
    if (numbers == NULL)
        return NULL;

    // Zufall initialisieren
    srand((unsigned int)time(NULL));

    TreeNode *root = NULL;
    unsigned int i = 0;

    // len-1 verschiedene Zufallszahlen im Bereich [1, 2*len] erzeugen
    while (i < len - 1)
    {
        unsigned int candidate = (unsigned int)(rand() % (2 * len)) + 1;
        int isDuplicate = 0;

        TreeNode *newRoot = addToTree(root, &candidate, sizeof(unsigned int),
                                      compareUnsignedInt, &isDuplicate);
        if (newRoot == NULL && root == NULL)
        {
            // Speicherfehler beim ersten Einfügen
            clearTree(root);
            free(numbers);
            return NULL;
        }
        root = newRoot;

        if (!isDuplicate)
        {
            numbers[i] = candidate;
            ++i;
        }
        // bei Duplikat wird einfach eine neue Zufallszahl generiert
    }

    // Einen zufälligen Eintrag aus den ersten len-1 duplizieren
    unsigned int duplicateIndex = (unsigned int)(rand() % (len - 1));
    numbers[len - 1] = numbers[duplicateIndex];

    // Baum wird nicht mehr benötigt
    clearTree(root);

    // Das Array durchmischen (Fisher-Yates-Shuffle), damit das Duplikat an zufälliger Position steht
    for (unsigned int j = len - 1; j > 0; --j)
    {
        unsigned int k = (unsigned int)(rand() % (j + 1));
        unsigned int tmp = numbers[j];
        numbers[j] = numbers[k];
        numbers[k] = tmp;
    }

    return numbers;
}

// 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;

    // Kopie des Arrays anlegen, da qsort in-place sortiert
    unsigned int *copy = malloc(len * sizeof(unsigned int));
    if (copy == NULL)
        return 0;

    memcpy(copy, numbers, len * sizeof(unsigned int));

    // Sortieren mit qsort
    qsort(copy, len, sizeof(unsigned int), compareUnsignedInt);

    // Benachbarte Elemente vergleichen, um das Duplikat zu finden
    unsigned int duplicate = 0;
    for (unsigned int i = 1; i < len; ++i)
    {
        if (copy[i] == copy[i - 1])
        {
            duplicate = copy[i];
            break;
        }
    }

    free(copy);
    return duplicate; // 0 falls kein Duplikat gefunden (Fehlerfall)
}