#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "util.h"

typedef int T;

// https://stackoverflow.com/a/22900767

#define LEFT(idx) (idx * 2 + 1)
#define RIGHT(idx) (idx * 2 + 2)
#define PARENT(idx) ((idx - 1) / 2)

static void
swap(T heap[], size_t i, size_t j)
{
	T temp  = heap[i];
	heap[i] = heap[j];
	heap[j] = temp;
}

#if defined(MAX_HEAP)
// MAX-HEAP Implementation
static void
fixup(T heap[], size_t i)
{
	size_t p = PARENT(i);

	while ( i > 0 && heap[p] < heap[i] ) {
		swap(heap, i, p);

		i = p;
		p = PARENT(i);
	}
}

static void
fixdown(T heap[], size_t i, size_t n)
{
	for ( ;; ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);
		size_t       m = i;

		if ( l < n && heap[m] < heap[l] ) {
			m = l;
		}

		if ( r < n && heap[m] < heap[r] ) {
			m = r;
		}

		if ( m == i ) {
			break;
		}

		swap(heap, m, i);

		i = m;
	}
}
#else
// MIN-HEAP Implementation
static void
fixup(T heap[], size_t i)
{
	size_t p = PARENT(i);

	while ( i > 0 && heap[i] < heap[p] ) {
		swap(heap, i, p);

		i = p;
		p = PARENT(i);
	}
}

static void
fixdown(T heap[], size_t i, size_t n)
{
	for ( ;; ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);
		size_t       m = i;

		if ( l < n && heap[l] < heap[m] ) {
			m = l;
		}

		if ( r < n && heap[r] < heap[m] ) {
			m = r;
		}

		if ( m == i ) {
			break;
		}

		swap(heap, m, i);

		i = m;
	}
}
#endif

static void
heapify(T heap[], size_t n)
{
	for ( size_t i = n / 2; i-- > 0; ) {
		fixdown(heap, i, n);
	}
}

static void
my_heapsort(T a[], size_t n)
{
	heapify(a, n);

	while ( n-- ) {
		swap(a, 0, n);
		fixdown(a, 0, n);
	}
}

// -------------------------------------------

struct pq { // Priority Queue
	T      heap[251];
	size_t sz;
};

void
pq_init(struct pq *pq)
{
	pq->sz = 0;
}

bool
pq_push(struct pq *pq, T data)
{
	if ( pq->sz == NELEM(pq->heap) ) {
		return false;
	}

	pq->heap[pq->sz] = data;
	fixup(pq->heap, pq->sz);
	++pq->sz;
	return true;
}

bool
pq_pop(struct pq *pq, T *data)
{
	if ( pq->sz == 0 ) {
		return false;
	}

	*data = pq->heap[0];
	--pq->sz;
	pq->heap[0] = pq->heap[pq->sz];
	fixdown(pq->heap, 0, pq->sz);
	return true;
}

// -------------------------------------------

void
print_heap(T heap[], size_t n)
{
	if ( n ) {
		printf("%d", heap[0]);
		for ( size_t i = 1; i != n; ++i ) {
			printf(", %d", heap[i]);
		}
		putchar('\n');
	}
}

void
test_heapsort(void)
{
	static const size_t N = 1000000;
	T                   array[N];

	puts("fülle....");
	srand(time(NULL));
	for ( size_t idx = 0; idx != NELEM(array); ++idx ) {
		array[idx] = rand();
	}

	puts("sortiere....");
	my_heapsort(array, NELEM(array));

	puts("teste...");
	for ( size_t idx = 1; idx != NELEM(array); ++idx ) {
#if defined(MAX_HEAP)
		if ( array[idx - 1] > array[idx] ) {
			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
			exit(EXIT_FAILURE);
		}
#else
		if ( array[idx - 1] < array[idx] ) {
			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
			exit(EXIT_FAILURE);
		}
#endif
	}
	puts("ok");
}

void
test_pq(void)
{
	struct pq pq[1];

	pq_init(pq);

	for ( int i = 0; i != 10; ++i ) {
		pq_push(pq, rand());
	}

	T data;
	while ( pq_pop(pq, &data) ) {
		printf("%d\n", data);
	}
}

int
main(void)
{
	test_heapsort();
	test_pq();
#if 0 // Heap-Testprogramm
	T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 };

	print_heap(heap, 10);

	//heap[10] = 13; fixup(heap, 10);
	swap(heap, 0, 9); fixdown(heap, 0, 9);

	print_heap(heap, 9);
#endif
}