#include "BSTree.h"
#include <cstdlib>
#include <iostream>
//#include <vector>

BSTree::BSTree(){
	this->root = NULL;
}

BSTree::BSTree(const BSTree &old_tree){
	//loop thru and pre order copy into a new (this) tree
/*	this->root = new Node();
	this->root->parent = NULL;
	this->root->left = old_tree->left;
	this->root->right = old_tree->right;
*/
	this->root = NULL;
	copyTree(old_tree.root);
}

BSTree::~BSTree(){
	deleteTree();
}

bool BSTree::empty(){
	return this->root == NULL;

}

bool BSTree::insert(int val){
	bool nextup = false;
	bool retval = false;
	if(this->root == NULL){
		this->root = new Node();
		this->root->value = val;
		this->root->parent = this->root->left = this->root->right = NULL;
		return true;
	} else {
		Node * toInsert = new Node();
		toInsert->value = val;
		toInsert->left = toInsert->right = NULL;
		Node * temp = root;
		bool rightside = false;
		while(temp){
			toInsert->parent = temp;
			if(val < temp->value){
				temp = temp->left;
				rightside = false;
			} else if(val > temp->value){
				temp = temp->right;
				rightside = true;
			} else /*if(val == temp->value)*/{
				//here they are equal
				return false;
			}
			if(!temp){
				//temp is now null
				if(rightside){
					toInsert->parent->right = toInsert;
				} else {
					toInsert->parent->left = toInsert;
				}
			}
		}
	}

}

BSTree::Node * BSTree::search(Node * n, int val){
	if(n != NULL){
		if(n->value == val){
			std::cout << "found" << std::endl;
			return n;
		}
		return search(n->left, val);
		return search(n->right, val);
	}
	std::cout << "missing" << std::endl;
	//return NULL;
}

bool BSTree::find(int val){
	if(root == NULL){
		return false;
	}
	return search(root, val) != NULL;
	//return found != NULL;

}

void BSTree::deleteTreeLoop(Node * n){
    if(n != NULL){
        deleteTreeLoop(n->left);
        deleteTreeLoop(n->right);
		delete n;
    }
}

void BSTree::deleteTree(){
	if(root == NULL){
		return;
	}
	deleteTreeLoop(root);
}

void BSTree::copyTreeLoop(Node * n){
    if(n != NULL){
		//code to iterate and copy thru...
		//Node * newNode = new Node();
		//newNode = n;
		insert(n->value);

        copyTreeLoop(n->left);
        copyTreeLoop(n->right);
    }
}

void BSTree::copyTree(Node * n){
	if(n == NULL){
		return;
	}
	copyTreeLoop(n);
}

BSTree::Node * BSTree::smallestNode(Node * n){
	Node * retval = NULL;
	if(n != NULL){
		while(n->left){
			n = n->left;
		}
		if(n->right){
			n->right->parent = n->parent;
			n->parent->right = n->right;
			//node was pinched out of the tree
		}
		retval = n;
	}
	return retval;
}

BSTree::Node * BSTree::largestNode(Node * n){
	Node * retval = NULL;
	if(n != NULL){
		//retval = n;
		while(n->right){
			n = n->right;
		}
		//if it has a left child set left child to where it used to be ***********
		if(n->left){
			n->left->parent = n->parent;
			n->parent->left = n->left;
			//n left is pushed up to where n used to be
		}
		//n now holds the value of the greatest node in the tree
		retval = n;
	}
	return retval;
}

bool BSTree::removeLoop(Node * n, int val){
    if(n != NULL){
		if(n->value == val){
			//So add greatest in left tree, or least in right tree into the node hole.
			//add a function: greatest in tree and pass the left child to it
			//add a function: least in tree and pass right child to it if there is no left child
			//if no children at all, do nothing
			if(n->left == NULL && n->right == NULL){
				//no children
				delete n;
				return true;
			}
			Node * temp = n;
			//here we have atleast one child, so we try the left side first.
			if(n->left){
				//left child exists, so we will find the greatest node in a tree with root being left child
				Node * greatest = largestNode(n->left);
				n->value = greatest->value;
				//should now have the greatest from the smaller tree inserted where the old node was
				delete greatest;
			} else {
				//right child exists, so we find least node in a tree with root being right child.
				Node * least = smallestNode(n->right);
				n->value = least->value;
				delete least;
			}
			//value is found, so no need to recurse more once its gone
			return true;
		}
        return removeLoop(n->left, val);
        return removeLoop(n->right, val);
    }
    return false;
}

bool BSTree::remove(int num){
    if(root == NULL){
        return false;
    }
    return removeLoop(root, num);

}

void BSTree::fillArrayLoop(std::vector<int> &list, Node * n){
	if(n != NULL){
        fillArrayLoop(list, n->left);
		list.push_back(n->value);
        fillArrayLoop(list, n->right);
    }
}

void BSTree::fillArray(std::vector<int> &list){
	if(root == NULL){
		return;
	}
	Node * n = root;
	fillArrayLoop(list, root);
}

void BSTree::sortedArray(std::vector<int> &list){
	//So like... put the list into a tree, then remove them into an array of size(list)
	//and yeah that? or are we overwriting list to hold this new array because we have
	//its address
	fillArray(list);

}