#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_LEFTIST_HEAP
#define CA_UWATERLOO_ALUMNI_DWHARDER_LEFTIST_HEAP

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

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

namespace Data_structures {
	template <typename Type>
	class Leftist_heap {
		public:
			Leftist_heap();
			~Leftist_heap();

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

			void push( Type const & );
			void push( Leftist_heap &  );
			Type pop();
			Type top();

			void clear();

		private:
			class Node {
				public:
					Type element;
					Node *left;
					Node *right;
					int min_null_path_length;

					Node( Type const & );
					int min_npl() const;
					void merge( Node *, Node * & );
					void clear();
			};

			int heap_size;
			Node *root;

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

	template <typename Type>
	int Leftist_heap<Type>::Node::min_npl() const {
		return ( this == 0 ) ? -1 : min_null_path_length;
	}

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

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

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

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

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

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

	template <typename Type>
	int Leftist_heap<Type>::size() const {
		return heap_size;
	}

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

	/************************************************************************
	 * Type top()
	 *
	 *  Returns the least object in the leftist heap and
	 *  leftist that node to the root.
	 ************************************************************************/

	template <typename Type>
	Type Leftist_heap<Type>::top() {
		if ( empty() ) {
			return Type();
		}

		return root->element;
	}

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

	template <typename Type>
	void Leftist_heap<Type>::push( Type const &e ) {
		if ( empty() ) {
			root = new Node( e );
			heap_size = 1;
			return;
		}

		root->merge( new Node( e ), root );
		++heap_size;
	}

	template <typename Type>
	void Leftist_heap<Type>::push( Leftist_heap &heap ) {
		if ( empty() ) {
			root      = heap.root;
			heap_size = heap.heap_size;
			heap.root      = 0;
			heap.heap_size = 0;

			return;
		}

		heap_size += heap.heap_size;
		root->merge( heap.root, root );

		heap.root      = 0;
		heap.heap_size = 0;
	}

	template <typename Type>
	Type Leftist_heap<Type>::pop() {
		if ( empty() ) {
			return Type();
		}

		Type tmp = root->element;

		if ( size() == 1 ) {
			heap_size = 0;
			delete root;
			root = 0;
			return tmp;
		}

		Node *old = root;

		if ( root->left == 0 || root->right == 0 ) {
			root = (root->left != 0) ? root->left : root->right;
		} else {
			Node *other = 0;

			if ( root->left->element <= root->right->element ) {
				other = root->right;
				root = root->left;
			} else {
				other = root->left;
				root = root->right;
			}

			root->merge( other, root );
		}

		delete old;
		--heap_size;

		return tmp;
	}

	template <typename Type>
	void Leftist_heap<Type>::Node::merge( Node *ptr, Node * &ptr_to_this ) {
		if ( ptr == 0 ) {
			return;
		}

		if ( this == 0 ) {
			ptr_to_this = ptr;
		}

		// If the this contains a larger element, we will swap the
		// two heaps and instead merge this heap with the argument.

		if ( element > ptr->element ) {
			ptr_to_this = ptr;
			ptr->merge( this, ptr_to_this );
			return;
		}

		if ( right == 0 ) {
			right = ptr;
		} else {
			right->merge( ptr, right );
		}

		min_null_path_length = std::min( 1 + left->min_npl(), 1 + right->min_npl() );

		if ( left->min_npl() < right->min_npl() ) {
			Node *tmp = left;
			left = right;
			right = tmp;
		}
	}

	/************************************************************************
	 * void clear()
	 *
	 *  Empty the leftist heap
	 ************************************************************************/

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

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

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

		delete this;
	}

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

	template <typename Type>
	std::ostream &operator<<( std::ostream &out, const Leftist_heap<Type> &heap ) {
		out << "Size:     " << heap.heap_size << std::endl;

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

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

			while ( !traversal.empty() ) {
				typename Leftist_heap<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