testbinheap.c

text/x-csrc

Download

#include "c.h"
#include "binaryheap.h"

#include <stdio.h>

void print_heap(binaryheap *h);

int c(binaryheap_node *a, binaryheap_node *b)
{
	/*
	 * The comparator could act on the nodes' keys too, but in this case
	 * it's easier to use the values.
	 */

	int av = *(int *)(a->value);
	int bv = *(int *)(b->value);

	if (av < bv)
		return -1;
	else if (av > bv)
		return 1;

	return 0;
}

int notc(binaryheap_node *a, binaryheap_node *b)
{
	int av = *(int *)(a->value);
	int bv = *(int *)(b->value);

	if (av < bv)
		return 1;
	else if (av > bv)
		return -1;

	return 0;
}

int main()
{
    binaryheap *h;
	binaryheap_node *node;

	int ints[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};

    h = binaryheap_allocate(7, c);
	if (h->space != 7 || h->size != 0 || h->compare != c) {
		printf("ERROR: binaryheap_allocate() is broken\n");
	}

	/*
	 * Does adding a bunch of elements to an empty heap result in a
	 * valid binary heap? If we remove them one by one, are they in
	 * the right order?
	 */

	binaryheap_add(h, "d", (void *)&ints[3]);
	binaryheap_add(h, "b", (void *)&ints[1]);
	binaryheap_add(h, "f", (void *)&ints[5]);
	binaryheap_add(h, "a", (void *)&ints[0]);
	binaryheap_add(h, "c", (void *)&ints[2]);
	binaryheap_add(h, "e", (void *)&ints[4]);
	binaryheap_add(h, "g", (void *)&ints[6]);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

	/*
	 * Does building a heap from unordered elements result in a valid
	 * binary heap? What if we add some more elements later?
	 */

	h = binaryheap_allocate(7, c);
	binaryheap_add_unordered(h, "d", (void *)&ints[3]);
	binaryheap_add_unordered(h, "b", (void *)&ints[1]);
	binaryheap_add_unordered(h, "f", (void *)&ints[5]);
	binaryheap_add_unordered(h, "a", (void *)&ints[0]);
	binaryheap_build(h);
	print_heap(h);
	binaryheap_add(h, "c", (void *)&ints[2]);
	binaryheap_add(h, "e", (void *)&ints[4]);
	binaryheap_add(h, "g", (void *)&ints[6]);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

	/*
	 * Next, we add nodes 1..15 without regard to the heap property,
	 * assemble a valid heap from them, and remove elements from it
	 * one by one.
	 */

	int i = 0;
	h = binaryheap_allocate(15, c);
	while (i < 15) {
		binaryheap_add_unordered(h, "", (void *)&ints[i]);
		i++;
	}
	binaryheap_build(h);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

	/*
	 * Then we repeat the test above with a reversed comparator and the
	 * last few nodes added in after the heap is built, to make sure
	 * min-heaps work as expected.
	 */

	i = 0;
	h = binaryheap_allocate(15, notc);
	while (i < 12) {
		binaryheap_add_unordered(h, "", (void *)&ints[14-i]);
		i++;
	}
	binaryheap_build(h);
	binaryheap_add(h, "", (void *)&ints[2]);
	binaryheap_add(h, "", (void *)&ints[1]);
	binaryheap_add(h, "", (void *)&ints[0]);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

	/*
	 * Now we test that replace_key works on a max heap.
	 */

	h = binaryheap_allocate(7, c);
	binaryheap_add(h, "f", (void *)&ints[8]);
	binaryheap_add(h, "d", (void *)&ints[6]);
	binaryheap_add(h, "b", (void *)&ints[4]);
	binaryheap_add(h, "g", (void *)&ints[9]);
	binaryheap_add(h, "c", (void *)&ints[5]);
	binaryheap_add(h, "a", (void *)&ints[3]);
	binaryheap_add(h, "e", (void *)&ints[7]);
	binaryheap_replace_first(h, "", (void *)&ints[10]);
	binaryheap_replace_first(h, "", (void *)&ints[2]);
	binaryheap_replace_first(h, "", (void *)&ints[11]);
	binaryheap_replace_first(h, "", (void *)&ints[1]);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

	/*
	 * And again for a min-heap.
	 */

	h = binaryheap_allocate(7, notc);
	binaryheap_add(h, "f", (void *)&ints[8]);
	binaryheap_add(h, "d", (void *)&ints[6]);
	binaryheap_add(h, "b", (void *)&ints[4]);
	binaryheap_add(h, "g", (void *)&ints[9]);
	binaryheap_add(h, "c", (void *)&ints[5]);
	binaryheap_add(h, "a", (void *)&ints[3]);
	binaryheap_add(h, "e", (void *)&ints[7]);
	binaryheap_replace_first(h, "", (void *)&ints[1]);
	binaryheap_replace_first(h, "", (void *)&ints[2]);
	binaryheap_replace_first(h, "", (void *)&ints[11]);
	binaryheap_replace_first(h, "", (void *)&ints[12]);
	print_heap(h);
	node = binaryheap_first(h);
	printf("%d - ", *(int *)node->value);
	while ((node = binaryheap_remove_first(h)) != NULL) {
		printf("%d ", *(int *)node->value);
	}
	printf("\n");
	binaryheap_free(h);

    return 0;
}

/*
 * The following functions recursively print a heap, with each node's
 * contents represented as "idx=key/val" followed by its children. An
 * empty heap is just "(empty)".
 */

void print_node(binaryheap *h, size_t node)
{
	int l = node*2+1;
	int r = node*2+2;

	printf("(%d=%s/%d", node, (char *)h->nodes[node].key,
		   *(int *)h->nodes[node].value);
	if (l < h->size) {
		printf (" ");
		print_node(h, node*2+1);
	}
	if (r < h->size) {
		printf (", ");
		print_node(h, node*2+2);
	}
	printf(")");
}

void print_heap(binaryheap *h)
{
	if (h->size == 0) {
		printf("(empty)\n");
		return;
	}

	print_node(h, 0);
	printf("\n");
}