/**
 * Copyright © 2016-2019 Xavier G. <xavier@kindwolf.org>
 * This work is free. You can redistribute it and/or modify it under the
 * terms of the Do What The Fuck You Want To Public License, Version 2,
 * as published by Sam Hocevar. See the COPYING file for more details.
 */

void array_sort(unsigned int **array, unsigned int count);
#define ARRAY_SORT 1
#include "common.c"

#define heap_parent_index(x) (((x) - 1) / 2)
#define heap_lchild_index(x) ((2 * (x)) + 1)
#define heap_rchild_index(x) ((2 * (x)) + 2)

void sift_down(unsigned int *heap, unsigned int start, unsigned int end) {
	unsigned int root;      /* Root of the heap being inspected. */
	unsigned int child;     /* Child of the heap being inspected. */
	unsigned int swap;      /* Node to be swapped with the root. */
	unsigned int swap_node; /* Used for the actual swap operation. */
	VERBOSE(3, "  sift_down(heap, %u, %u)\n", start, end);

	/* We want to sift down the provided heap, so we start at its root and
	explore down, looking for anomalies, i.e. for children larger than their
	parent node. */
	root = start;

	/* While the root being inspected has at least one child: */
	while ((child = heap_lchild_index(root)) <= end) {
		/* By default, we consider everything is fine, nothing needs to be
		swapped: */
		swap = root;
		/* Check the left child: */
		if (heap[child] > heap[root]) {
			/* The left child is larger than the root, it is candidate to be
			swapped with the root: */
			swap = child;
		}
		/* Check the right child (if any) against either its sibling
		or the root: */
		if (child + 1 <= end && heap[child + 1] > heap[swap]) {
			swap = child + 1;
		}
		/* Proceed with the swapping, if necessary: */
		if (swap == root) {
			return;
		}
		else {
			swap_node = heap[swap];
			heap[swap] = heap[root];
			heap[root] = swap_node;
			/* Consider the node we swapped as the new root and keep looping: */
			root = swap;
		}
	}
}

/*
 * Implementation of heap sort:
 */
void array_sort(unsigned int **array, unsigned int count) {
	unsigned int *src;          /* Unsorted, source array. */
	unsigned int swap;          /* Used to swap values. */
	int heap_end;               /* End of our heap. */
	int i;                      /* Used to iterate over the array. */

	/* Do nothing unless there are at least two items to sort: */
	if (count < 2) return;

	/* Heap sort is an in-place algorithm, i.e. we work directly on the
	provided array: */
	src = *array;
	heap_end = count - 1;

	/* The first step consists in turning the array into a max heap (i.e. into
	a binary tree with the maximum value at the top). */
	for (i = heap_parent_index(heap_end); i >= 0; --i) {
		sift_down(src, i, heap_end);
	}

	while (heap_end > 0) {
		/* The second step consists in swapping the root of our max heap (i.e.
		the largest value in the whole array) with the last item: */
		swap = src[heap_end];
		src[heap_end] = src[0];
		src[0] = swap;

		/* The third step consists in fixing our now-smaller but disturbed max
		heap by calling sift_down() again: */
		sift_down(src, 0, -- heap_end);

		/* Next, we loop until our heap has but a single value. */
	}
}