1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/PriorityQueue.c	Thu Feb 09 11:48:03 2012 +0100
     1.3 @@ -0,0 +1,129 @@
     1.4 +/*
     1.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     1.6 + *  Licensed under GNU General Public License version 2
     1.7 + *
     1.8 + * Author: hausers@cs.tu-berlin.de
     1.9 + */
    1.10 +
    1.11 +#include <limits.h>
    1.12 +#include <stdio.h>
    1.13 +#include <string.h>
    1.14 +
    1.15 +#include "PriorityQueue.h"
    1.16 +#ifndef DEBUG
    1.17 +#include "../VMS/vmalloc.h"
    1.18 +#endif
    1.19 +
    1.20 +#define left(i) 2*i
    1.21 +#define right(i) 2*i+1
    1.22 +#define parent(i) i/2
    1.23 +
    1.24 +#ifdef DEBUG
    1.25 +#include <stdlib.h>
    1.26 +#define VMS__malloc malloc
    1.27 +#define VMS__free free
    1.28 +#endif 
    1.29 +
    1.30 +void swap (PrioQueueStruc *Q, int a, int b) {
    1.31 +	void *valTmp;
    1.32 +	int keyTmp;
    1.33 +	keyTmp= Q->data[a].key;
    1.34 +	valTmp= Q->data[a].val;
    1.35 +	Q->data[a].key= Q->data[b].key;
    1.36 +	Q->data[a].val= Q->data[b].val;
    1.37 +	Q->data[b].key= keyTmp;
    1.38 +	Q->data[b].val= valTmp;
    1.39 +	
    1.40 +}
    1.41 +
    1.42 +bool increaseKey (PrioQueueStruc *Q, int i, int key) {
    1.43 +	if (key < Q->data[i].key) return false; // increasing not possible
    1.44 +
    1.45 +	Q->data[i].key= key;
    1.46 +	while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
    1.47 +		swap(Q,i,parent(i));
    1.48 +		i= parent(i);
    1.49 +	}	
    1.50 +	return true;
    1.51 +}
    1.52 +
    1.53 +void heapify (PrioQueueStruc *Q, int i) {
    1.54 +	int largest;
    1.55 +	int l,r;
    1.56 +	l= left(i);
    1.57 +	r= right(i);
    1.58 +	if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
    1.59 +	else largest= i;
    1.60 +	if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
    1.61 +	if (largest != i) {
    1.62 +		swap(Q,i,largest);
    1.63 +		heapify(Q,largest);
    1.64 +	}
    1.65 +}
    1.66 +
    1.67 +void enlargePrioQ (PrioQueueStruc *Q)  {
    1.68 +	size_t oldSize, newSize;
    1.69 +	heapNode *oldData,*newData;
    1.70 +
    1.71 +	oldSize= Q->size;
    1.72 +	newSize= 2*oldSize;
    1.73 +
    1.74 +	Q->maxSize= newSize;
    1.75 +	newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
    1.76 +	oldData= Q->data;
    1.77 +
    1.78 +	memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
    1.79 +	Q->data= newData;
    1.80 +
    1.81 +	VMS__free(oldData);
    1.82 +}
    1.83 +
    1.84 +
    1.85 +PrioQueueStruc* makeVMSPrioQ () {
    1.86 +	PrioQueueStruc *retQ;
    1.87 +	retQ= VMS__malloc(sizeof(PrioQueueStruc));
    1.88 +	retQ->maxSize= 1024;
    1.89 +	retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
    1.90 +	retQ->size= 0;
    1.91 +	return retQ;
    1.92 +}
    1.93 +
    1.94 +void* getFirstPrioQ (PrioQueueStruc *Q) {
    1.95 +	return Q->data[0].val;
    1.96 +}
    1.97 +
    1.98 +void* popPrioQ (PrioQueueStruc *Q) {
    1.99 +	void *max;
   1.100 +	if (Q->size < 1) max= NULL;
   1.101 +	else {
   1.102 +		max= Q->data[0].val;
   1.103 +		swap(Q,0,Q->size-1);
   1.104 +		Q->size--;
   1.105 +		heapify(Q,0);
   1.106 +	}	
   1.107 +	return max;
   1.108 +}
   1.109 +
   1.110 +bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
   1.111 +	if (Q->size == Q->maxSize) enlargePrioQ(Q);
   1.112 +
   1.113 +	Q->size++;
   1.114 +	Q->data[Q->size-1].key= INT_MIN;
   1.115 +	Q->data[Q->size-1].val= val;
   1.116 +
   1.117 +	return increaseKey(Q,Q->size-1,key);
   1.118 +}
   1.119 +
   1.120 +void printPrioQ (PrioQueueStruc *Q) {
   1.121 +	int i;
   1.122 +	printf("{");
   1.123 +	if (Q->size>0) printf("%s",(char *)Q->data[0].val);
   1.124 +	for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
   1.125 +	printf("} ... ");
   1.126 +
   1.127 +}
   1.128 +
   1.129 +void freePrioQ (PrioQueueStruc *Q) {
   1.130 +	VMS__free(Q->data);
   1.131 +	VMS__free(Q);
   1.132 +}

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/PriorityQueue.h	Thu Feb 09 11:48:03 2012 +0100
     2.3 @@ -0,0 +1,41 @@
     2.4 +/*
     2.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     2.6 + *  Licensed under GNU General Public License version 2
     2.7 + *
     2.8 + * Author: hausers@cs.tu-berlin.de
     2.9 + */
    2.10 +
    2.11 +#ifndef _PRIORITY_QUEUE_H
    2.12 +#define _PRIORITY_QUEUE_H
    2.13 +
    2.14 +#include <stdbool.h>
    2.15 +
    2.16 +typedef struct _PrioQueueStruc PrioQueueStruc;
    2.17 +typedef struct _heapNode heapNode;
    2.18 +
    2.19 +struct _heapNode {
    2.20 +	int key;
    2.21 +	void *val;
    2.22 +};
    2.23 +
    2.24 +struct _PrioQueueStruc {
    2.25 +	int size;
    2.26 +	int maxSize;
    2.27 +	
    2.28 +	heapNode *data;
    2.29 +};
    2.30 +
    2.31 +PrioQueueStruc* makeVMSPrioQ();
    2.32 +void* getFirstPrioQ (PrioQueueStruc *Q);
    2.33 +void* popPrioQ (PrioQueueStruc *Q);
    2.34 +bool insertPrioQ (void *val, int key, PrioQueueStruc *Q);
    2.35 +void freePrioQ (PrioQueueStruc *Q);
    2.36 +
    2.37 +#ifdef DEBUG
    2.38 +void printPrioQ (PrioQueueStruc *Q);
    2.39 +void swap (PrioQueueStruc *Q, int a, int b);
    2.40 +#endif
    2.41 +
    2.42 +
    2.43 +#endif
    2.44 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/TestPriorityQueue.c	Thu Feb 09 11:48:03 2012 +0100
     3.3 @@ -0,0 +1,159 @@
     3.4 +#include <stdbool.h>
     3.5 +#include <stdio.h>
     3.6 +#include <stdlib.h>
     3.7 +
     3.8 +
     3.9 +#include "CUnit/Basic.h"
    3.10 +#include "PriorityQueue.h"
    3.11 +
    3.12 +#ifndef DEBUG
    3.13 +#define DEBUG
    3.14 +#endif
    3.15 +
    3.16 +static PrioQueueStruc *Q; 
    3.17 +static char *first,*second,*third;
    3.18 +
    3.19 +int init_suite (void) {
    3.20 +	if (NULL == (Q= makeVMSPrioQ())) return -1;
    3.21 +	else return 0;
    3.22 +}
    3.23 +
    3.24 +int clean_suite (void) {
    3.25 +	return 0;
    3.26 +}
    3.27 +
    3.28 +void testInsertAElement (void) {
    3.29 +	
    3.30 +	first= malloc(3*sizeof(char));
    3.31 +	first= "foo";
    3.32 +
    3.33 +	printf("SIZE = %d | ",Q->size);
    3.34 +	printf("MAXSIZE = %d | ",Q->maxSize);
    3.35 +	CU_ASSERT(true == insertPrioQ(first,0,Q));
    3.36 +	printPrioQ(Q);
    3.37 +	printf("SIZE = %d | ",Q->size);
    3.38 +	printf("MAXSIZE = %d | ",Q->maxSize);
    3.39 +}
    3.40 +
    3.41 +void testInsertOneElement (void) {
    3.42 +	
    3.43 +	first= malloc(3*sizeof(char));
    3.44 +	first= "ten";
    3.45 +
    3.46 +	CU_ASSERT(true == insertPrioQ(first,10,Q));
    3.47 +	printPrioQ(Q);
    3.48 +}
    3.49 +
    3.50 +void testPopOneElement (void) {
    3.51 +	popPrioQ(Q);
    3.52 +}
    3.53 +
    3.54 +void testInsertSorted (void) {
    3.55 +	second= malloc(4*sizeof(char));
    3.56 +	second= "five";
    3.57 +	
    3.58 +	CU_ASSERT(true == insertPrioQ(second,5,Q));
    3.59 +	printPrioQ(Q);
    3.60 +}
    3.61 +
    3.62 +void testInsertAndHeapify (void) {
    3.63 +	third= malloc(6*sizeof(char));
    3.64 +	third= "twenty";
    3.65 +
    3.66 +	CU_ASSERT(true == insertPrioQ(third,20,Q));
    3.67 +	printPrioQ(Q);
    3.68 +}
    3.69 +
    3.70 +void testGetFirstElement (void) {
    3.71 +	void* elem;
    3.72 +
    3.73 +	elem= getFirstPrioQ(Q);
    3.74 +	CU_ASSERT(elem == third);
    3.75 +	printPrioQ(Q);
    3.76 +}
    3.77 +
    3.78 +void testSwap (void) {
    3.79 +	swap(Q,0,2);
    3.80 +	printPrioQ(Q);
    3.81 +	swap(Q,2,0);
    3.82 +	printPrioQ(Q);
    3.83 +}
    3.84 +
    3.85 +void testPop (void) {
    3.86 +	void *elem;
    3.87 +	
    3.88 +	elem= popPrioQ(Q);
    3.89 +	CU_ASSERT(elem == third);
    3.90 +	printPrioQ(Q);
    3.91 +	printf("size = %d",Q->size);
    3.92 +	elem= popPrioQ(Q);
    3.93 +	CU_ASSERT(elem == first);
    3.94 +	printPrioQ(Q);
    3.95 +	printf("size = %d",Q->size);
    3.96 +	elem= popPrioQ(Q);
    3.97 +	CU_ASSERT(elem == second);
    3.98 +	printPrioQ(Q);
    3.99 +	printf("size = %d",Q->size);
   3.100 +}
   3.101 +
   3.102 +void testPopEmptyQueue (void) {
   3.103 +	void *elem;
   3.104 +	CU_ASSERT (NULL == (elem= popPrioQ(Q)));
   3.105 +}
   3.106 +
   3.107 +void testEnlargeQueue (void) {
   3.108 +	int i;
   3.109 +	char *elem;
   3.110 +	for (i= 0; i<1163; i++) {
   3.111 +		elem= malloc(5*sizeof(char));
   3.112 +		sprintf(elem,"%d",i);
   3.113 +		CU_ASSERT(true == insertPrioQ(elem,i,Q));
   3.114 +	}
   3.115 +}
   3.116 +
   3.117 +
   3.118 +void testPopEnlargedQueue (void) {
   3.119 +	int i;
   3.120 +	char *elem; 
   3.121 +	for (i= 1162; i>= 0; i--) {
   3.122 +		elem= popPrioQ(Q);
   3.123 +		CU_ASSERT(i == atoi(elem));
   3.124 +	}
   3.125 +	CU_ASSERT(NULL == popPrioQ(Q));
   3.126 +}
   3.127 +
   3.128 +int main () {
   3.129 +	CU_pSuite pSuite= NULL;
   3.130 +
   3.131 +	if (CUE_SUCCESS != CU_initialize_registry()) return CU_get_error();
   3.132 +
   3.133 +	pSuite= CU_add_suite("Simple Test Suite",init_suite, clean_suite);
   3.134 +	if (NULL == pSuite) {
   3.135 +		CU_cleanup_registry();
   3.136 +		return CU_get_error();
   3.137 +	}
   3.138 +
   3.139 +	if (NULL == CU_add_test(pSuite,"test of insert first element",testInsertOneElement) ||
   3.140 +		NULL == CU_add_test(pSuite,"test of insert sorted",testInsertSorted) ||
   3.141 +		NULL == CU_add_test(pSuite,"test of insert and heapify",testInsertAndHeapify) ||
   3.142 +		NULL == CU_add_test(pSuite,"test of swap",testSwap) ||
   3.143 +		NULL == CU_add_test(pSuite,"test of get top element",testGetFirstElement) ||
   3.144 +		NULL == CU_add_test(pSuite,"test of pop elements",testPop) || 
   3.145 +		NULL == CU_add_test(pSuite,"test of pop an empty queue",testPopEmptyQueue) || 
   3.146 +	    NULL == CU_add_test(pSuite,"test of again a element",testInsertAElement) ||
   3.147 +	    NULL == CU_add_test(pSuite,"test of remove the element",testPopOneElement) ||
   3.148 +		NULL == CU_add_test(pSuite,"test of enlarge queue",testEnlargeQueue) || 
   3.149 +		NULL == CU_add_test(pSuite,"test of pop enlarged queue",testPopEnlargedQueue)) {
   3.150 +
   3.151 +
   3.152 +
   3.153 +		CU_cleanup_registry();
   3.154 +		return CU_get_error();
   3.155 +	}
   3.156 +	
   3.157 +
   3.158 +	CU_basic_set_mode(CU_BRM_VERBOSE);
   3.159 +	CU_basic_run_tests();
   3.160 +	CU_cleanup_registry();
   3.161 +	return CU_get_error();
   3.162 +}