/*****************************************
 * Instructions
 *  - Replace 'uwuserid' with your uWaterloo User ID
 *  - Select the current calendar term and enter the year
 *  - List students with whom you had discussions and who helped you
 *
 * uWaterloo User ID:  uwuserid @uwaterloo.ca
 * Submitted for ECE 250
 * Department of Electrical and Computer Engineering
 * University of Waterloo
 * Calender Term of Submission:  (Winter|Spring|Fall) 201N
 *
 * By submitting this file, I affirm that
 * I am the author of all modifications to
 * the provided code.
 *
 * The following is a list of uWaterloo User IDs of those students
 * I had discussions with in preparing this project:
 *    -
 *
 * The following is a list of uWaterloo User IDs of those students
 * who helped me with this project (describe their help; e.g., debugging):
 *    -
 *****************************************/

#ifndef STABLE_BINARY_HEAP_H
#define STABLE_BINARY_HEAP_H

#ifndef nullptr
#define nullptr 0
#endif

#include "ece250.h"
#include "Exception.h"
#include <cassert>

template <typename Type>
class Stable_binary_heap {
	private:
		int heap_capacity;
		Type *array;
		int *key_array;
		int heap_size;
		int key_count;

	public:
		Stable_binary_heap( int = 10 );
		Stable_binary_heap( Stable_binary_heap const & );
		~Stable_binary_heap();

		Stable_binary_heap &operator=( Stable_binary_heap const & );

		// Accessors

		int size() const;
		int capacity() const;
		bool empty() const;
		bool full() const;
		Type top() const;
		Type retrieve( int ) const;
		int key( int ) const;
		int count( Type const & ) const;

		// Mutators

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

	// Friends

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

template <typename Type>
Stable_binary_heap<Type>::Stable_binary_heap( int n ):
heap_capacity( n + 1 ),
array( new Type[heap_capacity] ),
key_array( new int[heap_capacity] ),
heap_size( 0 ),
key_count( 0 ) {
	// empty constructor
}

template <typename Type>
Stable_binary_heap<Type>::Stable_binary_heap( Stable_binary_heap<Type> const &heap ):
heap_capacity( 0 ),
array( 0 ),
key_array( 0 ),
heap_size( 0 ),
key_count( 0 ) {
	*this = heap;
}

template <typename Type>
Stable_binary_heap<Type>::~Stable_binary_heap() {
	// Your implementation here...
}

template <typename Type>
Stable_binary_heap<Type> &Stable_binary_heap<Type>::operator=( Stable_binary_heap<Type> const &rhs ) {
	if ( this == &rhs ) {
		return *this;
	}

	// Your implementation here...

	return *this;
}

template <typename Type>
int Stable_binary_heap<Type>::size() const {
	// Your implementation here...
	return 0;
}

template <typename Type>
int Stable_binary_heap<Type>::capacity() const {
	// Your implementation here...
	return 0;
}

template <typename Type>
bool Stable_binary_heap<Type>::empty() const {
	// Your implementation here...
	return true;
}

template <typename Type>
bool Stable_binary_heap<Type>::full() const {
	// Your implementation here...
	return false;
}

template <typename Type>
Type Stable_binary_heap<Type>::top() const {
	// Your implementation here...
	return Type();
}

template <typename Type>
Type Stable_binary_heap<Type>::retrieve( int n ) const {
	return array[n];
}

template <typename Type>
int Stable_binary_heap<Type>::key( int n ) const {
	return key_array[n];
}

template <typename Type>
int Stable_binary_heap<Type>::count( Type const &obj ) const {
	// Your implementation here...
	return 0;
}

template <typename Type>
void Stable_binary_heap<Type>::push( Type const &obj ) {
	// Your implementation here...
}

template <typename Type>
Type Stable_binary_heap<Type>::pop() {
	// Your implementation here...
	return Type();
}

template <typename Type>
void Stable_binary_heap<Type>::clear() {
	// Your implementation here...
}

// You can modify this function however you want:  it will not be tested

template <typename T>
std::ostream &operator<<( std::ostream &out, Stable_binary_heap<T> const &heap ) {
	for ( int i = 1; i <= heap.size(); ++i ) {
		out << heap.retrieve( i ) << "\t";
	}

	out << std::endl;

	for ( int i = 1; i <= heap.size(); ++i ) {
		out << heap.key( i ) << "\t";
	}


	return out;
}

// Is an error showing up in ece250.h or elsewhere?
// Did you forget a closing '}' ?

#endif