#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
#include "bintree.h"

// Statischer Stack für die Iteration (ersetzt das externe Argument)
static StackNode *iteratorStack = NULL;

TreeNode *addToTree(TreeNode *root, const void *data, size_t dataSize, CompareFctType compareFct, int *isDuplicate)
{
    if (root == NULL) {
        TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
        if (!newNode) return NULL;

        newNode->data = malloc(dataSize);
        if (newNode->data) {
            memcpy(newNode->data, data, dataSize);
        } else {
            free(newNode);
            return NULL;
        }

        newNode->left = NULL;
        newNode->right = NULL;

        if (isDuplicate) *isDuplicate = 0; // Neu eingefügt
        return newNode;
    }

    int cmp = compareFct(data, root->data);

    if (cmp < 0) {
        root->left = addToTree(root->left, data, dataSize, compareFct, isDuplicate);
    } else if (cmp > 0) {
        root->right = addToTree(root->right, data, dataSize, compareFct, isDuplicate);
    } else {
        // Element existiert bereits
        if (isDuplicate == NULL) {
            // Wenn isDuplicate NULL ist, explizit erlauben (siehe Aufgabenstellung/Kommentar)
            // Wir fügen es rechts ein
            root->right = addToTree(root->right, data, dataSize, compareFct, isDuplicate);
        } else {
            // Duplikat melden und NICHT einfügen
            *isDuplicate = 1;
        }
    }
    return root;
}

// Hilfsfunktion: Schiebt Node und alle linken Kinder auf den Stack
static void pushLeft(StackNode **stack, TreeNode *node) {
    while (node != NULL) {
        *stack = push(*stack, node);
        node = node->left;
    }
}

void *nextTreeData(TreeNode *root)
{
    // Wenn root übergeben wird, starte neue Iteration
    if (root != NULL) {
        clearStack(iteratorStack);
        iteratorStack = NULL;
        pushLeft(&iteratorStack, root);
    }

    if (top(iteratorStack) == NULL) {
        return NULL; // Ende der Iteration
    }

    TreeNode *current = (TreeNode *)top(iteratorStack);
    iteratorStack = pop(iteratorStack);
    void *data = current->data;

    // Wenn es einen rechten Teilbaum gibt, verarbeite diesen als nächstes
    if (current->right != NULL) {
        pushLeft(&iteratorStack, current->right);
    }

    return data;
}

void clearTree(TreeNode *root)
{
    if (root == NULL) return;
    clearTree(root->left);
    clearTree(root->right);
    if (root->data) free(root->data);
    free(root);
}

unsigned int treeSize(const TreeNode *root)
{
    if (root == NULL) return 0;
    return 1 + treeSize(root->left) + treeSize(root->right);
}