#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_QUATERNARY_HEAP
#define CA_UWATERLOO_ALUMNI_DWHARDER_QUATERNARY_HEAP

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

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

namespace Data_structures {
	template <typename T>
	class Ternary_heap {
		public:
			Ternary_heap( int );
			~Ternary_heap();
			Ternary_heap( Ternary_heap const & );
			Ternary_heap &operator=( Ternary_heap const & );

			bool empty() const;
			int size() const;
			int capacity() const;
			int count( T const & ) const;
			T top() const;

			void push( T const & );
			void pop();
			void clear();

		private:
			int heap_capacity;
			int initial_capacity;
			T *array;
			int heap_size;

			void double_capacity();
			void halve_capacity();

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

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

	template <typename T>
	Ternary_heap<T>::Ternary_heap( int n ):heap_capacity( std::max( 1, n ) ), initial_capacity( heap_capacity ), array( new T[heap_capacity] ), heap_size( 0 ) {
		// empty constructor
	}

	template <typename T>
	Ternary_heap<T>::~Ternary_heap() {
		delete [] array;
	}

	template <typename T>
	Ternary_heap<T>::Ternary_heap( Ternary_heap const &heap ):
		heap_capacity( heap.heap_capacity ),
		initial_capacity( heap.initial_capacity ),
		array( new T[heap_capacity] ),
		heap_size( heap.heap_size )
	{
		for ( int i = 0; i < heap_size; ++i ) {
			array[i] = heap.array[i];
		}
	}

	template <typename T>
	Ternary_heap<T> &Ternary_heap<T>::operator=( Ternary_heap const &heap ) {
		if ( this == &heap ) {
			return *this;
		}

		if ( heap_capacity != heap.heap_capacity ) {
			delete [] array;
			heap_capacity = heap.heap_capacity;
			array = new T[heap_capacity];
		}

		initial_capacity = heap.initial_capacity;
		heap_size = heap.heap_size;

		for ( int i = 0; i < size(); ++i ) {
			array[i] = heap.array[i];
		}

		return *this;
	}

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

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

	template <typename T>
	int Ternary_heap<T>::size() const {
		return heap_size;
	}

	template <typename T>
	int Ternary_heap<T>::capacity() const {
		return heap_capacity;
	}

	/************************************************************************
	 * int count( T const &obj ) const
	 *
	 *  Count the number of occurrences of the object 'obj' in the binary heap.
	 ************************************************************************/

	template <typename T>
	int Ternary_heap<T>::count( T const &obj ) const {
		int c = 0;

		for ( int i = 0; i < size(); ++i ) {
			if ( array[i] == obj ) {
				++c;
			}
		}

		return c;
	}

	
	template <typename T>
	T Ternary_heap<T>::top() const {
		if ( empty() ) {
			return T();
		}

		return array[0];
	}

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

	template <typename T>
	void Ternary_heap<T>::push( T const &obj ) {
		if ( size() == capacity() ) {
			double_capacity();
		}

		int i = heap_size;
		++heap_size;

		while ( i != 0 && array[(i - 1)/3] > obj ) {
			array[i] = array[(i - 1)/3];
			i = (i - 1)/3;
		}

		array[i] = obj;
	}

	template <typename T>
	void Ternary_heap<T>::pop() {
		if ( empty() ) {
			return;
		}

		--heap_size;
		T last = array[size()];

		int posn = 0;
		int posn30 = 0;
		int posn33 = 3;

		while ( posn33 < size() ) {
			int posn31 = posn30 + 1;
			int posn32 = posn30 + 2;

			T min = last;
			int loc = posn;

			if ( array[posn33] < min ) {
				min = array[posn33];
				loc = posn33;
			}

			if ( array[posn32] < min ) {
				min = array[posn32];
				loc = posn32;
			}

			if ( array[posn31] < min ) {
				min = array[posn31];
				loc = posn31;
			}

			array[posn] = min;

			if ( posn == loc ) {
				goto finish;
			}

			posn = loc;
			posn30 = 3*loc;
			posn33 = posn30 + 3;
		}

		{
			T min = last;
			int loc = posn;

			int posn31 = posn30 + 1;
			int posn32 = posn30 + 2;

			switch ( posn33 - size() ) {
			case 0:
				if ( array[posn32] < min ) {
					min = array[posn32];
					loc = posn32;
				}
			case 1:
				if ( array[posn31] < min ) {
					min = array[posn31];
					loc = posn31;
				}
			}

			array[posn] = min;

			if ( posn != loc ) {
				array[loc] = last;
			}
		}

		finish:

		if ( 4*size() == capacity() && capacity() > initial_capacity ) {
			halve_capacity();
		}
	}

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

	template <typename T>
	void Ternary_heap<T>::clear() {
		heap_size = 0;

		if ( heap_capacity != initial_capacity ) {
			heap_capacity = initial_capacity;
			delete [] array;
			array = new T[heap_capacity];
		}
	}

	template <typename T>
	void Ternary_heap<T>::double_capacity() {
		T *tmp_array = new T[2*capacity()];

		for ( int i = 0; i < size(); ++i ) {
			tmp_array[i] = array[i];
		}

		delete [] array;
		array = tmp_array;

		heap_capacity *= 2;
	}

	template <typename T>
	void Ternary_heap<T>::halve_capacity() {
		T *tmp_array = new T[capacity()/2];

		for ( int i = 0; i < size(); ++i ) {
			tmp_array[i] = array[i];
		}

		delete [] array;
		array = tmp_array;

		heap_capacity /= 2;
	}

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

	template <typename T>
	std::ostream &operator<<( std::ostream &out, const Ternary_heap<T> &heap ) {
		out << "Size:             " << heap.size() << std::endl;
		out << "Capacity:         " << heap.capacity() << std::endl;
		out << "Initial capacity: " << heap.initial_capacity << std::endl;

		for ( int i = 0; i < heap.size(); ++i ) {
			out << heap.array[i] << " ";
		}

		out << std::endl;

		return out;
	}
}

#endif