#include <stdlib.h>
#define INITIAL_CAPACITY 5
#define swap(type, a, b) \
			type p;\
			p = a;\
			a = b;\
			b = p;
typedef struct _CC_VECTOR {
	// Members
	int* Array;
	int Size;
	int Capacity;
} CC_VECTOR;

typedef struct _CC_HEAP {
	// Members
	int Size;
	int Capacity;
	int* HeapElements;
} CC_HEAP;

int HpCreateMaxHeap(CC_HEAP **MaxHeap, CC_VECTOR* InitialElements)
{
	if (MaxHeap == NULL || InitialElements == NULL)
		return -1;

	*MaxHeap = (CC_HEAP*)malloc(sizeof(CC_HEAP));

	if (*MaxHeap == NULL)
		return -1;

	(*MaxHeap)->Size = 0;
	(*MaxHeap)->Capacity = INITIAL_CAPACITY;
	(*MaxHeap)->HeapElements = (int *)malloc((*MaxHeap)->Capacity * sizeof(int));

	if ((*MaxHeap)->HeapElements == NULL)
	{
		free(*MaxHeap);
		*MaxHeap = NULL;
		return -1;
	}

	for (int i = 0; i < InitialElements->Size; i++)
	{
		///how to invoke the function with parameter MaxHeap/MinHeap??? (&,*)
		HpInsert(*MaxHeap, InitialElements->Array[i]);
		int j = (*MaxHeap)->Size - 1;
		// Fix the max heap property if it is violated 
		while (j != 0 && (*MaxHeap)->HeapElements[(j - 1) / 2] < (*MaxHeap)->HeapElements[j])
		{
			swap(int, (*MaxHeap)->HeapElements[j], (*MaxHeap)->HeapElements[(j - 1) / 2]);
			j = (j - 1) / 2;
		}
	}

	return 0;
}

int HpCreateMinHeap(CC_HEAP **MinHeap, CC_VECTOR* InitialElements)
{
	printf("%p\n", InitialElements); ///InitialElements is NULL in  main!!!
	if (MinHeap == NULL || InitialElements == NULL)
		return -1;

	*MinHeap = (CC_HEAP*)malloc(sizeof(CC_HEAP));

	if (*MinHeap == NULL)
		return -1;

	(*MinHeap)->Size = 0;
	(*MinHeap)->Capacity = INITIAL_CAPACITY;
	(*MinHeap)->HeapElements = (int *)malloc((*MinHeap)->Capacity * sizeof(int));

	if ((*MinHeap)->HeapElements == NULL)
	{
		free(*MinHeap);
		*MinHeap = NULL;
		return -1;
	}

	for (int i = 0; i < InitialElements->Size; i++)
	{
		HpInsert(*MinHeap, InitialElements->Array[i]);
		int j = (*MinHeap)->Size - 1;
		// Fix the min heap property if it is violated 
		while (j != 0 && (*MinHeap)->HeapElements[(j - 1) / 2] > (*MinHeap)->HeapElements[j])
		{
			swap(int, (*MinHeap)->HeapElements[j], (*MinHeap)->HeapElements[(j - 1) / 2]);
			j = (j - 1) / 2;
		}
	}

	return 0;
}

int HpDestroy(CC_HEAP **Heap)
{
	if (Heap == NULL || (*Heap) == NULL)
	{
		return -1;
	}

	(*Heap)->Capacity = 0;
	(*Heap)->Size = 0;

	if ((*Heap)->HeapElements != NULL)
	{
		free((*Heap)->HeapElements);
	}

	return 0;
}
///separate for MinHeap and MaxHeap...
int HpInsert(CC_HEAP *Heap, int Value)
{
	if (Heap == NULL)
		return -1;

	if (Heap->Size == Heap->Capacity)
	{

		Heap->HeapElements = (int *)realloc(Heap->HeapElements, Heap->Capacity * 2);

		if (Heap->HeapElements == NULL)
		{
			return -1;
		}

		Heap->Capacity *= 2;
	}

	// First insert Value at the end 
	Heap->Size++;
	Heap->HeapElements[Heap->Size - 1] = Value;

	return 0;
}

int HpRemove(CC_HEAP *Heap, int Value)
{
	if (Heap == NULL)
	{
		return -1;
	}

	int i;
	for (i = 0; i < Heap->Size; i++)
	{
		if (Heap->HeapElements[i] == Value)
		{
			break;
		}
	}

	if (i == Heap->Size)
	{
		return -1; //as not found
	}

	Heap->HeapElements[i] = Heap->HeapElements[Heap->Size - 1];
	heapify(Heap);
	///heapify separate for MinHeap and MaxHeap...
	return 0;
}

int HpGetExtreme(CC_HEAP *Heap, int* ExtremeValue)
{
	if (Heap == NULL)
	{
		return -1;
	}

	*ExtremeValue = Heap->HeapElements[0];

	return 0;
}

int HpPopExtreme(CC_HEAP *Heap, int* ExtremeValue)
{
	if (Heap == NULL)
	{
		return -1;
	}

	*ExtremeValue = Heap->HeapElements[0];
	///how to deallocate the mamory occupied by the extreme value
	return 0;
}

int HpGetElementCount(CC_HEAP *Heap)
{
	if (Heap == NULL)
	{
		return -1;
	}

	return Heap->Size;
}

int HpSortToVector(CC_HEAP *Heap, CC_VECTOR* SortedVector)
{
	CC_UNREFERENCED_PARAMETER(Heap);
	CC_UNREFERENCED_PARAMETER(SortedVector);
	return -1;
}