#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_SEARCH_NODE
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_SEARCH_NODE

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2011 by Douglas Wilhelm Harder.  All rights reserved.

#include <cassert>
#include <iostream>
using namespace std;
#include "Binary_node.h"

namespace Data_structures {
	template <typename Type>
	class Binary_search_tree;

	template <typename Type>
	class Binary_search_node:public Binary_node<Type> {
		private:
			using Binary_node<Type>::element;
			using Binary_node<Type>::left_tree;
			using Binary_node<Type>::right_tree;

			int tree_height;
			int node_count;

		public:
			using Binary_node<Type>::retrieve;
			using Binary_node<Type>::is_leaf;

			Binary_search_node( Type const & );
			Binary_search_node *left() const;
			Binary_search_node *right() const;

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

			Type next( Type const & ) const;
			Type previous( Type const & ) const;
			Type at( int ) const;

			void clear();
			bool insert( Type const & );
			bool erase( Type const &, Binary_node<Type> *& );

			friend class Binary_search_tree<Type>;
	};

	template <typename Type>
	Binary_search_node<Type>::Binary_search_node( Type const &obj ):
	Binary_node<Type>( obj ),
	node_count( 1 ) {
		// Just calls the constructor of the base class
	}

	template <typename Type>
	Binary_search_node<Type> *Binary_search_node<Type>::left() const {
		return reinterpret_cast<Binary_search_node *>( left_tree );
	}

	template <typename Type>
	Binary_search_node<Type> *Binary_search_node<Type>::right() const {
		return reinterpret_cast<Binary_search_node *>( right_tree );
	}


	template <typename Type>
	int Binary_search_node<Type>::size() const {
		return node_count;
	}

	template <typename Type>
	Type Binary_search_node<Type>::front() const {
		return ( left() == 0 ) ? retrieve() : left()->front();
	}

	template <typename Type>
	Type Binary_search_node<Type>::back() const {
		return ( right() == 0 ) ? retrieve() : right()->back();
	}

	template <typename Type>
	bool Binary_search_node<Type>::find( Type const &obj ) const {
		if ( retrieve() == obj ) {
			return true;
		} else if ( obj < retrieve() ) {
			return ( left() == 0 ) ? false : left()->find( obj );
		} else {
			assert( retrieve() < obj );
			return ( right() == 0 ) ? false : right()->find( obj );
		}
	}

	template <typename Type>
	Type Binary_search_node<Type>::next( Type const &obj ) const {
		if ( retrieve() == obj  ) {
			return ( right() == 0 ) ? obj : right()->front();
		} else if ( retrieve() > obj ) {
			Type tmp = ( left() == 0 ) ? obj : left()->next( obj );

			return ( tmp == obj ) ? retrieve() : tmp;
		} else {
			assert( retrieve() < obj );
			return ( right() == 0 ) ? obj : right()->next( obj );
		}
	}

	template <typename Type>
	Type Binary_search_node<Type>::previous( Type const &obj ) const {
		if ( retrieve() == obj  ) {
			return ( left() == 0 ) ? obj : left()->back();
		} else if ( retrieve() < obj ) {
			Type tmp = ( right() == 0 ) ? obj : right()->previous( obj );

			return ( tmp == obj ) ? retrieve() : tmp;
		} else {
			assert( retrieve() > obj );
			return ( left() == 0 ) ? obj : left()->previous( obj );
		}
	}

	template <typename Type>
	Type Binary_search_node<Type>::at( int k ) const {
		if ( k == 0 || left()->size() == k ) {
			return retrieve();
		} else if ( left()->size() > k ) {
			return left()->at( k );
		} else {
			return right()->at( k - left()->size() - 1 );
		}
	}

	template <typename Type>
	void Binary_search_node<Type>::clear() {
		if ( left() != 0 ) {
			left()->clear();
		}

		if ( right() != 0 ) {
			right()->clear();
		}

		delete this;
	}

	template <typename Type>
	bool Binary_search_node<Type>::insert( Type const &obj ) {
		if ( obj < retrieve() ) {
			if ( left() == 0 ) { 
				left_tree = new Binary_search_node<Type>( obj );
				++node_count;
				return true;
			} else {
				if ( left()->insert( obj ) ) {
					++node_count;
					return true;
				} else {
					return false;
				}
			}
		} else if ( obj > retrieve() ) {
			if ( right() == 0 ) {
				right_tree = new Binary_search_node<Type>( obj );
				++node_count;
				return true;
			} else {
				if ( right()->insert( obj ) ) {
					++node_count;
					return true;
				} else {
					return false;
				}
			}
		} else {
			return false;
		}
	}

	template <typename Type>
	bool Binary_search_node<Type>::erase( Type const &obj, Binary_node<Type> *&ptr_to_this ) {
		if ( obj == retrieve() ) {
			if ( is_leaf() ) {
				ptr_to_this = 0;
				delete this;
			} else if ( left() != 0 && right() != 0 ) {
				element = right()->front();
				right()->erase( retrieve(), right_tree );
				--node_count;
			} else {
				ptr_to_this = ( left() != 0 ) ? left() : right();
				delete this;
			}

			return true;
		} else if ( obj < retrieve() ) {
			if ( left() == 0 ) {
				return false;
			}

			if ( left()->erase( obj, left_tree ) ) {
				--node_count;
				return true;
			} else {
				return false;
			}
		} else {
			if ( right() == 0 ) {
				return false;
			}

			if ( right()->erase( obj, right_tree ) ) {
				--node_count;
				return true;
			} else {
				return false;
			}
		}
	}
}

#endif