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

// Vergleichsfunktion für den generischen Baum
static int compareInts(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;
}

unsigned int *createNumbers(unsigned int len)
{
    if (len < 2) return NULL;

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

    TreeNode *root = NULL;
    int isDuplicate = 0;
    unsigned int count = 0;

    srand(time(NULL));

    // 1. Array mit eindeutigen Zahlen füllen
    while (count < len - 1) {
        // Zufallszahl generieren (Bereich groß genug wählen)
        unsigned int r = (rand() % (len * 3)) + 1;

        // Versuchen in Baum einzufügen
        // Wir übergeben &isDuplicate, damit Duplikate abgelehnt werden
        root = addToTree(root, &r, sizeof(unsigned int), compareInts, &isDuplicate);

        if (isDuplicate == 0) {
            array[count] = r;
            count++;
        }
    }

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

    // 2. Duplikat erzeugen (einen vorhandenen Wert ans Ende kopieren)
    unsigned int dupIndex = rand() % (len - 1);
    array[len - 1] = array[dupIndex];

    // 3. Mischen
    for (unsigned int i = 0; i < len; i++) {
        unsigned int j = rand() % len;
        unsigned int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return array;
}

unsigned int getDuplicate(const unsigned int *numbers, unsigned int len)
{
    if (!numbers || len < 2) return 0;

    unsigned int *copy = (unsigned int *)malloc(len * sizeof(unsigned int));
    if (!copy) return 0;

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

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

    unsigned int duplicate = 0;
    for (unsigned int i = 0; i < len - 1; i++) {
        if (copy[i] == copy[i+1]) {
            duplicate = copy[i];
            break;
        }
    }

    free(copy);
    return duplicate;
}