#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "iterative_tree_traversals.h" // struct types and function declarations used in this file


/********************************************************************
|* MAIN function
\*/
int main(int argc, char* argv[]) {
    // Empty list
    BSTNode* root = NULL;

    // Insert a value
    insert(4, &root);
    insert(2, &root);
    insert(6, &root);
    insert(1, &root);
    insert(3, &root);
    insert(5, &root);
    insert(7, &root);

    printf("Pre-order\n");
    print_tree_pre_order(root);

    printf("In-order\n");
    print_tree_in_order(root);

    // Free
    destroy_tree(&root);

    return EXIT_SUCCESS;
}


/********************************************************************
|* Iterative tree traversals
\*/
void print_tree_in_order(BSTNode* root) {  // IN-ORDER traversal:  left, root, right
    StackNode* top = NULL;
    BSTNode* curr = root;
    while(curr != NULL || top != NULL) {   // *** OR ***
        if(curr != NULL) {
            stack_push(&top, curr); // "Push the 4 onto the stack:"
            curr = curr -> left;    // "Go to the left subtree"
        }
        else {
            curr = stack_pop(&top);
            printf("curr -> value == %d\n", curr -> value);
            curr = curr -> right;    // will lead to pushing curr -> right next time
        }
    }
}

void print_tree_pre_order(BSTNode* root) {  // PRE-ORDER traversal:  root, left, right
    StackNode* top = NULL;
    stack_push(&top, root);
    while(top != NULL) {
        BSTNode* curr = stack_pop(&top);
        if(curr != NULL) {
            printf("curr -> value == %d\n", curr -> value);
            stack_push(&top, curr -> right);
            stack_push(&top, curr -> left);
        }
    }
}


/********************************************************************
|* STACK operations
\*/
void stack_push(StackNode** a_top, BSTNode* value) {
    StackNode* new_top = malloc(sizeof(*new_top));
    *new_top = (StackNode) { .next = NULL, .value = value };  // Compound literal
    if(*a_top != NULL) {  // If stack is not initially empty...
        new_top -> next = *a_top;   // make the new top refer to the existing top
    }
    *a_top = new_top; // new top becomes the top of the stack
    assert(*a_top != NULL);  // Just added something, so can't possibly be empty now.
    assert((*a_top) -> value == value);  // Top should have the character we just pushed.
}

BSTNode* stack_pop(StackNode** a_top) {  // Usage:  Must not be called with an empty stack.
    StackNode* old_top = *a_top;
    BSTNode* value = old_top -> value;
    *a_top = old_top -> next;
    free(old_top);
    return value;
}

bool stack_is_empty(StackNode* top) {
    return (top == NULL);
}


/********************************************************************
|* BST (binary search tree) operations
\*/
void insert(int value, BSTNode** a_root) {
    // If tree is empty, then insert the value as the root of this tree.
    if(*a_root == NULL) {
        // CREATE new node
        BSTNode* new_node = malloc(sizeof(*new_node));
        *new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };

        // CONNECT new node to the tree
        *a_root = new_node;
    }
    // Otherwise, insert in either the left or right subtree, depending on the value.
    else if(value < (*a_root) -> value) {
        insert(value, &((*a_root) -> left));
    }
    else if(value >= (*a_root) -> value) {
        insert(value, &((*a_root) -> right));
    }
}

void destroy_tree(BSTNode** a_root) {  // 
    if(*a_root != NULL) {
        destroy_tree(&((*a_root) -> left));
        assert((*a_root) -> left == NULL);  // left subtree has been destroyed and is empty
        destroy_tree(&((*a_root) -> right));
        assert((*a_root) -> right == NULL);

        free(*a_root);   // deallocate
        *a_root = NULL;  // set to NULL to indicate that it is empty
    }
    assert(*a_root == NULL); // Tree must be empty
}

/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */