#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SPLAY_TREE
#define CA_UWATERLOO_ALUMNI_DWHARDER_SPLAY_TREE

#include <cassert>
#include <ostream>
#include <queue>
#include <stack>

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

namespace Data_structures {
	enum rotation { TRUE, FALSE, ZIG, ZAG };

	template <typename Type>
	class Splay_tree {
		public:
			Splay_tree();
			~Splay_tree();

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

			Type front();
			Type back();
			bool member( Type const & );
			void insert( Type const & );
			void erase( Type const & );
			void clear();

		private:
			void zig();
			void zag();

			class Node {
				public:
					Type element;
					Node *left;
					Node *right;

					Node( Type const & );

					rotation member( Type const &, Node * & );
					rotation front( Node * & );
					rotation back( Node * & );
					rotation insert( Type const &, Node * & );
					void erase( Type const &, Node * & );
					void clear();

					void zig_zig( Node * & );
					void zig_zag( Node * & );
					void zag_zig( Node * & );
					void zag_zag( Node * & );
			};

			int tree_size;
			Node *root;

		template <typename T>
		friend std::ostream &operator<<( std::ostream &, const Splay_tree<T> & );
	};

	/***************************************************
	 * *********************************************** *
	 * *                                             * *
	 * *    Constructors, Destructors, operator =    * *
	 * *                                             * *
	 * *********************************************** *
	 ***************************************************/

	template <typename Type>
	Splay_tree<Type>::Splay_tree(): root( 0 ), tree_size( 0 ) {
		// does nothing
	}

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

	template <typename Type>
	Splay_tree<Type>::Node::Node( Type const &e ):element( e ), left( 0 ), right( 0 ) {
		// does nothing
	}

	/***************************************************
	 * *********************************************** *
	 * *                                             * *
	 * *              Public Accessors               * *
	 * *                                             * *
	 * *********************************************** *
	 ***************************************************/

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

	template <typename Type>
	int Splay_tree<Type>::size() const {
		return tree_size;
	}

	/***************************************************
	 * *********************************************** *
	 * *                                             * *
	 * *               Public Mutators               * *
	 * *                                             * *
	 * *********************************************** *
	 ***************************************************/

	/************************************************************************
	 * Type front()
	 *
	 *  Returns the least object in the splay tree and
	 *  splays that node to the root.
	 ************************************************************************/

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

		if ( root->front( root ) == ZIG ) {
			zig();
		}

		return root->element;
	}

	template <typename Type>
	rotation Splay_tree<Type>::Node::front( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		if ( left == 0 ) {
			return TRUE;
		} else {
			rotation value = left->front( left );

			switch( value ) {
				case TRUE:  return ZIG;
				case ZIG:   zig_zig( ptr_to_this );
				            return TRUE;
			}
		}
	}

	/************************************************************************
	 * Type back()
	 *
	 *  Returns the greatest object in the splay tree and
	 *  splays that node to the root.
	 ************************************************************************/

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

		if ( root->back( root ) == ZAG ) {
			zag();
		}

		return root->element;
	}

	template <typename Type>
	rotation Splay_tree<Type>::Node::back( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		if ( right == 0 ) {
			return TRUE;
		} else {
			rotation value = right->back( right );

			switch( value ) {
				case TRUE:  return ZAG;
				case ZAG:   zag_zag( ptr_to_this );
				            return TRUE;
			}
		}
	}

	/************************************************************************
	 * bool member( Type const &e )
	 *
	 *  Determines if there is a node in the tree with the element 'e'.
	 ************************************************************************/

	template <typename Type>
	bool Splay_tree<Type>::member( Type const &e ) {
		if ( empty() ) {
			return false;
		}

		rotation value = root->member( e, root );

		switch( value ) {
			case FALSE: return false;
			case ZIG:   zig();
			            break;
			case ZAG:   zag();
		}

		return true;
	}

	template <typename Type>
	rotation Splay_tree<Type>::Node::member( Type const &e, typename Splay_tree<Type>::Node * &ptr_to_this ) {
		if ( e < element ) {
			if ( left == 0 ) {
				return FALSE;
			} else {
				rotation value = left->member( e, left );

				switch( value ) {
					case FALSE: return FALSE;
					case TRUE:  return ZIG;
					case ZIG:   zig_zig( ptr_to_this );
					            return TRUE;
					case ZAG:   zig_zag( ptr_to_this );
					            return TRUE;
				}
			}
		} else if ( e > element ) {
			if ( right == 0 ) {
				return FALSE;
			} else {
				rotation value = right->member( e, right );

				switch( value ) {
					case FALSE: return FALSE;
					case TRUE:  return ZAG;
					case ZIG:   zag_zig( ptr_to_this );
					            return TRUE;
					case ZAG:   zag_zag( ptr_to_this );
					            return TRUE;
				}
			}
		} else {
			return TRUE;
		}
	}


	/************************************************************************
	 * void insert( Type const &e )
	 *
	 *  Insert the new object 'e' into the tree.
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::insert( Type const &e ) {
		if ( empty() ) {
			root = new Node( e );
			tree_size = 1;
			return;
		}

		rotation value = root->insert( e, root );

		switch( value ) {
			case FALSE: return;
			case ZIG:   zig();
			            break;
			case ZAG:   zag();
		}

		++tree_size;
	}

	template <typename Type>
	rotation Splay_tree<Type>::Node::insert( Type const &e, typename Splay_tree<Type>::Node * &ptr_to_this ) {
		if ( e < element ) {
			if ( left == 0 ) {
				left = new Node( e );
				return ZIG;
			} else {
				rotation value = left->insert( e, left );

				switch( value ) {
					case FALSE: return FALSE;
					case TRUE:  return ZIG;
					case ZIG:   zig_zig( ptr_to_this );
					            return TRUE;
					case ZAG:   zig_zag( ptr_to_this );
					            return TRUE;
				}
			}
		} else if ( e > element ) {
			if ( right == 0 ) {
				right = new Node( e );
				return ZAG;
			} else {
				rotation value = right->insert( e, right );

				switch( value ) {
					case FALSE: return FALSE;
					case TRUE:  return ZAG;
					case ZIG:   zag_zig( ptr_to_this );
					            return TRUE;
					case ZAG:   zag_zag( ptr_to_this );
					            return TRUE;
				}
			}
		} else {
			return FALSE;
		}
	}

	/************************************************************************
	 * void erase( Type const &e )
	 *
	 *  Remove the element 'e' from the splay tree.
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::erase( Type const &e ) {
		if ( !empty() ) {
			// Let member splay the erased element to the root 

			if ( member( e ) ) {
				--tree_size;
				root->erase( e, root );
			}
		}
	}

	template <typename Type>
	void Splay_tree<Type>::Node::erase( Type const &e, typename Splay_tree<Type>::Node * &ptr_to_this ) {
		if ( left != 0 && right != 0 ) {
			// Get the minimum element from the right sub-tree
			Node *min = right;
			Node * &ptr_to_min = right;

			while ( min->left != 0 ) {
				ptr_to_min = min->left;
				min = min->left;
			}

			element = min->element;

			ptr_to_min = min->right;

			delete min;
		} else {
			if ( left == 0 && right == 0 ) {
				ptr_to_this = 0;
			} else if ( left == 0 ) {
				ptr_to_this = right;
			} else {
				ptr_to_this = left;
			}

			delete this;
		}
	}

	/************************************************************************
	 * void clear()
	 *
	 *  Empty the splay tree
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::clear() {
		if ( !empty() ) {
			root->clear();
			root = 0;
			tree_size = 0;
		}
	}

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

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

		delete this;
	}

	/***************************************************
	 * *********************************************** *
	 * *                                             * *
	 * *            The Splay Operations             * *
	 * *                                             * *
	 * *********************************************** *
	 ***************************************************/

	/************************************************************************
	 * void zig_zig()
	 *          *              ll
	 *         / \            /  \
	 *        l   Z    ->    A    l
	 *       / \                 / \
	 *     ll   lr            llr   *
         *    /  \                     / \
         *   A    llr                lr   Z
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::Node::zig_zig( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		Node *l =   left;
		Node *ll =  left->left;
		Node *lr =  left->right;
		Node *llr = left->left->right;

		ptr_to_this = ll;
		ll->right = l;
		l->left = llr;
		l->right = this;
		left = lr;
	}

	/************************************************************************
	 * void zig_zig()
	 *          *                  lr
	 *         / \               /    \
	 *        l   Z    ->      l        *
	 *       / \              / \      / \
	 *      A   lr           A  lrl  lrr  Z
         *         /  \
         *      lrl    lrr
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::Node::zig_zag( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		Node *l =   left;
		Node *lr =  left->right;
		Node *lrl = left->right->left;
		Node *lrr = left->right->right;

		ptr_to_this = lr;
		lr->left = l;
		lr->right = this;
		l->right = lrl;
		left = lrr;
	}

	/************************************************************************
	 * void zig_zig()
	 *          *                  rl
	 *         / \               /    \
	 *        A   r    ->      *        r
	 *           / \          / \      / \
	 *         rl   Z        A  rll  rlr  Z
         *        /  \
         *     rll    rlr
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::Node::zag_zig( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		Node *r =   right;
		Node *rl =  right->left;
		Node *rll = right->left->left;
		Node *rlr = right->left->right;

		ptr_to_this = rl;
		rl->left = this;
		rl->right = r;
		right = rll;
		r->left = rlr;
	}

	/************************************************************************
	 * void zig_zig()
	 *       *                   rr
	 *      / \                 /  \
	 *     A   r       ->      r    Z
	 *        / \             / \
	 *      rl   rr          *   rrl
         *          /  \        / \
         *       rrl    Z      A   rl
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::Node::zag_zag( typename Splay_tree<Type>::Node * &ptr_to_this ) {
		Node *r =   right;
		Node *rl =  right->left;
		Node *rr =  right->right;
		Node *rrl = right->right->left;

		ptr_to_this = rr;
		rr->left = r;
		r->left = this;
		r->right = rrl;
		right = rl;
	}

	/************************************************************************
	 * void zig()
	 *   This is called from the root.
	 *
	 *          *              l
	 *         / \            / \
	 *        l   Z    ->    A   *
	 *       / \                / \
	 *      A   lr            lr   Z
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::zig() {
		Node *rt =  root;
		Node *l =   root->left;
		Node *lr =  root->left->right;

		root = l;
		l->right = rt;
		rt->left = lr;
	}

	/************************************************************************
	 * void zag()
	 *   This is called from the root.
	 *
	 *          *              r
	 *         / \            / \
	 *        A   r    ->    *   Z
	 *           / \        / \
	 *         rl   Z      A   rl
	 ************************************************************************/

	template <typename Type>
	void Splay_tree<Type>::zag() {
		Node *rt =  root;
		Node *r =   root->right;
		Node *rl =  root->right->left;

		root = r;
		r->left = rt;
		rt->right = rl;
	}

	/***************************************************
	 * *********************************************** *
	 * *                                             * *
	 * *                   Friends                   * *
	 * *                                             * *
	 * *********************************************** *
	 ***************************************************/

	template <typename Type>
	std::ostream &operator<<( std::ostream &out, const Splay_tree<Type> &tree ) {
		out << "Size:     " << tree.tree_size << std::endl;

		if ( !tree.empty() ) {
			std::stack<typename Splay_tree<Type>::Node *> traversal;
			std::stack<int> indentation;

			traversal.push( tree.root );
			indentation.push( 0 );

			while ( !traversal.empty() ) {
				typename Splay_tree<Type>::Node *node = traversal.top();
				int indent = indentation.top();

				traversal.pop();
				indentation.pop();

				out.width( indent );
				out.fill( ' ' );
				out << "";

				if ( node == 0 ) {
					out << "-" << std::endl;
				} else {
					out << node->element << std::endl;

					if ( node->left != 0 || node->right != 0 ) {
						traversal.push( node->right );
						indentation.push( indent + 1 );

						traversal.push( node->left );
						indentation.push( indent + 1 );
					}
				}
			}
		}

		return out;
	}
}

#endif