#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_SERACH_TREE
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINARY_SERACH_TREE

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

#include "Binary_search_node.h"
#include "Exception.h"

namespace Data_structures {
	template <typename Type>
	class Binary_search_tree {
		protected:
			Binary_node<Type> *root_node;

		public:
			Binary_search_tree();

			Binary_search_node<Type> *root() const;

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

			Type next( const Type & ) const;
			Type previous( const Type & ) const;
			Type at( int ) const;
			Type operator[]( int ) const;

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

	template <typename Type>
	Binary_search_tree<Type>::Binary_search_tree():
	root_node( 0 ) {
		// Empty constructor
	}

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

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

	template <typename Type>
	int Binary_search_tree<Type>::size() const {
		return empty() ? 0 : root()->size();
	}

	template <typename Type>
	int Binary_search_tree<Type>::height() const {
		return empty() ? -1 : root()->height();
	}

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

		return root()->front();
	}

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

		return root()->back();
	}

	template <typename Type>
	bool Binary_search_tree<Type>::find( Type const &obj ) const {
		return empty() ? false : root()->find( obj );
	}

	template <typename Type>
	Type Binary_search_tree<Type>::at( int n ) const {
		if ( n < 0 || n >= size() ) {
			return Type();
		}

		return root()->at( n );
	}

	template <typename Type>
	Type Binary_search_tree<Type>::operator[]( int n ) const {
		return root()->at( n );
	}

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

		return root()->next( obj );
	}

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

		return root()->previous( obj );
	}

	template <typename Type>
	void Binary_search_tree<Type>::clear() {
		if ( !empty() ) {
			root()->clear();
		}
	}

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

		return root()->insert( obj );
	}

	template <typename Type>
	bool Binary_search_tree<Type>::erase( Type const &obj ) {
		return empty() ? false : root()->erase( obj, root_node );
	}
}

#endif