/*
 * Mark Whitley
 * IT 327 - Data Struct
 * Week 8 Lab 2 - C++ implementation of an AVL (balanced, binary search) tree
 *
 * Note: the AVL tree is derived from BinarySearchTree, meaning it inherits
 * all it's methods. some are overridden (notably insert()) to add code to
 * balance the tree.
 */

#include "avltree.h"
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

static bool debugging = true;

// ------ AVL node, inner class --------

	// parent needs to set itself up before us, we call it's constructor
AVLNode::AVLNode(string data) : BinarySearchNode(data)
{
	// ... set this node's balance member to 0

}

void AVLNode::print()
{
	cout << data << ":" << balance << " ";
}

// ------ AVL tree class --------

// overloaded insert function
void AVLTree::insert(string addme)
{
	// we won't insert a node that already exists
	//
	// ... modify condition: test if the node exists in the tree. (Hint: call
	// the exists() method that we inherit from BinarySearchTree)
	if (false) {
		if (debugging) cout << "\"" << addme << "\" already exists in tree" << endl;
		return;
	}

	// ... call the recursive insert method (below), passing it 'root' and
	// 'addme' (Note: if the compiler gives you grief, you will need to cast
	// root to an AVLNode * like so: (AVLNode *&)root.) assign insert()'s
	// return value to 'root'.

	// ... size of the tree just got bigger, increment 'size' member

}

void AVLTree::update_balance(AVLNode * node)
{
	// sanity check: make sure we weren't passed a null node
	// ... call assert(), passing it a condition that tests if the node is not null

	// ... modify next line: set the node's balance (hint: arrow operator) to
	// the difference between the height of the right node (hint: call
	// get_height() on the right child) and the height of the left node (hint:
	// get_height() on the left child)
	node->balance = 0;

	// verification #1: balance better not hit -3 ever
	// ... call assert(), passing it a condition that tests if the node's
	// balance is not equal to -3

	// verification #2: balance better not hit +3 ever
	// ... call assert(), passing it a condition that tests if the node's
	// balance is not equal to +3

}


// recursive approach to inserting a node
//
// Note: If this function looks long, imagine what it would look like with all
// the comments and debugging noise stripped out. It'd be pretty short
AVLNode * AVLTree::insert(AVLNode * &node, string addme)
{
	// ... modify condition, test if node is NULL
	if (false) {
		// ... return a new AVLNode, passing 'addme' to it's constructor

	// ... modify condition, test if 'addme' is less than the node's data
	} else if (false) {
		// ... insert to the left by calling insert (recursively), passing it
		// the node's left child and 'addme'. (Note: you may need to cast the
		// node's left child to an AVLNode *& like so: (AVLNode
		// *&)node->left.) assign the return value to node->left.

		// ... in the unwinding phase we update the balance. call
		// update_balance() passing it 'node'

		// ... test if the tree became unbalanced with that last insertion,
		// change if condition to test if node's balance is -2. (what's the
		// difference between a single and a double equals sign?)
		if (false) {
			if (debugging) {
				cout << "tree is left-heavy, looks like this:" << endl;
				print_tree();
				cout << endl;
			}

			// ... modify condition to test if the string we were adding
			// ('addme') is less than this node's left child's data (Hint: two
			// arrow operators)
			if (false) {
				if (debugging) cout << "the node \"" << node->data <<
					"\" is left-left heavy, need to LL rotate.." << endl;

				// ... call LL_rotate() on the node, assign it's return value
				// to 'node'

			} else {

				if (debugging) cout << "the node \"" << node->data <<
					"\" is left-right heavy, need to LR rotate.." << endl;

				// ... call LR_rotate() on the node, assign it's return value
				// to 'node'

			}

			if (debugging) {
				cout << "done, tree now looks like this:" << endl;
				print_tree();
				cout << endl;
			}
		}
	// ... modify condition, test if 'addme' is greater than the node's data
	} else if (false) {

		// ... insert to the right by calling insert (recursively), passing it
		// the node's right child and 'addme'. (Note: you will need to cast
		// the node's right child to an AVLNode * like so: (AVLNode *&)node->right)
		// assign the return value to node->right.

		// ... in the unwinding phase we update the balance. call
		// update_balance() passing it 'node'

		// ... test if the tree became unbalanced with that last insertion,
		// change if condition to test if node's balance is +2
		if (false) {
			if (debugging) {
				cout << "tree is right-heavy, looks like this:" << endl;
				print_tree();
				cout << endl;
			}

			// ... modify condition to test if the string we were adding
			// ('addme') is greater than this node's right child's data (Hint:
			// two arrow operators)
			if (false) {
				if (debugging) cout << "the node \"" << node->data <<
					"\" is right-right heavy, need to RR rotate.." << endl;

				// ... call RR_rotate() on the node, assign it's return value
				// to 'node'

			} else {

				if (debugging) cout << "the node \"" << node->data <<
					"\" is right-left heavy, need to RL rotate.." << endl;

				// ... call RL_rotate() on the node, assign it's return value
				// to 'node'

			}

			if (debugging) {
				cout << "done, tree now looks like this:" << endl;
				print_tree();
				cout << endl;
			}
		}
	}

	return node;
}

AVLNode * AVLTree::LL_rotate(AVLNode * LL_hvy)
{
	// sanity check #1: we can't rotate a null node.
	//
	// ... call assert() with a condition that tests if LL_hvy is not null.


	// sanity check #2: if we're going to rotate left, the node we were passed
	// better have a left child.
	//
	// ... call assert() with a condition that tests if LL_hvy's left child is
	// not null.


	// the left child of the LL-heavy node will be the new root after we
	// rotate
	//
	// ... modify next line: in place of NULL, assign to 'new_root' the left
	// child of LL_hvy.  (Note: you will need to cast it to an AVLNode *, much
	// like we did in the insert() method(s) above.
	AVLNode * new_root = NULL;

	// the new root's right child will be the current LL-heavy node, so the
	// new root needs to give his right child to someone else, specifically
	// LL-heavy, as his left child
	//
	// ... set LL_hvy's left child to new_root's right child


	// as promised, the new root's right child is now the LL-heavy node
	//
	// ... set new_root's right child to LL_hvy


	// after the rotation, the balances will have changed
	//
	// ... call update_balance() on (a) LL_hvy and (b) new_root (2 lines total)


	return new_root;
}

AVLNode * AVLTree::RR_rotate(AVLNode * RR_hvy)
{
	// ... you guys get to figure this one out on your own. here's some hints:
	//
	// - begin with copy & paste from LL_rotate(), above (including the sanity
	// checks)
	//
	// - replace all 'LL_hvy's with 'RR_hvy'
	//
	// - everyplace where it says "right", it needs to be changed to "left".
	// likewise, everyplace where it says "left", it needs to be changed to
	// "right". (this part can get a little thorny, pay close attention to
	// what you're doing.)
	//
	// - the return statement at the bottom will need to be replaced with the
	// one from LL_rotate(). I put it in so the code would compile.


	return NULL;
}

AVLNode * AVLTree::LR_rotate(AVLNode * LR_hvy)
{
	// 3 sanity checks: write assert statements that verify each of the
	// following tests:
	//
	// ... the passed node (LR_hvy) must not be null

	// ... the passed node must have a left child

	// ... the passed node's left node must have a right child (Hint: 2 arrow
	// operators)

	// ... call RR_rotate on LR_hvy's left child, assign the result to
	// LR_hvy's left child. (Note: if the compiler gives you grief, you will
	// need to cast the argument to an (AVLNode *) as before


	// ... modify return statement: in place of NULL, call LL_rotate, passing
	// it LR_hvy.
	return NULL;
}

AVLNode * AVLTree::RL_rotate(AVLNode * RL_hvy)
{
	// ... you guys get to figure this one out on your own. here's some hints:
	//
	// - begin with copy & paste from LR_rotate(), above (including the sanity
	// checks)
	//
	// - replace all 'LR_hvy's with 'RL_hvy'
	//
	// - everyplace where it says "right", it needs to be changed to "left".
	// likewise, everyplace where it says "left", it needs to be changed to
	// "right". (Again, be careful here.)
	//
	// - everyplace where it says LL_rotate() it needs to be changed to
	// RR_rotate(), and vice-versa. (details matter)
	//
	// - the return statement at the bottom will need to be replaced with
	// something similar to the one from LR_rotate(). I put it in so the code
	// would compile.


	return NULL;
}