#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 ) {
	// empty
}

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;
}

/*
 *  int size()
 *
 *  Return the size of the current tree.
 *  This is an iterative implementation using a stack.
 *
 *  This implementation uses a stack at most equal to 2*h + 1.
 *
 *  It places the root node onto the stack and sets the 'tree_size' to zero.
 *  
 *  While the stack is not empty:
 *    - Pop the top of the stack
 *    - Increment the value of 'tree_size'
 *    - Place any children of the popped node onto the stack
 *
 *  When the stack is empty, 'tree_size' stores the number of nodes in the tree.
 */

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

	// Perform a depth-first traversal of the tree

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

	// Initialize 'tree_size' to zero and push the
	// root node onto the top of the stack.

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

	// While the stack is not empty:
	//   - pop the top of the stack
	//   - increment 'tree_size'
	//   - push any children onto the stack

	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;
}

/*
 *  int height()
 *
 *  Return the height of the current tree.
 *  This is an iterative implementation using a stack.
 *
 *  This implementation uses a stack exactly equal to h + 1.
 *
 *  It stores the 'depth' of the current top of the stack in a local variable
 *  and as the tree is traversed (depth-first traversal), the value of 'depth'
 *  is appropriately modified.  Here we must be far more careful with our stack.
 *
 *  The 'height' is the maximum value that 'depth' attains.
 */

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

	// Perform a depth-first traversal of the tree

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

	// We begin by placing all nodes along the left-most branch of
	// the tree into the stack:
	//                     C
	//                    / \
	//                   B   ?
	//                  / \
	//      A          A   ?
	//      B           \
	//      C            ?

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

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

	// The 'height' of the tree is at least equal to the current 'depth'
	int height = depth;

	while( !depth_stack.empty() ) {
		if ( depth_stack.top()->right() != nullptr && depth_stack.top()->right() != last_popped ) {
			// If there is a right sub-tree, and that right sub-tree was
			// not the last object that was popped off the stack, put it
			// onto the stack and then push all nodes along its left-most
			// branch onto the stack:
			//                     C
			//                    / \
			//                   *   F
			//                      / \
			//      D              E   ?
			//      E             / \
			//      F            D   ?
			//      G             \
			//      ?              ?
			//
			// At each step, increment the 'depth' and check if the new depth
			// greater than the current value of 'height'.

			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 {
			// Else, there is no right sub-tree, or we have already
			// just visited it, so pop the current top of the stack
			// and record that it has been the last popped node.
			//  - decrement the depth

			last_popped = depth_stack.top();
			depth_stack.pop();
			--depth;
		}
	} 

	// At this point, 'height' is the maximum depth of any node in the tree

	return height;
}

/*
 *  Type front() const
 *
 *  The front is defined as that element that precedes all other elements in the
 *  tree (i.e., the first element).  This value is stored in the left-most node.
 *
 *  It is an undefined operation to call 'front' on an empty tree.
 *
 *  Assign a pointer to the address of the root node.
 *  While the left sub-tree is not assigned 'nullptr',
 *      assign the pointer to the address of that sub-tree.
 */

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();
}

/*
 *  Type back() const
 *
 *  The back is defined as that element that succeeds all other elements in the
 *  tree (i.e., the last element).  This value is stored in the right-most node.
 *
 *  It is an undefined operation to call 'back' on an empty tree.
 *
 *  Assign a pointer to the address of the root node.
 *  While the right sub-tree is not assigned 'nullptr',
 *      assign the pointer to the address of that sub-tree.
 */

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();
}

/*
 *  bool find( Type const & ) const
 *
 *  If the tree is empty, throw an underflow exception.
 *
 *  Set a pointer to the root node then iterate:
 *     - There is an object in the node pointed to
 *     - If the object equals the argument, return true.
 *     - If the object is less than the argument:
 *          * Return false if the left sub-tree is null,
 *          * Otherwise, update the pointer to point to the left tree
 *     - Otherwise the object is greater than the argument:
 *          * Return false if the right sub-tree is null,
 *          * Otherwise, update the pointer to point to the right tree
 *
 */

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;
	}

	// Perform a depth-first traversal of the tree

	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;
	} 

	root_node = nullptr;
}

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();
			}
		}
	}
}

/*
 *  bool erase()
 *
 *  There are two cases:
 *   - the object being erased is stored in the root node, or
 *   - it is not in the root node.
 *
 *  There are two possible approaches to this:
 *   - Each time we delete a node, check to see whether or not it is
 *     the root node and then take the appropriate action, or
 *   - Deal with two separate cases:
 *      * One were we deal with deleting the root node, and
 *      * The general case where we are deleting a node other than the root.
 *
 *  This implementation chooses the second.
 *
 */

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

	// The object is stored in the root node

	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 {
			// Note, we could cheat here:
			//  - Find the minimum element in the right sub-tree
			//  - Recursively call delete on that element on the entire tree
			//  - The set the root node to that element
			// However, we will explicitly get that element and bring it up.

			// Two cases:
			//  - The right node is the front of the right sub-tree
			//  - The front of the right sub-tree is in the left sub-tree
			//      *        *
			//     / \      / \
			//    ?   *    ?   *
			//         \      / \
			//          ?    *   ?

			if ( root()->right()->left() == nullptr ) {
				// In this first case, copy the value in the
				// right sub-tree and then delete that node.

				root()->element = root()->right()->retrieve();
				Binary_search_node<Type> *tmp = root()->right();
				root()->right_tree = root()->right()->right();
				delete tmp;
			} else {
				// In the second, find the minimum entry in the
				// right sub-tree, copy it up, and then delete
				// that node.

				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();

				// Either the front of the right sub-tree is a leaf
				// node, or it has a right sub-tree.  In either
				// case, we appropriately update its parent.

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

				delete ptr;
			}
		}

		return true;
	}

	// The object is stored in any other node other than the root node

	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