#include "stdafx.h"
#include<cassert>
#pragma once
using namespace std;

template <class T>
class Vector{
protected:
	T *tab;
	int _size;
public:
	Vector(int size = 10);
	Vector(Vector&);
	~Vector(){delete[] tab;}
	int size(){return _size;}
	T &operator[](int);
	Vector &operator=(Vector&);
	bool operator==(Vector&);
	T *operator&() {return tab;}
	void printVector();
};

template<class T>
Vector<T>::Vector(int t){
	assert(t>0);
	_size = t;
	tab = new T[t];
}
template<class T>
Vector<T>::Vector(Vector& t){
	_size = t.size();
	tab = new T[t.size()];
	for(int register i=0; i<_size; i++)
		*(tab+i)=*(t.tab+i);
}
template <class T>
T& Vector<T>::operator[](int i){
	if (i < _size)
		return *(tab+i);
	else {
		T* tabaux;
		tabaux = new T[i + 10];
		for(int register j=0; j<_size; j++)
			*(tabaux+j)=*(tab+j);
		delete[] tab;
		_size = i + 10;
		tab = tabaux;
		return *(tab+i);
	}
}
template <class T>
Vector<T>& Vector<T>::operator=(Vector<T>& t){

	if(t.tab == tab) return *this;
	if(this->_size != t.size()){
		delete[] tab;
		_size = t.size();
		tab = new T[_size];
		
		for(int register i=0; i<_size; i++)
			*(tab+i)=*(t.tab+i);
		
		return *this;
	}
	for(int register i=0; i<_size; i++)
		*(tab+i)=*(t.tab+i);
	return *this;
}

template <class T>
bool Vector<T>::operator==(Vector<T>& t){
	
	for (int register i = 0; i<10; i++){
		if (!(*(tab+i) ==  *(t.tab+i)))
			return false;
	}
	return true;
}

template <class T>
void Vector<T>::printVector(){
	for (int register i = 0 ; i < _size ; i++){
		cout << "vector["<<i<<"]="<<tab[i]<<"\n";
	}
}

template <class T>
class Heap{
protected:
	int _firstIndex;
	int _lastIndex;
	int _size;
	Vector<T>tab;
public:
	Heap(int firstIndex,int lastIndex);
	void heapify(int i);
	int parent(int i);
	int left(int i);
	int right(int i);
	T heapExtractMax();
	T getEvent(int i);
	void heapInsert(T key);
	void setSize(int value);
	Vector<T> getVector();
	int size(){return _size;}
};

template <class T>
Heap<T>::Heap(int firstIndex, int lastIndex){
	_firstIndex = firstIndex;
	_lastIndex = lastIndex;
	_size = 0;
	Vector<T> array(lastIndex-firstIndex);
	tab = array;
}

template <class T>
void Heap<T>::heapify(int i){
	int l = left(i);
	int r = right(i);
	int largest = 0;
	if (l <= _size && tab[l] > tab[i])
		largest = l;
	else
		largest = i;
	if (r <= _size && tab[r] > tab[largest])
		largest = r;
	if (largest != i) {
		T aux = tab[largest];
		tab[largest] = tab[i];
		tab[i] = aux;
		heapify(largest);
	}
}

template <class T>
int Heap<T>::parent(int i){
	return i/2;
}

template <class T>
int Heap<T>::left(int i){
	return 2*i;
}

template <class T>
int Heap<T>::right(int i){
	return (2*i)+1;
}

template <class T>
T Heap<T>::heapExtractMax(){
	assert(_size >= 1);
	T max = tab[1];
	tab[1] = tab[_size];
	_size = _size-1;
	heapify(1);
	return max;
}

template <class T>
void Heap<T>::heapInsert(T key){
	_size = _size + 1;
	int i = _size;
	while(i>1 && tab[parent(i)] < key) {
		tab[i] = tab[parent(i)];
		i = parent(i);
	}
	tab[i] = key;
}
template <class T>
Vector<T> Heap<T>::getVector()
{
	return tab;
}

template <class T>
T Heap<T>::getEvent(int i){
	return tab[i];
}

template <class T>
void Heap<T>::setSize(int value){
	_size = value;
	Vector<T> array(_lastIndex-_firstIndex);
	tab = array;
}