/**
 * @file avltree.cpp
 * Definitions of the binary tree functions you'll be writing for this lab.
 * You'll need to modify this file.
 */

template <class K, class V>
V AVLTree<K, V>::find(const K& key) const
{
    return find(root, key);
}

template <class K, class V>
V AVLTree<K, V>::find(Node* subtree, const K& key) const
{
    if (subtree == NULL)
        return V();
    else if (key == subtree->key)
        return subtree->value;
    else {
        if (key < subtree->key)
            return find(subtree->left, key);
        else
            return find(subtree->right, key);
    }
}

template <class K, class V>
void AVLTree<K, V>::rotateLeft(Node*& t)
{
    functionCalls.push_back("rotateLeft"); // Stores the rotation name (don't remove this)
    // your code here
    if (t == NULL || t->right == NULL) {
        return;
    }
    //we have t->b->c to the right, we do:
    //b's left child becomes t's right child.
    //t becomes b's left child
    Node * newRoot = t->right;
    Node * temp = newRoot->left;

    newRoot->left = t;
    t->right = temp;
    //t = newRoot;

    newRoot->height = findHeight(newRoot);
    if (newRoot->left != NULL){
        newRoot->left->height = findHeight(newRoot->left);
    }
    if (newRoot->right != NULL){
        newRoot->right->height = findHeight(newRoot->right);
    }

}

template <class K, class V>
void AVLTree<K, V>::rotateLeftRight(Node*& t)
{
    functionCalls.push_back("rotateLeftRight"); // Stores the rotation name (don't remove this)
    // Implemented for you:
    rotateLeft(t->left);
    rotateRight(t);
}

template <class K, class V>
void AVLTree<K, V>::rotateRight(Node*& t)
{
    functionCalls.push_back("rotateRight"); // Stores the rotation name (don't remove this)
    Node * newRoot = t->left;
    Node * temp = newRoot->right;

    newRoot->right = t;
    t->left = temp;

    newRoot->height = findHeight(newRoot);
    if (newRoot->left != NULL){
        newRoot->left->height = findHeight(newRoot->left);
    }
    if (newRoot->right != NULL){
        newRoot->right->height = findHeight(newRoot->right);
    }
}

template <class K, class V>
void AVLTree<K, V>::rotateRightLeft(Node*& t)
{
    functionCalls.push_back("rotateRightLeft"); // Stores the rotation name (don't remove this)
    // your code here
    rotateRight(t->right);
    rotateLeft(t);
}

template <class K, class V>
void AVLTree<K, V>::rebalance(Node*& subtree)
{
    if (subtree == NULL){
        return;
    }

    int currBalanceFactor = balanceFactor(subtree);

    if (currBalanceFactor < -1){
        if (balanceFactor(subtree->right) <= 0){
            rotateLeft(subtree);
        }
        else {
            rotateRightLeft(subtree);
        }
    }
    else if (currBalanceFactor > 1){
        if (balanceFactor(subtree->left) >= 0 ){
            rotateRight(subtree);
        }
        else {
            rotateRight(subtree);
        }
    }

    subtree->height = findHeight(subtree);

}

template <class K, class V>
int AVLTree<K, V>::balanceFactor(Node*& subtree) {
    if (subtree == NULL){
        return 0;
    }

    int leftH = heightOrNeg1(subtree->left);
    int rightH = heightOrNeg1(subtree->right);
    return leftH - rightH;
}

template <class K, class V>
int AVLTree<K, V>::findHeight(Node*& subtree) {
    if (subtree == NULL){
        return 0;
    }
    return max(findHeight(subtree->left), findHeight(subtree->right)) + 1;
}

template <class K, class V>
void AVLTree<K, V>::insert(const K & key, const V & value)
{
    insert(root, key, value);
}

template <class K, class V>
void AVLTree<K, V>::insert(Node*& subtree, const K& key, const V& value)
{
    if (subtree == NULL){
        subtree = new Node(key, value);
    }
    else if (subtree->key == key){
        subtree->value = value;
    }
    else if (key < subtree->key){
        insert(subtree->left, key, value);
        //rebalance(subtree);
    }
    else {
        insert(subtree->right, key, value);
        //rebalance(subtree);
    }
}

template <class K, class V>
void AVLTree<K, V>::remove(const K& key)
{
    remove(root, key);
}

template <class K, class V>
void AVLTree<K, V>::remove(Node*& subtree, const K& key)
{
    if (subtree == NULL)
        return;

    if (key < subtree->key) {
        // your code here
    } else if (key > subtree->key) {
        // your code here
    } else {
        if (subtree->left == NULL && subtree->right == NULL) {
            /* no-child remove */
            // your code here
        } else if (subtree->left != NULL && subtree->right != NULL) {
            /* two-child remove */
            // your code here
        } else {
            /* one-child remove */
            // your code here
        }
        // your code here
    }
}