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

//TODO: getDuplicate und createNumbers implementieren
/*  *   * Erzeugen eines Arrays mit der vom Nutzer eingegebenen Anzahl an Zufallszahlen.
  * Sicherstellen, dass beim Befüllen keine Duplikate entstehen.
  * Duplizieren eines zufälligen Eintrags im Array.
  * in `getDuplicate()`: Sortieren des Arrays und Erkennen der doppelten Zahl durch Vergleich benachbarter Elemente. */

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


int compareUInts(const void *arg1, const void *arg2){
    unsigned int val1 = *(unsigned int *)arg1;
    unsigned int val2 = *(unsigned int *)arg2;

    if(val1 < val2) return -1;
    if(val1 > val2) return 1;
    return 0;
}

unsigned int* createNumbers(unsigned int len)
{
    if(len == 0){
        return NULL;
    }

    unsigned int* numbers = (unsigned int*)malloc(len * sizeof(unsigned int));
    if(numbers == NULL){
        return NULL;
    }

    TreeNode *tree = NULL;
    
    unsigned int i = 0;
    while(i < len){
        unsigned int tmp = (rand() % (2*len)) + 1;

        int isDuplicate = 0;
        tree = addToTree(tree, &tmp, sizeof(unsigned int), compareUInts, &isDuplicate);

        if(!isDuplicate){
            numbers[i] = tmp;
            i++;
        }
    }

    clearTree(tree);

    unsigned int rIdx = rand() % len;
    unsigned int duplicate = numbers[rIdx];

    unsigned int tIdx = rand() % len;
    while(tIdx == rIdx){
        tIdx = rand() % len;
    }
    numbers[tIdx] = duplicate;

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

    unsigned int* sorted = (unsigned int*)malloc(len * sizeof(unsigned int));
    if(sorted == NULL){
        return 0;
    }

    TreeNode *tree = NULL;
    for(unsigned int i = 0; i < len; i++){
        tree = addToTree(tree, &numbers[i], sizeof(unsigned int), compareUInts, NULL);
    }

    sorted[0] = *(unsigned int *)nextTreeData(tree);

    for(unsigned int j = 1; j < len; j++){
        sorted[j] = *(unsigned int*)nextTreeData(NULL);
    }
    unsigned int duplicate = 0;
    for(unsigned int k = 0; k < len - 1; k++){
        if(sorted[k] == sorted[k+1]){
            duplicate = sorted[k];
            break;
        }
    }
    free(sorted);
    return duplicate;
}