#include "bstree.h"
#include <iostream>
#include <cstdlib> // for exit(0), if you need it
using namespace std;

/*
 * driver program that tests the BinarySearchTree class.
 *
 * Adds nodes to a binary tree such that
 * the following tree is formed:
 *
 *        d
 *       / \
 *      /   \
 *     b     f
 *    / \   / \
 *   a   c e   g
 */

// (support function)
void tree_stats(BinarySearchTree &bstree)
{
	if (bstree.is_empty()) cout << "the tree is empty" << endl;
	else cout << "the tree is NOT empty" << endl;
	cout << "size of tree: " << bstree.get_size() << endl;
	cout << "height of tree: " << bstree.get_height() << endl;
}

int main()
{
	cout << "--- instantiating new tree --- \n";
	// must implement: constructor, is_empty(), get_size(), get_height()
	BinarySearchTree bstree;
	tree_stats(bstree);


	cout << "\n--- add items to the tree --- \n";
	// must implement: insert(string addme), insert(BinarySearchNode * node)

	cout << "Adding some nodes to the tree..." << endl;
	bstree.insert("d");
	bstree.insert("b");
	bstree.insert("f");
	bstree.insert("a");
	bstree.insert("c");
	bstree.insert("e");
	bstree.insert("g");
	bstree.insert("g"); // test adding existing string

	tree_stats(bstree);


	cout << "\n--- search for items --- \n";
	// must implement: exists()

	cout << "Testing to see if some nodes exist..." << endl;
	// one that exists
	if (bstree.exists("c")) cout << "\"c\" exists" << endl;
	else cout << "\"c\" doesn't exist" << endl;
	// non-existant
	if (bstree.exists("x")) cout << "\"x\" exists" << endl;
	else cout << "\"x\" doesn't exist" << endl;


	cout << "\n--- display the contents of the tree, various ways ---\n";
	// must implement public & private versions (i.e. the ones that take a
	// BinarySearchNode * as a parameter) of preorder_print(),
	// postorder_print(), inorder_print()

	cout << "output shows root on the left, leaves on the right" << endl;
	bstree.print_tree();
	bstree.inorder_print();
	bstree.preorder_print();
	bstree.postorder_print();
	cout << endl;


	// ... HOMEWORK: uncomment the next lines when you're ready to do the homework
	/*
	cout << "--- delete some nodes from the tree ---\n";
	// must implement: del()

	// try removing a leaf node
	if (bstree.del("a")) cout << "removed leaf node 'a'" << endl;
	else cout << "could NOT remove left node 'a'" << endl;
	bstree.print_tree();
	bstree.inorder_print();
	cout << endl;

	// try removing a middle node with left and right children
	if (bstree.del("f")) cout << "removed middle node 'f'" << endl;
	else cout << "could NOT remove middle node 'f'" << endl;
	bstree.print_tree();
	bstree.inorder_print();
	cout << endl;

	// try removing the root node
	if (bstree.del("d")) cout << "removed root node 'd'" << endl;
	else cout << "could NOT remove root node 'd'" << endl;
	bstree.print_tree();
	bstree.inorder_print();
	cout << endl;

	// try removing a non-existant node
	if (bstree.del("x")) cout << "removed non-existant node \"x\"" << endl;
	else cout << "could NOT remove non-existant node \"x\"" << endl;
	bstree.print_tree();
	bstree.inorder_print();
	cout << endl;
	*/


	cout << "--- clear the tree ---\n";
	// must implement: clear(), delete_subtree(), and the destructor
	bstree.clear();
	tree_stats(bstree);


	return 0;
}