#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "strbst.h"
/*
strbst defines strbst with one member: strbstnode->head.
strbstnode has left, right, data, ind, and ht for avl balancing
*/
int max(int a, int b) {
    return ( (a < b) ? a : b);
}

typedef char height;

strbst* newbst(void) {
    return calloc(sizeof(strbst),1);
}

static strbstnode* newbstnode(char* ind, void* data) {
    // Doesn't insert, just allocates
    strbstnode* out = malloc(sizeof(strbstnode));
    out->ind = ind;
    out->data = data;
    out->left = out->right = NULL;
    out->ht = 0;
    return out;
}

// A nonexistent node has height of -1 so that childless nodes are ht 0.
#define getht(node) ( (node) ? node->ht : -1 )

// The basic (and only) balancing operations for AVL: rotations
// Take address of top node so that the real tree can change.
static void rightrot(strbstnode** bst) {
/*
    a         b
   / \       / \
  b   e =>  c   a
 / \           / \
c   d         d   e
*/
    strbstnode* flip = (*bst)->left->right; // flip = d
    (*bst)->left->right = *bst; // position of d = a
    *bst = (*bst)->left; // tip = b
    (*bst)->right->left = flip;
}

static void leftrot(strbstnode** bst) {
/*
  a            b
 / \          / \
e   b   =>   a   c
   / \      / \
  d   c    e   d
*/
    strbstnode* flip = (*bst)->right->left; // flip = d
    (*bst)->right->left = *bst; // position of d = a
    *bst = (*bst)->right; // tip = b
    (*bst)->left->right = flip;
}
// NOTE: These functions are valid because `b` is guaranteed in the
// conditions where the rotations are called.

static int insnode(strbstnode** bst, strbstnode* new) {
    // returns height of right node minus height of left node ("bias")
    if (!*bst) { // When an empty node is reached,
        *bst = new; // place the node
        return 0; // no children, so height difference is zero
    }
    strbstnode** node;
    if (strcmp(new->ind, (*bst)->ind) < 0) // bst < ind?
        // the address of the new node has to be taken so that node's
        // addr is not returned
        node = &((*bst)->left);
    else // assumed that new's index is not contained in tree
        node = &((*bst)->right);
    // node is the parent of the subtree which will contain new
    int heavy = insnode( node, new );
        // insert it into the subtree and get its bias
    int diff = getht((*bst)->right) - getht((*bst)->left);
    if (diff > 1) { // was originally valid (diff==1), so diff == 2
        if (heavy == -1) // if node is left heavy,
            rightrot(node); // make it right heavy. ht shouldn't change.
        leftrot(bst); // fixes, since heavy side is either right heavy
                      // or centered
    } else if (diff < -1){ // diff == -2
        if (heavy == 1)
            leftrot(node); // make left heavy
        rightrot(bst); // fix
    }
    // Calculate the current node's height
    (*bst)->ht = max( getht((*bst)->left), getht((*bst)->right) )+1;
    // And return calculated bias
    return ( getht((*bst)->right) - getht((*bst)->left) );
}

void insbst(strbst* bst, char* ind, void* data) {
    insnode(&(bst->head), newbstnode(ind, data)); // allows recursion
}

static void* querynode(strbstnode* node, char* ind){
    // tail-recursive finding algorithm
    if (!node) return NULL; // NULL => node not found
    int cmp = strcmp(ind, node->ind);
    if (cmp > 0) // ind > node->ind
        return querynode(node->right, ind);
    else if (cmp < 0) // ind < node->ind
        return querynode(node->left, ind);
    else
        return node->data; // void* data is passed back up the chain
}

void* query(strbst* bst, char* ind) {
    return querynode(bst->head, ind);
}

static void printbstnode(strbstnode* node) {
    if (!node) return;
    // Recursive printing
    if (node->right)
        printbstnode(node->right);
    if (node->left)
        printbstnode(node->left);
    // Print one line.
    // With all components, "node %s (right) %s (left) %s\n"
    printf("node %s", node->ind);
    if (node->right)
        printf(" (right) %s",node->right->ind);
    if (node->left)
        printf(" (left) %s", node->left->ind);
    printf("\n");
}

void printbst(strbst* bst) {
    printbstnode(bst->head);
}