#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_B23_TREE
#define CA_UWATERLOO_ALUMNI_DWHARDER_B23_TREE

#include <cassert>
#include <ostream>

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.
// 2-3 Trees are B-trees with L = M = 3

namespace Data_structures {
	/****************************************************
	 * ************************************************ *
	 * *                 B 2-3 Trees                  * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	class B23_tree {
		public:
			B23_tree();
			~B23_tree();
			bool empty() const;
			int size() const;
			int count( Type const & ) const;
			bool validate() const;

			Type front() const;
			Type back() const;
			void print() const;

			void clear();
			void insert( Type const & );

			class iterator;

			iterator begin();
			iterator end();
			iterator find( Type const & );

		private:
			class tree_node;
			class internal;

			tree_node *root_node;

		friend class iterator;
	};

	/****************************************************
	 * ************************************************ *
	 * *              2-3 Tree Leaf Node              * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	class B23_tree<Type>::tree_node {
		public:
			int node_count;
			Type values[2];
			tree_node();

			tree_node( Type const & );

			virtual Type front() const;
			virtual Type back() const;
			virtual void print( int ) const;
			virtual bool leaf() const;
			virtual tree_node *child( int ) const;

			virtual void clear();
			virtual tree_node *insert( Type const & );
	};

	/****************************************************
	 * ************************************************ *
	 * *            2-3 Tree Internal Node            * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	class B23_tree<Type>::internal : public tree_node {
		using B23_tree<Type>::tree_node::node_count;
		using B23_tree<Type>::tree_node::values;

		public:
			tree_node *children[3];

			internal( tree_node *, tree_node * );
			internal( Type const &, tree_node *, tree_node * );

			virtual Type front() const;
			virtual Type back() const;
			virtual void print( int ) const;
			virtual bool leaf() const;
			virtual tree_node *child( int ) const;

			virtual void clear();
			virtual tree_node *insert( Type const & );
	};

	/****************************************************
	 * ************************************************ *
	 * *                   Iterator                   * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	class B23_tree<Type>::iterator {
		public:
			iterator();

			iterator &operator++();
			iterator operator++( int );
			iterator &operator--();
			iterator operator--( int );
			Type operator*();
			bool operator==( iterator const &rhs ) const;
			bool operator!=( iterator const &rhs ) const;

		private:
			iterator( tree_node * );
			tree_node *current_node;
			int index;

			class stack_node;
			stack_node *stack_top;

		friend class B23_tree;
	};

	/****************************************************
	 * Stack Node Class
	 *   class B23_tree<Type>::iterator :: stack_node
	 *
	 * Author: Douglas Wilhelm Harder
	 * 2009-10-10
	 *
	 * A tree_node used to create a stack where each entry
	 * of the stack stores:
	 *   - A pointer to a tree tree_node, and
	 *   - A pointer to the next stack tree_node.
	 *
	 * This stack is used for implementing a depth-
	 * first traversal of the tree.
	 ****************************************************/

	template <typename Type>
	class B23_tree<Type>::iterator::stack_node {
		public:
			tree_node *pointer;
			int index;
			stack_node *next;

			stack_node( tree_node *, int, stack_node * );
			stack_node( stack_node const & );

		friend class B23_tree<Type>::iterator;
	};

	/****************************************************
	 * ************************************************ *
	 * *             2-3 Tree Definitions             * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	B23_tree<Type>::B23_tree():
	root_node( new tree_node() ) {
		// Empty constructor
	}

	/*
	 * Destructor
	 *    B23_tree<Type> :: ~B23_tree()
	 *
	 * Walk through the skip list and delete
	 * all of the nodes. O(n)
	 */

	template <typename Type>
	B23_tree<Type>::~B23_tree() {
		root_node->clear();
	}

	template <typename Type>
	void B23_tree<Type>::print() const {
		root_node->print( 0 );
	}

	template <typename Type>
	Type B23_tree<Type>::front() const {
		if ( empty() ) {
			return Type();
		}

		root_node->front();
	}

	template <typename Type>
	Type B23_tree<Type>::back() const {
		if ( empty() ) {
			return Type();
		}

		root_node->back();
	}

	template <typename Type>
	bool B23_tree<Type>::empty() const {
		return  root_node->node_count == 0;
	}

	/*
	 * Insertion
	 *    B23_tree<Type> :: insert( Type const & )
	 *
	 * Insert a new tree_node into the root_node.
	 * If the returned value is non-zero, replace
	 * the root_node tree_node with an internal tree_node with two
	 * childrenren.
	 */

	template <typename Type>
	void B23_tree<Type>::insert( Type const &obj ) {
		tree_node *result = root_node->insert( obj );

		if ( result != 0 ) {
			root_node = new internal( root_node, result );
		}
	}

	/*
	 * Iterator
	 *   iterator B23_tree<Type> :: begin()
	 *
	 * Returns an in-order traversing
	 * iterator which initially refers to the front tree_node.
	 *
	 * O(ln(n))
	 */

	template <typename Type>
	typename B23_tree<Type>::iterator B23_tree<Type>::begin() {
		return iterator( root_node );
	}

	template <typename Type>
	typename B23_tree<Type>::iterator B23_tree<Type>::end() {
		return iterator();
	}

	/****************************************************
	 * ************************************************ *
	 * *        2-3 Tree Leaf Node Definitions        * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	B23_tree<Type>::tree_node::tree_node():
	node_count( 0 ) {
		// Empty constructor
	}

	template <typename Type>
	B23_tree<Type>::tree_node::tree_node( Type const &obj ):
	node_count( 1 ) {
		values[0] = obj;
	}

	template <typename Type>
	void B23_tree<Type>::tree_node::clear() {
		delete this;
	}

	template <typename Type>
	void B23_tree<Type>::tree_node::print( int n ) const {
		if ( this == 0 ) {
			return;
		}

		for ( int i = 0; i < node_count; ++i ) {
			for ( int j = 0; j < n; ++j ) {
				std::cout << '\t';
			}

			std::cout << values[i] << std::endl;
		}
	}

	template <typename Type>
	Type B23_tree<Type>::tree_node::front() const {
		return values[0];
	}

	template <typename Type>
	Type B23_tree<Type>::tree_node::back() const {
		return values[node_count - 1];
	}

	template <typename Type>
	bool B23_tree<Type>::tree_node::leaf() const {
		return true;
	}

	template <typename Type>
	typename B23_tree<Type>::tree_node *B23_tree<Type>::tree_node::child( int n ) const {
		return 0;
	}

	template <typename Type>
	typename B23_tree<Type>::tree_node *B23_tree<Type>::tree_node::insert( Type const &obj ) {
		switch ( node_count ) {
			case 0:
				values[0] = obj;
				node_count = 1;
				return 0;
			case 1:
				if ( obj == values[0] ) {
					return 0;
				}

				if ( obj > values[0] ) {
					values[1] = obj;
				} else {
					values[1] = values[0];
					values[0] = obj;
				}

				node_count = 2;
				return 0;
			case 2:
				tree_node *tmp;

				if ( obj > values[1] ) {
					tmp = new tree_node( obj );
				} else {
					if ( obj == values[0] || obj == values[1]  ) {
						return 0;
					}

					tmp = new tree_node( values[1] );

					if ( obj > values[0] ) {
						values[1] = obj;
					} else {
						values[1] = values[0];
						values[0] = obj;
					}
				}

				return tmp;
			default:
				assert( false );
		}
	}

	/****************************************************
	 * ************************************************ *
	 * *      2-3 Tree Internal Node Definitions      * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	B23_tree<Type>::internal::internal( tree_node *left, tree_node *middle ):
	tree_node() {
		children[0] = left;
		children[1] = middle;
		values[0] = children[0]->values[1];

		node_count = 1;
		children[0]->node_count = 1;

		children[2] = 0;
	}

	template <typename Type>
	B23_tree<Type>::internal::internal( Type const &obj, tree_node *left, tree_node *middle ):
	tree_node() {
		children[0] = left;
		children[1] = middle;
		values[0] = obj;

		node_count = 1;

		children[2] = 0;
	}

	template <typename Type>
	typename B23_tree<Type>::tree_node *B23_tree<Type>::internal::insert( Type const &obj ) {
		assert( node_count == 1 || node_count == 2 );

		if ( obj == values[0] ) {
			return 0;
		}

		if ( obj < values[0] ) {
			tree_node *result = children[0]->insert( obj );

			if ( result == 0 ) {
				return 0;
			} else {
				// The left subtree split

				if ( node_count == 1 ) {
					children[2] = children[1];
					children[1] = result;

					values[1] = values[0];
					values[0] = children[0]->values[1];

					children[0]->node_count = 1;
					node_count = 2;

					return 0;
				} else {
					assert( node_count == 2 );

					internal *tmp = new internal( values[1], children[1], children[2] );

					children[0]->node_count = 1;
					children[1] = result;

					values[1] = values[0];
					values[0] = children[0]->values[1];

					node_count = 1;

					return tmp;
				}
			}
		} else {
			assert( obj > values[0] );

			if ( node_count == 1 ) {
				tree_node *result = children[1]->insert( obj );

				if ( result != 0 ) {
					children[2] = result;

					values[1] = children[1]->values[1];

					children[1]->node_count = 1;
					node_count = 2;
				}

				return 0;
			} else {
				assert( node_count == 2 );

				if ( obj == values[1] ) {
					return 0;
				}

				if ( obj < values[1] ) {
					tree_node *result = children[1]->insert( obj );

					if ( result == 0 ) {
						return 0;
					} else {
						internal *tmp = new internal( values[1], result, children[2] );

						values[1] = children[1]->values[1];

						children[1]->node_count = 1;

						node_count = 1;

						return tmp;
					}
				} else {
					assert( obj > values[1] );

					tree_node *result = children[2]->insert( obj );

					if ( result == 0 ) {
						return 0;
					} else {
						internal *tmp = new internal( children[2]->values[1], children[2], result );

						children[2]->node_count = 1;

						node_count = 1;

						return tmp;
					}
				}
			}
		}
	}

	template <typename Type>
	void B23_tree<Type>::internal::clear() {
		for ( int i = 0; i < node_count; ++i ) {
			if ( children[i] == 0 ) {
				break;
			}

			children[i]->clear();
		}

		tree_node::clear();
	}

	template <typename Type>
	void B23_tree<Type>::internal::print( int n ) const {
		if ( this == 0 ) {
			return;
		}

		for ( int i = 0; i < node_count; ++i ) {
			children[i]->print( n + 1 );

			for ( int j = 0; j < n; ++j ) {
				std::cout << '\t';
			}

			std::cout << values[i] << std::endl;
		}

		children[node_count]->print( n + 1 );
	}

	template <typename Type>
	Type B23_tree<Type>::internal::front() const {
		children[0]->front();
	}

	template <typename Type>
	Type B23_tree<Type>::internal::back() const {
		children[node_count]->back();
	}

	template <typename Type>
	bool B23_tree<Type>::internal::leaf() const {
		return false;
	}

	template <typename Type>
	typename B23_tree<Type>::tree_node *B23_tree<Type>::internal::child( int n ) const {
		return children[n];
	}

	/****************************************************
	 * ************************************************ *
	 * *            Iterator Definitions              * *
	 * ************************************************ *
	 ****************************************************/

	template <typename Type>
	B23_tree<Type>::iterator::iterator():
	stack_top( 0 ) {
		// Empty constructor
	}

	template <typename Type>
	B23_tree<Type>::iterator::iterator( tree_node *n ):
	stack_top( new stack_node( n, 0, 0 ) ) {
		while ( !stack_top->pointer->leaf() ) {
			stack_top = new stack_node( stack_top->pointer->child(0), 0, stack_top );
		}
	}

	template <typename Type>
	typename B23_tree<Type>::iterator &B23_tree<Type>::iterator::operator++() {
		++stack_top->index;

		if ( stack_top->pointer->leaf() ) {
			while ( stack_top != 0 && stack_top->index == stack_top->pointer->node_count ) {
				stack_node *tmp = stack_top;
				stack_top = stack_top->next;
				delete tmp;
			}
		} else {
			stack_top = new stack_node( stack_top->pointer->child( stack_top-> index ), 0, stack_top );

			while ( !stack_top->pointer->leaf() ) {
				stack_top = new stack_node( stack_top->pointer->child(0), 0, stack_top );
			}
		}

		return *this;
	}

	template <typename Type>
	typename B23_tree<Type>::iterator B23_tree<Type>::iterator::operator++( int ) {
		iterator copy = *this;

		++(*this);

		return copy;
	}

	template <typename Type>
	typename B23_tree<Type>::iterator &B23_tree<Type>::iterator::operator--() {
		--stack_top->index;

		if ( stack_top->pointer->leaf() ) {
			while ( stack_top != 0 && stack_top->index == -1 ) {
				stack_node *tmp = stack_top;
				stack_top = stack_top->next;
				delete tmp;
			}
		} else {
			stack_top = new stack_node( stack_top->pointer->child( stack_top-> index ), 0, stack_top );

			while ( !stack_top->pointer->leaf() ) {
				stack_top = new stack_node( stack_top->pointer->child(0), 0, stack_top );
			}
		}

		return *this;
	}

	template <typename Type>
	typename B23_tree<Type>::iterator B23_tree<Type>::iterator::operator--( int ) {
		iterator copy = *this;

		--(*this);

		return copy;
	}

	template <typename Type>
	Type B23_tree<Type>::iterator::operator*() {
		return stack_top->pointer->values[stack_top->index];
	}

	template <typename Type>
	bool B23_tree<Type>::iterator::operator==( iterator const &rhs ) const {
		if ( stack_top == 0 || rhs.stack_top == 0 ) {
			return ( stack_top == rhs.stack_top );
		}

		return ( stack_top->pointer == rhs.stack_top->pointer );
	}

	template <typename Type>
	bool B23_tree<Type>::iterator::operator!=( iterator const &rhs ) const {
		if ( stack_top == 0 || rhs.stack_top == 0 ) {
			return ( stack_top != rhs.stack_top );
		}

		return ( stack_top->pointer != rhs.stack_top->pointer );
	}

	template <typename Type>
	B23_tree<Type>::iterator::stack_node::stack_node( tree_node *p, int i, stack_node *n ):
	pointer( p ),
	index( i ),
	next( n ) {
		// Empty constructor
	}

	template <typename Type>
	B23_tree<Type>::iterator::stack_node::stack_node( stack_node const &tree_node ):
	pointer( tree_node.pointer ),
	index( tree_node.index ),
	next( tree_node.next ) {
		// Empty constructor
	}
}

#endif