#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.
unsigned int *createNumbers(unsigned int len) {

    if (len < 2)
      return NULL;

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

    srand((unsigned int)time(NULL));

    for (unsigned int i = 0; i < len - 1; i++) {
        unsigned int n;
        int duplicate;
        do {
            duplicate = 0;
            n = rand() % (2 * len) + 1;

            for (unsigned int j = 0; j < i; j++) {
                if (numbers[j] == n) {
                    duplicate = 1;
                    break;
                }
            }
        } while (duplicate);

        numbers[i] = n;
    }

    // zufälliges Duplikat am Ende
    unsigned int idx1 = rand() % (len - 1);
    numbers[len - 1] = numbers[idx1];

    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 || len < 2) return 0;

    // Kopie erstellen, damit Original nicht verändert wird
    unsigned int *copy = malloc(len * sizeof(unsigned int));
    if (!copy) return 0;
    memcpy(copy, numbers, len * sizeof(unsigned int));

    // Einfacher Bubble Sort oder Insert Sort direkt in dieser Funktion
    // damit wir keine Hilfsfunktionen brauchen
    for (unsigned int i = 0; i < len - 1; i++) {
        for (unsigned int j = 0; j < len - i - 1; j++) {
            if (copy[j] > copy[j + 1]) {
                unsigned int tmp = copy[j];
                copy[j] = copy[j + 1];
                copy[j + 1] = tmp;
            }
        }
    }

    // benachbarte Elemente vergleichen
    for (unsigned int i = 0; i < len - 1; i++) {
        if (copy[i] == copy[i + 1]) {
            unsigned int dup = copy[i];
            free(copy);
            return dup;
        }
    }

    free(copy);
    return 0;
}