From ea8cdd180adbf6c3dacd3c700482b72825a9b8c1 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 29 Nov 2020 09:25:41 +0100
Subject: Fix codelayout und eigene Testprogramme eingebaut.

---
 heap.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 56 insertions(+), 17 deletions(-)

(limited to 'heap.c')

diff --git a/heap.c b/heap.c
index b9c15fa..dec68a2 100644
--- a/heap.c
+++ b/heap.c
@@ -1,6 +1,7 @@
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <time.h>
 
 #include "util.h"
 
@@ -41,14 +42,17 @@ fixdown(T heap[], size_t i, size_t n)
 		const size_t r = RIGHT(i);
 		size_t       m = i;
 
-		if ( l < n && heap[m] < heap[l] )
+		if ( l < n && heap[m] < heap[l] ) {
 			m = l;
+		}
 
-		if ( r < n && heap[m] < heap[r] )
+		if ( r < n && heap[m] < heap[r] ) {
 			m = r;
+		}
 
-		if ( m == i )
+		if ( m == i ) {
 			break;
+		}
 
 		swap(heap, m, i);
 
@@ -59,8 +63,9 @@ fixdown(T heap[], size_t i, size_t n)
 static void
 heapify(T heap[], size_t n)
 {
-	for ( size_t i = n / 2 - 1; i >= 0; --i )
+	for ( size_t i = n / 2; i-- > 0; ) {
 		fixdown(heap, i, n);
+	}
 }
 
 static void
@@ -68,7 +73,7 @@ my_heapsort(T a[], size_t n)
 {
 	heapify(a, n);
 
-	for ( size_t i = n - 1; i >= 0; --i ) {
+	for ( size_t i = n; i-- > 0; ) {
 		swap(a, 0, i);
 		fixdown(a, 0, i);
 	}
@@ -90,8 +95,9 @@ pq_init(struct pq *pq)
 bool
 pq_push(struct pq *pq, T data)
 {
-	if ( pq->sz == NELEM(pq->heap) )
+	if ( pq->sz == NELEM(pq->heap) ) {
 		return false;
+	}
 
 	pq->heap[pq->sz] = data;
 	fixup(pq->heap, pq->sz);
@@ -102,8 +108,9 @@ pq_push(struct pq *pq, T data)
 bool
 pq_pop(struct pq *pq, T *data)
 {
-	if ( pq->sz == 0 )
+	if ( pq->sz == 0 ) {
 		return false;
+	}
 
 	*data = pq->heap[0];
 	--pq->sz;
@@ -119,26 +126,41 @@ print_heap(T heap[], size_t n)
 {
 	if ( n ) {
 		printf("%d", heap[0]);
-		for ( size_t i = 1; i != n; ++i )
+		for ( size_t i = 1; i != n; ++i ) {
 			printf(", %d", heap[i]);
+		}
 		putchar('\n');
 	}
 }
 
-int
-main(void)
+void
+test_heapsort(void)
 {
-#if 0 // Heap-Testprogramm
-	T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 };
+	static const size_t N = 1001;
+	T                   array[N];
 
-	print_heap(heap, 10);
+	puts("fülle....");
+	srand(time(NULL));
+	for ( size_t idx = 0; idx != NELEM(array); ++idx ) {
+		array[idx] = rand();
+	}
 
-	//heap[10] = 13; fixup(heap, 10);
-	swap(heap, 0, 9); fixdown(heap, 0, 9);
+	puts("sortiere....");
+	my_heapsort(array, NELEM(array));
 
-	print_heap(heap, 9);
-#endif
+	puts("teste...");
+	for ( size_t idx = 1; idx != NELEM(array); ++idx ) {
+		if ( array[idx - 1] > array[idx] ) {
+			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
+			exit(EXIT_FAILURE);
+		}
+	}
+	puts("ok");
+}
 
+void
+test_pq(void)
+{
 	struct pq pq[1];
 
 	pq_init(pq);
@@ -150,3 +172,20 @@ main(void)
 	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
+}
-- 
cgit v1.3