#pragma once

template <class TYPE_>
class priorityQueue{

private:
	int capacity;
	int index;
	int numItems;
	TYPE_ * arr;

	void sortTheArr(){
		
		for(int x = 0 ; x< capacity; x++){
			int smallest = arr[x];
			int index = x ;
			for(int y = x; y < capacity; y++){
				if(arr[y] < smallest){
					smallest = arr[y];
					index = y;
				}
				TYPE_ temp = arr[index];
				arr[index] = smallest;

			}
		}
	}

	void resize(int newCap){
		TYPE_ * arr2 = new TYPE_[newCap];

		for(int x  = 0; x < capacity; x++){
			arr2[x] = arr[x];
		}
		delete[] arr;
		arr =  arr2;
		capacity = newCap;
	}

public:
	
	priorityQueue(){
		capacity = 10;
		index = 0;
		numItems = 0;
		arr = new TYPE_[capacity];
	}

	void insert(TYPE_ item){
		numItems++;
		if(numItems == capacity){
			resize(capacity * 2);
		}
		else{
			//cout<< "inserting "<< item << " into "<< index<<endl;
			arr[index] = item;
			index++;
		}
	}

	TYPE_ extractMin(){
		if(! empty()){
			int smallest = arr[0];
			int ind = 0;
				for(int x = 0; x < index; x++){
					if(arr[x] < smallest){
						smallest = arr[x];
						ind = x;
					}
				}
				//if(ind != index-1)
					arr[ind] = arr[index - 1];
				index--;
				numItems --;
			return smallest;
		}
		return -1;
	}

	bool empty(){
		if(numItems <= 0 )
			return true;
		else
			return false;
	}

};






=============================================================================================================================

#pragma once
#include <iostream>
#include "priorityQueue.h"
using namespace std;

template <class THING>
void priorityQueueSort(THING * items, int start, int end)
{
	//declare a variable of type priority queue
	priorityQueue<double> p1;

	//insert the items from the 'items' array into the priority queue, one by one
	for(int x = start; x < end+1; x++){
		p1.insert(items[x]);
		cout << "adding "<< items[x]<< " into "<< x<<endl;
	}

	//extract the items from the priorityQueue one by one and write each value
	// into the 'items' array in the order they come out.
	int count = 0;
	while(!p1.empty()){
		int x = p1.extractMin();
		//cout << "count at: "<< count << "  is: "<< x<<endl;
		items[count] = x;
		count++;
	}
}

int main()
{
	///////////////////////////////////////////////////
	//Step 1:  Implement an array based priority queue.
	////////////////////////////////////////////////////

	//A priority queue is an abract data type that supports
	//two operations:  1) insert an item, 'insert(x)', and
	//2) remove and return the smallest item, 'extractMin()'.
	//Implement a priority queue using an array based implementation.
	//Be prepared to answer:  
	//What is the run time of your insert method?  
	//What is the run time of your extractMin method?
	//What is the run time of your priorityQueueSort function?

	priorityQueue<double> pq;

	pq.insert(57);
	pq.insert(32);
	pq.insert(105);
	pq.insert(17);
	
	cout << pq.extractMin() << endl; //17
	cout << pq.extractMin() << endl; //32
	cout << endl;
	
	pq.insert(68);
	pq.insert(5);
	pq.insert(43);

	cout << pq.extractMin() << endl; //5
	cout << pq.extractMin() << endl; //43
	cout << pq.extractMin() << endl; //57
	cout << endl;
	
	pq.insert(120);
	pq.insert(500);
	pq.insert(3);
	pq.insert(73);
	pq.insert(29);

	
	//3 29 68 73 105 120 500
	while (!pq.empty())
	{
		cout << pq.extractMin() << endl;
	}
	cout << endl;
	
	///////////////////////////////////////////////////////////////////
	//Step 2: now, write a sorting routine that uses a priority queue to sort
	///////////////////////////////////////////////////////////////////

	//fill a big array with random numbers
	int size = 10;
	int * numbers = new int[size];
	for (int i = 0; i < size; i++)
	{
		//numbers[i] = rand();
		numbers[i] = i *i;
		cout << "original " << numbers[i] << endl;
	}

	//sort the array using a priority queue to help you
	priorityQueueSort(numbers, 0, size - 1);

	//now array should be in sorted order
	for (int i = 0; i < size; i++)
	{
		cout << "sorted ";		
		cout << numbers[i] << endl;
	}
	

	return 0;
}