#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "numbers.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.


// Returns len random numbers between 1 and 2x len in random order which are all different, except for two entries.
// Returns NULL on errors.
unsigned int *createNumbers(unsigned int len)
{
    if (len < 2) return NULL;

    // Allocate memory for the array
    unsigned int *numbers = malloc(len * sizeof(unsigned int));
    if (!numbers) return NULL;

    // Initialize random number generator
    srand((unsigned int)time(NULL));

    // We need to ensure len-1 unique numbers in range [1, 2*len]
    unsigned int maxValue = 2 * len;
    unsigned int uniqueCount = len - 1;  // We'll generate len-1 unique values

    // Generate unique numbers using a simple linear search approach
    for (unsigned int i = 0; i < uniqueCount; i++) {
        int isUnique;
        unsigned int candidate;

        // Keep generating until we find a unique number
        do {
            candidate = (rand() % maxValue) + 1;  // Random number in [1, 2*len]
            isUnique = 1;

            // Check if candidate already exists in our array so far
            for (unsigned int j = 0; j < i; j++) {
                if (numbers[j] == candidate) {
                    isUnique = 0;
                    break;
                }
            }
        } while (!isUnique);

        numbers[i] = candidate;
    }

    // Now we have len-1 unique numbers. Duplicate one of them.
    // Choose a random index from the unique numbers
    unsigned int duplicateIndex = rand() % uniqueCount;
    unsigned int duplicateValue = numbers[duplicateIndex];

    // Add the duplicate at the last position
    numbers[len - 1] = duplicateValue;

    // Shuffle the entire array to randomize the position of the duplicate
    for (unsigned int i = 0; i < len; i++) {
        unsigned int swapIndex = rand() % len;

        // Swap numbers[i] and numbers[swapIndex]
        unsigned int temp = numbers[i];
        numbers[i] = numbers[swapIndex];
        numbers[swapIndex] = temp;
    }

    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;

    // Create a copy of the array since we need to sort it
    unsigned int *copy = malloc(len * sizeof(unsigned int));
    if (!copy) return 0;

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

    // Simple bubble sort implementation (no external function dependencies)
    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]) {
                // Swap if out of order
                unsigned int temp = copy[j];
                copy[j] = copy[j + 1];
                copy[j + 1] = temp;
            }
        }
    }

    // Now find the duplicate by checking adjacent elements
    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;
}