# HG changeset patch
# User hausers
# Date 1328784483 -3600
# Node ID 9ecc993a29ea029806c612b52bf4e10a714af0b1

initial heap implementation

diff -r 000000000000 -r 9ecc993a29ea PriorityQueue.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/PriorityQueue.c	Thu Feb 09 11:48:03 2012 +0100
@@ -0,0 +1,129 @@
+/*
+ *  Copyright 2009 OpenSourceStewardshipFoundation.org
+ *  Licensed under GNU General Public License version 2
+ *
+ * Author: hausers@cs.tu-berlin.de
+ */
+
+#include <limits.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "PriorityQueue.h"
+#ifndef DEBUG
+#include "../VMS/vmalloc.h"
+#endif
+
+#define left(i) 2*i
+#define right(i) 2*i+1
+#define parent(i) i/2
+
+#ifdef DEBUG
+#include <stdlib.h>
+#define VMS__malloc malloc
+#define VMS__free free
+#endif 
+
+void swap (PrioQueueStruc *Q, int a, int b) {
+	void *valTmp;
+	int keyTmp;
+	keyTmp= Q->data[a].key;
+	valTmp= Q->data[a].val;
+	Q->data[a].key= Q->data[b].key;
+	Q->data[a].val= Q->data[b].val;
+	Q->data[b].key= keyTmp;
+	Q->data[b].val= valTmp;
+	
+}
+
+bool increaseKey (PrioQueueStruc *Q, int i, int key) {
+	if (key < Q->data[i].key) return false; // increasing not possible
+
+	Q->data[i].key= key;
+	while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
+		swap(Q,i,parent(i));
+		i= parent(i);
+	}	
+	return true;
+}
+
+void heapify (PrioQueueStruc *Q, int i) {
+	int largest;
+	int l,r;
+	l= left(i);
+	r= right(i);
+	if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
+	else largest= i;
+	if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
+	if (largest != i) {
+		swap(Q,i,largest);
+		heapify(Q,largest);
+	}
+}
+
+void enlargePrioQ (PrioQueueStruc *Q)  {
+	size_t oldSize, newSize;
+	heapNode *oldData,*newData;
+
+	oldSize= Q->size;
+	newSize= 2*oldSize;
+
+	Q->maxSize= newSize;
+	newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
+	oldData= Q->data;
+
+	memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
+	Q->data= newData;
+
+	VMS__free(oldData);
+}
+
+
+PrioQueueStruc* makeVMSPrioQ () {
+	PrioQueueStruc *retQ;
+	retQ= VMS__malloc(sizeof(PrioQueueStruc));
+	retQ->maxSize= 1024;
+	retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
+	retQ->size= 0;
+	return retQ;
+}
+
+void* getFirstPrioQ (PrioQueueStruc *Q) {
+	return Q->data[0].val;
+}
+
+void* popPrioQ (PrioQueueStruc *Q) {
+	void *max;
+	if (Q->size < 1) max= NULL;
+	else {
+		max= Q->data[0].val;
+		swap(Q,0,Q->size-1);
+		Q->size--;
+		heapify(Q,0);
+	}	
+	return max;
+}
+
+bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
+	if (Q->size == Q->maxSize) enlargePrioQ(Q);
+
+	Q->size++;
+	Q->data[Q->size-1].key= INT_MIN;
+	Q->data[Q->size-1].val= val;
+
+	return increaseKey(Q,Q->size-1,key);
+}
+
+void printPrioQ (PrioQueueStruc *Q) {
+	int i;
+	printf("{");
+	if (Q->size>0) printf("%s",(char *)Q->data[0].val);
+	for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
+	printf("} ... ");
+
+}
+
+void freePrioQ (PrioQueueStruc *Q) {
+	VMS__free(Q->data);
+	VMS__free(Q);
+}
diff -r 000000000000 -r 9ecc993a29ea PriorityQueue.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/PriorityQueue.h	Thu Feb 09 11:48:03 2012 +0100
@@ -0,0 +1,41 @@
+/*
+ *  Copyright 2009 OpenSourceStewardshipFoundation.org
+ *  Licensed under GNU General Public License version 2
+ *
+ * Author: hausers@cs.tu-berlin.de
+ */
+
+#ifndef _PRIORITY_QUEUE_H
+#define _PRIORITY_QUEUE_H
+
+#include <stdbool.h>
+
+typedef struct _PrioQueueStruc PrioQueueStruc;
+typedef struct _heapNode heapNode;
+
+struct _heapNode {
+	int key;
+	void *val;
+};
+
+struct _PrioQueueStruc {
+	int size;
+	int maxSize;
+	
+	heapNode *data;
+};
+
+PrioQueueStruc* makeVMSPrioQ();
+void* getFirstPrioQ (PrioQueueStruc *Q);
+void* popPrioQ (PrioQueueStruc *Q);
+bool insertPrioQ (void *val, int key, PrioQueueStruc *Q);
+void freePrioQ (PrioQueueStruc *Q);
+
+#ifdef DEBUG
+void printPrioQ (PrioQueueStruc *Q);
+void swap (PrioQueueStruc *Q, int a, int b);
+#endif
+
+
+#endif
+
diff -r 000000000000 -r 9ecc993a29ea TestPriorityQueue.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TestPriorityQueue.c	Thu Feb 09 11:48:03 2012 +0100
@@ -0,0 +1,159 @@
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+#include "CUnit/Basic.h"
+#include "PriorityQueue.h"
+
+#ifndef DEBUG
+#define DEBUG
+#endif
+
+static PrioQueueStruc *Q; 
+static char *first,*second,*third;
+
+int init_suite (void) {
+	if (NULL == (Q= makeVMSPrioQ())) return -1;
+	else return 0;
+}
+
+int clean_suite (void) {
+	return 0;
+}
+
+void testInsertAElement (void) {
+	
+	first= malloc(3*sizeof(char));
+	first= "foo";
+
+	printf("SIZE = %d | ",Q->size);
+	printf("MAXSIZE = %d | ",Q->maxSize);
+	CU_ASSERT(true == insertPrioQ(first,0,Q));
+	printPrioQ(Q);
+	printf("SIZE = %d | ",Q->size);
+	printf("MAXSIZE = %d | ",Q->maxSize);
+}
+
+void testInsertOneElement (void) {
+	
+	first= malloc(3*sizeof(char));
+	first= "ten";
+
+	CU_ASSERT(true == insertPrioQ(first,10,Q));
+	printPrioQ(Q);
+}
+
+void testPopOneElement (void) {
+	popPrioQ(Q);
+}
+
+void testInsertSorted (void) {
+	second= malloc(4*sizeof(char));
+	second= "five";
+	
+	CU_ASSERT(true == insertPrioQ(second,5,Q));
+	printPrioQ(Q);
+}
+
+void testInsertAndHeapify (void) {
+	third= malloc(6*sizeof(char));
+	third= "twenty";
+
+	CU_ASSERT(true == insertPrioQ(third,20,Q));
+	printPrioQ(Q);
+}
+
+void testGetFirstElement (void) {
+	void* elem;
+
+	elem= getFirstPrioQ(Q);
+	CU_ASSERT(elem == third);
+	printPrioQ(Q);
+}
+
+void testSwap (void) {
+	swap(Q,0,2);
+	printPrioQ(Q);
+	swap(Q,2,0);
+	printPrioQ(Q);
+}
+
+void testPop (void) {
+	void *elem;
+	
+	elem= popPrioQ(Q);
+	CU_ASSERT(elem == third);
+	printPrioQ(Q);
+	printf("size = %d",Q->size);
+	elem= popPrioQ(Q);
+	CU_ASSERT(elem == first);
+	printPrioQ(Q);
+	printf("size = %d",Q->size);
+	elem= popPrioQ(Q);
+	CU_ASSERT(elem == second);
+	printPrioQ(Q);
+	printf("size = %d",Q->size);
+}
+
+void testPopEmptyQueue (void) {
+	void *elem;
+	CU_ASSERT (NULL == (elem= popPrioQ(Q)));
+}
+
+void testEnlargeQueue (void) {
+	int i;
+	char *elem;
+	for (i= 0; i<1163; i++) {
+		elem= malloc(5*sizeof(char));
+		sprintf(elem,"%d",i);
+		CU_ASSERT(true == insertPrioQ(elem,i,Q));
+	}
+}
+
+
+void testPopEnlargedQueue (void) {
+	int i;
+	char *elem; 
+	for (i= 1162; i>= 0; i--) {
+		elem= popPrioQ(Q);
+		CU_ASSERT(i == atoi(elem));
+	}
+	CU_ASSERT(NULL == popPrioQ(Q));
+}
+
+int main () {
+	CU_pSuite pSuite= NULL;
+
+	if (CUE_SUCCESS != CU_initialize_registry()) return CU_get_error();
+
+	pSuite= CU_add_suite("Simple Test Suite",init_suite, clean_suite);
+	if (NULL == pSuite) {
+		CU_cleanup_registry();
+		return CU_get_error();
+	}
+
+	if (NULL == CU_add_test(pSuite,"test of insert first element",testInsertOneElement) ||
+		NULL == CU_add_test(pSuite,"test of insert sorted",testInsertSorted) ||
+		NULL == CU_add_test(pSuite,"test of insert and heapify",testInsertAndHeapify) ||
+		NULL == CU_add_test(pSuite,"test of swap",testSwap) ||
+		NULL == CU_add_test(pSuite,"test of get top element",testGetFirstElement) ||
+		NULL == CU_add_test(pSuite,"test of pop elements",testPop) || 
+		NULL == CU_add_test(pSuite,"test of pop an empty queue",testPopEmptyQueue) || 
+	    NULL == CU_add_test(pSuite,"test of again a element",testInsertAElement) ||
+	    NULL == CU_add_test(pSuite,"test of remove the element",testPopOneElement) ||
+		NULL == CU_add_test(pSuite,"test of enlarge queue",testEnlargeQueue) || 
+		NULL == CU_add_test(pSuite,"test of pop enlarged queue",testPopEnlargedQueue)) {
+
+
+
+		CU_cleanup_registry();
+		return CU_get_error();
+	}
+	
+
+	CU_basic_set_mode(CU_BRM_VERBOSE);
+	CU_basic_run_tests();
+	CU_cleanup_registry();
+	return CU_get_error();
+}