#ifndef CLASS_TREE_H
#define CLASS_TREE_H

// Remove this if you want to use the tree without graphviz support
#define GRAPHVIZ

#ifdef GRAPHVIZ
#include<graphviz/cgraph.h>
#include<graphviz/gvc.h>
#endif

#include<iostream>
using namespace std;

template<class T>
struct node {
	T data;
	node *left, *right;
};

template<class T>
class Tree {
	node<T> *root = 0;
#ifdef GRAPHVIZ
	void make_image_recur(Agraph_t*, Agnode_t*, node<T>*);
#endif
public:
	bool find_reference(T data, T **found_place);
	void insert(T data);
	T& search(T data);

#ifdef GRAPHVIZ
	void make_image(string);
#endif
	void deallocate_tree(node<T>* place){
		// This would be where code for preorder traversal goes
		if(place->left)
			deallocate_tree(place->left);
		// This place for inorder
		if(place->right)
			deallocate_tree(place->right);
		// This place down here for postorder traversal
		delete place;  // So we do deletion postorder
	}
	~Tree(){
		deallocate_tree(root);
	}
	void print_inorder(node<T>* place = 0);
	void remove(T data);
	void rotate_left(node<T> **place = 0);
	void rotate_right(node<T> **place = 0);
	void improve_balance(node<T> **place = 0);
	int depth_from_place(node<T> *place);
};

template<class T>
bool Tree<T>::find_reference(T data, T **found_place){
	node<T> *place = root;
	while(place){
		if(place->data == data){
			*found_place = &(place->data);
			return true;
		}
		if(place->data > data)
			place = place->left;
		if(place && place->data < data)
			place = place->right;
	}
	return false;
}

template<class T>
T& Tree<T>::search(T data){
	node<T> *place = root;
	while(place){
		if(place->data == data)
			return place->data;
		if(place->data > data)
			place = place->left;
		if(place->data < data)
			place = place->right;
	}
	cout << "Oh no!  We didn't find it!\n"; // TODO:  Handle this somehow
	return data;
}

template<class T>
void Tree<T>::insert(T data){
	node<T> *new_node = new node<T>;
	new_node->data = data;
	new_node->left = new_node->right = 0;
	if(!root){
		root = new_node;
		return;
	}
	node<T> *place = root;
	node<T> *parent = 0;
	while(place){
		parent = place;
		if(data < place->data)
			place = place->left;
		else if(data > place->data)
			place = place->right;
		else 
			cout << "Help!  A duplicate!\n";
	}
	if(parent->data < data)
		parent->right = new_node;
	else
		parent->left = new_node;
}

#ifdef GRAPHVIZ
/* To build this program remember to add -lcgraph and -lgvc to your compile line
If there's an error about missing header files, maybe libgraphviz-dev isn't installed:
sudo apt install libgraphviz-dev
*/
template<class T>
void Tree<T>::make_image_recur(Agraph_t *g, Agnode_t *parent, node<T> *place){
	Agnode_t *us = agnode(g, (char*)to_string(place->data).c_str(), 1); // problem later because a T isn't a char*
	if(parent)
		agedge(g, parent, us, (char*)"", 1);
	if(place->left)
		make_image_recur(g, us, place->left);
	if(place->right)
		make_image_recur(g, us, place->right);
}

template<class T>
void Tree<T>::make_image(string name){
	Agraph_t *g;
	g = agopen((char*)"G", Agdirected, 0);

	// Go through the tree, and add all our nodes!
	// Add our own node
	// If there is a left subtree, add the left subtree
	// If there is a right subtree, add the right subtree
	make_image_recur(g, 0, root);

	GVC_t* gvc = gvContext();
	gvLayout(gvc, g, "dot");
	gvRenderFilename(gvc, g, "png", (name + ".png").c_str());
	gvFreeLayout(gvc, g);
	agclose(g);


}

#endif
template<class T>
void Tree<T>::remove(T data){
	node<T> *place = root;
	node<T> *parent = 0;
	while(place && place->data != data){
		parent = place;
		if(place->data > data)
			place = place->left;
		else
			place = place->right;
	}
	if(!place)
		return;
	// Find the predecessor
	if(place->left){
		node<T> *predecessor = place->left;
		while(predecessor->right){
			predecessor = predecessor->right;
		}
		T hold_data = predecessor->data;
		remove(predecessor->data);
		place->data = hold_data; // Will this cause an extra destructor call?
		return;
	}
	if(place->right){
		node<T> *predecessor = place->right;
		while(predecessor->left){
			predecessor = predecessor->left;
		}
		T hold_data = predecessor->data;
		remove(predecessor->data);
		place->data = hold_data; // Will this cause an extra destructor call?
		return;
	}
	
	// This only works if place is a leaf
	// That's the only case left!  place->left and place->right are both null
	if(parent->right == place)
		parent->right = 0;
	else
		parent->left = 0;
	delete place;
}


// A workaround for the parameter
// Caution:  Don't use this if you expect the recursion to stop when place == null
template<class T>
void Tree<T>::print_inorder(node<T>* place){
	if(!place)
		place = root;
	// This would be where code for preorder traversal goes
	if(place->left)
		print_inorder(place->left);
	// This place for inorder
	
	cout << place->data << " ";

	if(place->right)
		print_inorder(place->right);
	// This place down here for postorder traversal
	if(place == root)
		cout << endl;
}

template<class T>
void Tree<T>::rotate_left(node<T> **place){
	if(place == 0)
		place = &root;
	node<T> *old_root = *place;
	node<T> *new_root = (*place)->right;
	if(!new_root)
		return;
	old_root->right = new_root->left;
	new_root->left = old_root;
	*place = new_root;
}

template<class T>
void Tree<T>::rotate_right(node<T> **place){
	if(place == 0)
		place = &root;
	node<T> *old_root = *place;
	node<T> *new_root = (*place)->left;
	if(!new_root)
		return;
	old_root->left = new_root->right;
	new_root->right = old_root;
	*place = new_root;
}

/* Sorry, it's not this simple! */
template<class T>
void Tree<T>::improve_balance(node<T> **place){
	/* if the balance is really bad:
	 * 	Do a rotation the correct way to make it better!
	 */
	if(place == 0)
		place = &root;
	if(! *place)
		return;
	improve_balance(&(*place)->right);
	if(! *place)
		return;
	improve_balance(&(*place)->left);
	if(! *place)
		return;
	int left_depth = depth_from_place((*place)->left);
	int right_depth = depth_from_place((*place)->right);
	if(left_depth > right_depth + 1)
		rotate_right(&root);
	else if(right_depth > left_depth + 1)
		rotate_left(&root);
	else
		cout << "No rotation:  " << left_depth << " " << right_depth << "\n";
}

int maximum(int a, int b){
	return (a>b)? a:b;
}
template<class T>
int Tree<T>::depth_from_place(node<T> *place){
	if(!place)
		return 0;
//	return maximum(depth_from_place(place->left), depth_from_place(place->right)) + 1;
	return depth_from_place(place->left) + depth_from_place(place->right) + 1;
}
#endif