#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BINOMIAL_HEAP
#define CA_UWATERLOO_ALUMNI_DWHARDER_BINOMIAL_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 Binomial_heap {
		public:
			Binomial_heap();
			~Binomial_heap();

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

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

			void clear();

		private:
			class Node {
				public:
					Type element;
					Node *head;
					Node *tail;
					Node *next;
					int order;

					Node( Type const & );
					void clear();
			};

			Node *trees;
			int heap_size;
			void merge( Node *&, int );
			static void pop_check_and_push( Node *&, Node *& );
			static void pop_merge_and_push( Node *&, Node *&, Node *& );
			static Node *merge_trees( Node *, Node * );

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

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

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

	template <typename Type>
	Binomial_heap<Type>::~Binomial_heap() {
		for ( Node *ptr = trees; ptr != 0; ptr = ptr->next ) {
			ptr->clear();
		}
	}

	template <typename Type>
	Binomial_heap<Type>::Node::Node( Type const &e ):element( e ), head( 0 ), tail( 0 ), next( 0 ), order( 0 ) {
		// does nothing
	}

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

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

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

	/************************************************************************
	 * Type top()
	 *
	 *  Returns the least object in the binomial heap by
	 *  finding the minimum value of the children.
	 ************************************************************************/

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

		Type min = trees->element;

		for ( Node *ptr = trees->next; ptr != 0; ptr = ptr->next ) {
			if ( ptr->element < min ) {
				min = ptr->element;
			}
		} 

		return min;
	}

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

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

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

		Node *tmp_trees = new Node( e );

		// Merge the current binomial heap with the temporary binomial heap
		merge( tmp_trees, 1 );

		assert( tmp_trees == 0 );
	}

	/************************************************************************
	 * void push( Binomial_heap<Type> &heap )
	 *
	 *  Push the elements of the binomial heap 'heap' onto this heap
	 *  and empty 'heap'.
	 ************************************************************************/

	template <typename Type>
	void Binomial_heap<Type>::push( Binomial_heap<Type> &heap ) {
		if ( heap.empty() ) {
			return;
		}

		if ( empty() ) {
			trees = heap.trees;
			heap_size = heap.heap_size;

			heap.trees = 0;
			heap.heap_size = 0;

			return;
		}

		// Merge the current binomial heap with the binomial heap 'heap'
		merge( heap.trees, heap.heap_size );
		assert( heap.trees == 0 );
		heap.heap_size = 0;
	}

	/*
	 *     X  ->  X  -> min ->  X  ->  0
	 *            |      |\     |\ \
	 *            X      Y Y    X X X
	 *                     |      | |\
	 *                     Y      X X X
	 *                                | 
	 *                                X
	 *
	 *     X  ->  X  ->  X  ->  0        Y  ->  Y
	 *            |      |\ \                   |
	 *            X      X X X                  Y
	 *                     | |\
	 *                     X X X
	 *                         | 
	 *                         X
	 *
	 *  And the second tree is merged into the first.
	 */

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

		// Find the minimum element to extract
		// 'update' is the node immediately prior to the node
		// to be popped.

		Node *update = 0;
		Type min = trees->element;

		for ( Node *prev = trees, *curr = trees->next; curr != 0; prev = curr, curr = curr->next ) {
			if ( curr->element < min ) {
				update = prev;
				min = curr->element;
			}
		}

		Node *tmp_trees = ( update == 0 ) ? trees->head : update->next->head;

		// Remove the node from the tree
		// Set 'tmp_trees' to form the sequence of trees

		int tmp_size = 1 << (( update == 0 ) ? trees->order : update->next->order);
		Node *old_node = ( update == 0 ) ? trees : update->next;

		if ( update == 0 ) {
			trees = trees->next;
		} else {
			update->next = update->next->next;
		}

		delete old_node;

		heap_size -= tmp_size;

		// Merge the current binomial heap with the one node removed and
		// that node converted into a temporary binomial heap

		merge( tmp_trees, tmp_size - 1 );
		assert( tmp_trees == 0 );

		return min;
	}

	/************************************************************************
	 *  Merge this binomial heap with the node on the left.
	 ************************************************************************/

	template <typename Type>
	void Binomial_heap<Type>::merge( Node *&additions, int delta_size ) {
		if ( additions == 0 ) {
			return;
		}

		if ( trees == 0 ) {
			trees = additions;
			additions = 0;
			heap_size += delta_size;
			return;
		}

		Node *stack = 0;

		// Walk through the two forests from lowest order
		// to highest order.
		//
		// If we are moving only one tree to the stack (the other has a
		// higher order), we first check to make sure we don't have to
		// merge it with what is on top of the stack.
		//
		// Comment: as stack is always the last argument, it may be
		// a good idea to abstract it out and create a class...

		while ( additions != 0 && trees != 0 ) {
			if ( additions->order < trees->order ) {
				pop_check_and_push( additions, stack );
			} else if ( additions->order > trees->order ) {
				pop_check_and_push( trees, stack );
			} else {
				pop_merge_and_push( additions, trees, stack );
			}
		}

		while ( additions != 0 ) {
			pop_check_and_push( additions, stack );
		}

		while ( trees != 0 ) {
			pop_check_and_push( trees, stack );
		}

		// Copy everything from the stack back
		// to trees in the reverse order.

		trees = stack;
		stack = stack->next;
		trees->next = 0;

		while ( stack != 0 ) {
			Node *tmp = stack;
			stack = stack->next;
			tmp->next = trees;
			trees = tmp;
		}

		heap_size += delta_size;
	}

	/************************************************************************
	 *     A     B          A
	 *     |\    |\         |\ \
	 *     X X   X X   ->   X X  B
	 *       |     |          |  |\
	 *       X     X          X  X X
	 *                             |
	 *                             X
	 ************************************************************************/

	template <typename Type>
	typename Binomial_heap<Type>::Node *Binomial_heap<Type>::merge_trees( Node *left, Node *right ) {
		if ( left->element <= right->element ) {
			if ( left->head == 0 ) {
				left->head = right;
				left->tail = right;
			} else {
				left->tail->next = right;
				left->tail = right;
			}

			++(left->order);

			return left;
		} else {
			if ( right->head == 0 ) {
				right->head = left;
				right->tail = left;
			} else {
				right->tail->next = left;
				right->tail = left;
			}

			++(right->order);

			return right;
		}
	}

	template <typename Type>
	void Binomial_heap<Type>::pop_check_and_push( Node *&from, Node *&to ) {
		if ( to != 0 && (from->order == to->order) ) {
			Node *tmp = merge_trees( from, to );
			to = to->next;
			from = from->next;
			tmp->next = to;
			tmp->tail->next = 0;
			to = tmp;
		} else {
			Node *tmp = from;
			from = from->next;
			tmp->next = to;
			to = tmp;
		}
	}

	template <typename Type>
	void Binomial_heap<Type>::pop_merge_and_push( Node *&from_1, Node *&from_2, Node *&to ) {
		Node *tmp = merge_trees( from_1, from_2 );
		from_1 = from_1->next;
		from_2 = from_2->next;
		tmp->next = to;
		tmp->tail->next = 0;
		to = tmp;
	}

	/************************************************************************
	 * void clear()
	 *
	 *  Empty the binomial heap by calling clear on each of the
	 *  trees in the heap.  These delete themselves recursively.
	 ************************************************************************/

	template <typename Type>
	void Binomial_heap<Type>::clear() {
		for ( Node *ptr = trees; ptr != 0; ptr = ptr->next ) {
			ptr->clear();
		}

		heap_size = 0;
		trees = 0;
	}

	template <typename Type>
	void Binomial_heap<Type>::Node::clear() {
		for ( Node *ptr = head; ptr != 0; ptr = ptr->next ) {
			ptr->clear();
		}

		delete this;
	}

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

	template <typename Type>
	std::ostream &operator<<( std::ostream &out, const Binomial_heap<Type> &heap ) {
		out << "Size:     " << heap.size() << std::endl;
		out << "Top:      " << heap.top() << std::endl;

		for ( typename Binomial_heap<Type>::Node *ptr = heap.trees; ptr != 0; ptr = ptr->next ) {
			std::stack<typename Binomial_heap<Type>::Node *> traversal;
			std::stack<int> indentation;

			traversal.push( ptr );
			indentation.push( 0 );

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

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

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

				out << node->element << " (" << node->order << ')' << std::endl;

				for ( typename Binomial_heap<Type>::Node *ptr = node->head; ptr != 0; ptr = ptr->next ) {
					traversal.push( ptr );
					indentation.push( indent + 1 );
				}
			}
		}

		return out;
	}
}

#endif