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

static StackNode *iterStack = NULL;
static void pushLeftBranch(StackNode **stack, TreeNode *node);

// Inserts a new node into the BST.
// If isDuplicate == NULL → duplicates are allowed
// If isDuplicate != NULL → duplicates are ignored and *isDuplicate = 1
TreeNode *addToTree(TreeNode *root, const void *data, size_t dataSize,
                    CompareFctType compareFct, int *isDuplicate)
{
    if (root == NULL)
    {
        TreeNode *newNode = calloc(1, sizeof(TreeNode));
        if (!newNode)
            return NULL;

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

        memcpy(newNode->data, data, dataSize);

        if (isDuplicate)
            *isDuplicate = 0;

        return newNode;
    }

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

    if (cmp < 0 || (cmp == 0 && isDuplicate == NULL))
    {
        root->left = addToTree(root->left, data, dataSize, compareFct, isDuplicate);
    }
    else if (cmp > 0)
    {
        root->right = addToTree(root->right, data, dataSize, compareFct, isDuplicate);
    }
    else
    {
        if (isDuplicate)
            *isDuplicate = 1;
    }

    return root;
}

static void pushLeftBranch(StackNode **stack, TreeNode *node)
{
    while (node)
    {
        *stack = push(*stack, node);
        node = node->left;
    }
}

// If root != NULL → reset iterator and start from new tree.
// If root == NULL → continue iterating.
void *nextTreeData(TreeNode *root)
{
    // Start new iteration
    if (root != NULL)
    {
        // reset old iterator state
        clearStack(iterStack);
        iterStack = NULL;

        // push root and all left children
        pushLeftBranch(&iterStack, root);
    }

    // No active iterator
    if (iterStack == NULL)
        return NULL;

    // Get next node
    TreeNode *node = (TreeNode *)top(iterStack);
    iterStack = pop(iterStack);

    // push right subtree and its left descendants
    if (node->right)
        pushLeftBranch(&iterStack, node->right);

    return node->data;
}

// Frees all nodes and also resets iterator.
void clearTree(TreeNode *root)
{
    if (!root)
        return;

    clearTree(root->left);
    clearTree(root->right);

    free(root->data);
    free(root);

    // If we clear the tree, iterator must not point into freed memory.
    clearStack(iterStack);
    iterStack = NULL;
}

unsigned int treeSize(const TreeNode *root)
{
    if (!root)
        return 0;

    return 1 + treeSize(root->left) + treeSize(root->right);
}