/*
 * driver program that tests the AVLTree class.
 */
#include "avltree.h"
#include <iostream>
#include <cstdlib> // for exit(0), if you need it
#include <ctime>

int main()
{
	AVLTree avltree;

	//*
	cout << "\n--- left-heavy subtree that requires a single rotation ---\n";
	avltree.clear();     // root on left, leaves on right
	avltree.insert("c"); // c:-2
	avltree.insert("b"); //    b:-1
	avltree.insert("a"); //       a:0

	cout << "\n--- right-heavy subtree that requires a single rotation ---\n";
	avltree.clear();     // root on left, leaves on right
	avltree.insert("a"); //       c:0
	avltree.insert("b"); //    b:1
	avltree.insert("c"); // a:2

	cout << "\n--- left-heavy subtree that requires a double rotation ---\n";
	avltree.clear();     // root on left, leaves on right
	avltree.insert("c"); // c:-2
	avltree.insert("a"); //       b:0
	avltree.insert("b"); //    a:1

	cout << "\n--- right-heavy subtree that requires a double rotation ---\n";
	avltree.clear();     // root on left, leaves on right
	avltree.insert("a"); //    c:-1
	avltree.insert("c"); //       b:0
	avltree.insert("b"); // a:2
	// */


	// These next are only included to perform big tests of the tree to see how
	// it stands up. Feel free to uncomment this section and see how they run.
	// There isn't any special code you need to add other than the stuff you
	// wrote to get the above code to work.

	/*
	cout << "\n--- Massive test #1: add all 26 letters in order ---\n";
	avltree.clear();
	for (char c = 'a'; c <= 'z'; c++) {
		string str;
		str.append(1, c); // converts the char to a string
		cout << "inserting \"" << str << "\" into tree.." << endl;
		avltree.insert(str);
	}

	cout << "\n--- Massive test #2: add all 26 letters in reverse order ---\n";
	avltree.clear();
	for (char c = 'z'; c >= 'a'; c--) {
		string str;
		str.append(1, c); // converts the char to a string
		cout << "inserting \"" << str << "\" into tree.." << endl;
		avltree.insert(str);
	}

	cout << "\n--- Massive test #3: a buncha letters in random order ---\n";
	cout << "  (Note: the output of this one will be different every time)\n";
	avltree.clear();
	srand(time(NULL));
	while (avltree.get_size() < 26) {
		char c = (rand() % 26) + 97;
		string str;
		str.append(1, c); // converts the char to a string
		cout << "inserting \"" << str << "\" into tree.." << endl;
		avltree.insert(str);
	}
	cout << "At the end, tree looks like this:" << endl;
	avltree.print_tree();
	cout << endl;
	// */

	return 0;
}