#ifndef BINARY_SEARCH_TREE_ITERATIVE
#define BINARY_SEARCH_TREE_ITERATIVE

#ifndef nullptr
#define nullptr 0
#endif

#include <cassert>
#include <stack>
#include "Exception.h"
#include "Binary_search_node_iterative.h"

template <typename Type>
class Binary_search_tree {
	private:
		Binary_search_node<Type> *root_node;
		Binary_search_node<Type> *root() const;

	public:
		Binary_search_tree();
		~Binary_search_tree();

		bool empty() const;
		int size() const;
		int height() const;

		Type front() const;
		Type back() const;
		bool find( Type const & ) const;

		bool insert( Type const & );
		bool erase( Type const & );
		void clear();
};

template <typename Type>
Binary_search_tree<Type>::Binary_search_tree():
root_node( nullptr ) {
}

template <typename Type>
Binary_search_tree<Type>::~Binary_search_tree() {
	clear();
}

template <typename Type>
Binary_search_node<Type> *Binary_search_tree<Type>::root() const {
	return root_node;
}

template <typename Type>
bool Binary_search_tree<Type>::empty() const {
	return root() == nullptr;
}

template <typename Type>
int Binary_search_tree<Type>::size() const {
	if ( root() == nullptr ) {
		return 0;
	}

	std::stack< Binary_search_node<Type> * > depth_stack;

	int tree_size = 0;
	depth_stack.push( root() );

	while( !depth_stack.empty() ) {
		Binary_search_node<Type> *ptr = depth_stack.top();
		depth_stack.pop();
		++tree_size;

		if ( ptr->right() != nullptr ) {
			depth_stack.push( ptr->right() );
		}

		if ( ptr->left() != nullptr ) {
			depth_stack.push( ptr->left() );
		}
	} 

	return tree_size;
}

template <typename Type>
int Binary_search_tree<Type>::height() const {
	if ( root() == nullptr ) {
		return -1;
	}

	std::stack< Binary_search_node<Type> * > depth_stack;
	Binary_search_node<Type> *last_popped = nullptr;

	depth_stack.push( root() );
	int depth = 0;

	while ( depth_stack.top()->left() != nullptr ) {
		depth_stack.push( depth_stack.top()->left() );
		++depth;
	}

	int height = depth;

	while( !depth_stack.empty() ) {
		if ( depth_stack.top()->right() != nullptr && depth_stack.top()->right() != last_popped ) {
			depth_stack.push( depth_stack.top()->right() );
			++depth;
			height = std::max( height, depth );

			while ( depth_stack.top()->left() != nullptr ) {
				depth_stack.push( depth_stack.top()->left() );
				++depth;
				height = std::max( height, depth );
			}
		} else {
			last_popped = depth_stack.top();
			depth_stack.pop();
			--depth;
		}
	} 

	return height;
}

template <typename Type>
Type Binary_search_tree<Type>::front() const {
	if ( empty() ) {
		throw underflow();
	}

	Binary_search_node<Type> *ptr = root();
	
	while ( ptr->left() != nullptr ) {
		ptr = ptr->left();
	}

	return ptr->retrieve();
}

template <typename Type>
Type Binary_search_tree<Type>::back() const {
	if ( empty() ) {
		throw underflow();
	}

	Binary_search_node<Type> *ptr = root();
	
	while ( ptr->right() != nullptr ) {
		ptr = ptr->right();
	}

	return ptr->retrieve();
}

template <typename Type>
bool Binary_search_tree<Type>::find( Type const &obj ) const {
	if ( empty() ) {
		throw underflow();
	}

	Binary_search_node<Type> *current = root();
	
	while ( true ) {
		if ( current->retrieve() == obj ) {
			return true;
		} else if ( current->retrieve() > obj ) {
			if ( current->left() == nullptr ) {
				return false;
			} else {
				current = current->left();
			}
		} else {
			if ( current->right() == nullptr ) {
				return false;
			} else {
				current = current->right();
			}
		}
	}
}

template <typename Type>
void Binary_search_tree<Type>::clear() {
	if ( root() == nullptr ) {
		return;
	}

	std::stack< Binary_search_node<Type> * > depth_stack;

	depth_stack.push( root() );

	while( !depth_stack.empty() ) {
		Binary_search_node<Type> *ptr = depth_stack.top();
		depth_stack.pop();

		if ( ptr->right() != nullptr ) {
			depth_stack.push( ptr->right() );
		}

		if ( ptr->left() != nullptr ) {
			depth_stack.push( ptr->left() );
		}

		delete ptr;
	} 
}

template <typename Type>
bool Binary_search_tree<Type>::insert( Type const &obj ) {
	if ( empty() ) {
		root_node = new Binary_search_node<Type>( obj );
		return true;
	}

	Binary_search_node<Type> *current = root();
	
	while ( true ) {
		if (  current->retrieve() == obj ) {
			return false;
		}

		if ( current->retrieve() > obj ) {
			if ( current->left() == nullptr ) {
				current->left_tree = new Binary_search_node<Type>( obj );
				return true;
			} else {
				current = current->left();
			}
		} else {
			if ( current->right() == nullptr ) {
				current->right_tree = new Binary_search_node<Type>( obj );
				return true;
			} else {
				current = current->right();
			}
		}
	}
}

template <typename Type>
bool Binary_search_tree<Type>::erase( Type const &obj ) {
	if ( empty() ) {
		return false;
	}

	if ( root()->retrieve() == obj ) {
		if ( root()->left() == nullptr && root()->right() == nullptr ) {
			root_node = nullptr;

			delete root();
		} else if ( root()->left() == nullptr ) {
			Binary_search_node<Type> *tmp = root();
			root_node = root()->right();

			delete tmp;
		} else if ( root()->right() == nullptr ) {
			Binary_search_node<Type> *tmp = root();
			root_node = root()->left();

			delete tmp;
		} else {
			if ( root()->right()->left() == nullptr ) {
				root()->element = root()->right()->retrieve();
				Binary_search_node<Type> *tmp = root()->right();
				root()->right_tree = root()->right()->right();
				delete tmp;
			} else {
				Binary_search_node<Type> *ptr = root()->right();
				Binary_search_node<Type> *parent;
	
				while ( ptr->left() != nullptr ) {
					parent = ptr;
					ptr = ptr->left();
				}

				root()->element = ptr->retrieve();

				if ( ptr->right() == nullptr ) {
					parent->left_tree = nullptr;
				} else {
					parent->left_tree = ptr->right();
				}

				delete ptr;
			}
		}

		return true;
	}

	Binary_search_node<Type> *current = root();
	Binary_search_node<Type> *parent;
	bool is_left_subtree;
	
	while ( true ) {
		if ( current->retrieve() == obj ) {
			break;
		} else if ( current->retrieve() > obj ) {
			if ( current->left() == nullptr ) {
				return false;
			} else {
				parent = current;
				current = current->left();
				is_left_subtree = true;
			}
		} else {
			if ( current->right() == nullptr ) {
				return false;
			} else {
				parent = current;
				current = current->right();
				is_left_subtree = false;
			}
		}
	}

	if ( current->left() == nullptr && current->right() == nullptr ) {
		if ( is_left_subtree ) {
			parent->left_tree = nullptr;
		} else {
			parent->right_tree = nullptr;
		}

		delete current;
	} else if ( current->left() == nullptr ) {
		if ( is_left_subtree ) {
			parent->left_tree = current->right();
		} else {
			parent->right_tree = current->right();
		}

		delete current;
	} else if ( current->right() == nullptr ) {
		if ( is_left_subtree ) {
			parent->left_tree = current->left();
		} else {
			parent->right_tree = current->left();
		}

		delete current;
	} else {
		if ( current->right()->left() == nullptr ) {
			current->element = current->right()->retrieve();
			Binary_search_node<Type> *tmp = current->right();
			current->right_tree = current->right()->right();
			delete tmp;
		} else {
			Binary_search_node<Type> *ptr = current->right();

			while ( ptr->left() != nullptr ) {
				parent = ptr;
				ptr = ptr->left();
			}

			current->element = ptr->retrieve();

			if ( ptr->right() == nullptr ) {
				parent->left_tree = nullptr;
			} else {
				parent->left_tree = ptr->right();
			}

			delete ptr;
		}
	}

	return true;
}

#endif