Newer
Older
/*
Gruppe: 22
Nirvan Charansurya Udaysingh Jhurree
Marc-Jan Szpineter
Sheung Tung Tony Tam
------------------
Eine dynamische liste (node_list) enthaelt die nodes des syntrees.
Jedem Knoten wird eine ID in Form eines unsigned int zugewiesen (beginnend bei 0) und ueber diese ID ist
der node auch direkt in der Liste referenzierbar (z.B. node_list[5]).
Der aktuelle ID-Wert wird im syntree gespeichert und bei jedem Knoten einfach hochgezaehlt.
Der root node ist ein dummy node, denn der Baum waechst von den Blaettern zur Wurzel
und es kann isolierte Knoten geben.
Jeder node hat eine Liste an children (dynamisch).
Dabei wird einfach eine Liste an SyntreeNodeIDs gespeichert.
Die Reihenfolge des Auftretens dieser IDs bestimmt die Reihenfolge im Baum von links nach rechts.
*/
#include <stdio.h> // fprintf(), printf(), ...
#include <stddef.h> // NULL
#include <stdlib.h> // malloc(), ...
#include "syntree.h"
#define NODE_LIST_INIT_CAPACITY_IN_UNITS 1024 // change to 1 to test if realloc() is implemented correctly
#define NODE_LIST_ADD_WHEN_FULL_IN_UNITS 1024 // ..
#define NODE_CHILDREN_LIST_INIT_CPACITY_IN_UNITS 10 // change to 1 to test if realloc() is implemented correctly
#define NODE_CHILDREN_LIST_ADD_WHEN_FULL_IN_UNITS 10 // ...
#define ERR_ALLOCATING_MEM -1
int syntreeInit(Syntree *self) {
self->root = self->next_ID++;
/* DEBUG */
//printf("syntreeInit(...), size: %d\n", self->size);
self->node_list = malloc(SIZE_OF_UNIT * NODE_LIST_INIT_CAPACITY_IN_UNITS);
self->capacity = NODE_LIST_INIT_CAPACITY_IN_UNITS;
if (self->node_list == NULL) {
fprintf(stderr, "ERROR during initilalization of syntree: received NULL pointer from malloc()\n");
return ERR_ALLOCATING_MEM;
}
self->node_list[self->root].val = 0;
self->node_list[self->root].amount_of_children = 0;
self->node_list[self->root].capacity_children = 0;
self->node_list[self->root].children = NULL;
return 0;
}
void syntreeRelease(Syntree *self) {
/* DEBUG */
//printf("syntreeRelease(...), size: %d\n", self->size);
for (int i = 0; i < self->size; ++i) {
free(self->node_list[i].children); // free all references to children from all nodes
}
free(self->node_list); // free all nodes
}
SyntreeNodeID syntreeNodeNumber(Syntree *self, int number) {
/* DEBUG */
//printf("syntreeNodeNumber(...), size: %d\n", self->size);
// realloc() on node_list
if (self->size >= self->capacity) {
syntree_allocateNewSpaceForNodes(self);
self->node_list[id].val = number;
self->node_list[id].amount_of_children = 0;
self->node_list[id].capacity_children = 0;
self->node_list[id].children = NULL;
self->size++;
return id;
}
SyntreeNodeID syntreeNodeTag(Syntree *self, SyntreeNodeID id) {
/* DEBUG */
//printf("syntreeNodeTag(...), size: %d\n", self->size);
// realloc() on node_list
if (self->size >= self->capacity) {
syntree_allocateNewSpaceForNodes(self);
}
self->node_list[new_id].val = 0;
self->node_list[new_id].amount_of_children = 1;
self->node_list[new_id].children = malloc( (sizeof (SyntreeNodeID)) * NODE_CHILDREN_LIST_INIT_CPACITY_IN_UNITS );
self->node_list[new_id].capacity_children = NODE_CHILDREN_LIST_INIT_CPACITY_IN_UNITS;
if (self->node_list[new_id].children == NULL) {
fprintf(stderr, "ERROR in function syntreeNodeTag(...): received NULL pointer from malloc()\n");
exit(ERR_ALLOCATING_MEM);
self->node_list[new_id].children[0] = id;
/*
if (self->root == 0) {
self->root = new_id;
}
return new_id;
}
SyntreeNodeID syntreeNodePair(Syntree *self, SyntreeNodeID id1, SyntreeNodeID id2) {
/* DEBUG */
//printf("syntreeNodePair(...), size: %d\n", self->size);
return syntreeNodeAppend(self, syntreeNodeTag(self,id1), id2);
}
SyntreeNodeID syntreeNodeAppend(Syntree *self, SyntreeNodeID list, SyntreeNodeID elem) {
/* DEBUG */
//printf("syntreeNodeAppend(...), size: %d\n", self->size);
// 'list' is no list node?
if (self->node_list[list].amount_of_children <= 0) {
fprintf(stderr, "ERROR in syntreeNodeAppend(...): list node with ID %d is no list node. The function didn't append element with ID %d.\n", list, elem);
// realloc() for children of list node 'list'
if (self->node_list[list].amount_of_children >= self->node_list[list].capacity_children) {
syntree_allocateNewSpaceForChildren(self, list);
}
self->node_list[list].children[self->node_list[list].amount_of_children++] = elem;
return list;
}
SyntreeNodeID syntreeNodePrepend(Syntree *self, SyntreeNodeID elem, SyntreeNodeID list) {
/* DEBUG */
//printf("syntreeNodePrepend(...), size: %d\n", self->size);
// 'list' is no list node?
if (self->node_list[list].amount_of_children <= 0) {
fprintf(stderr, "ERROR in syntreeNodePrepend(...): list node with ID %d is no list node. The function didn't append element with ID %d.\n", list, elem);
}
// realloc() for children of list node 'list'
if (self->node_list[list].amount_of_children >= self->node_list[list].capacity_children) {
syntree_allocateNewSpaceForChildren(self, list);
}
// move all IDs in the children list 1 up and add elem at index 0
for (int j = self->node_list[list].amount_of_children; j > 0; --j) {
self->node_list[list].children[j] = self->node_list[list].children[j-1];
self->node_list[list].children[0] = elem;
self->node_list[list].amount_of_children++;
return list;
}
void syntreePrint(const Syntree *self, SyntreeNodeID root) {
/* DEBUG */
//printf("syntreePrint(...)\n");
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
syntreePrint_rec(self, root);
if (self != NULL) {
printf("\n");
} else {
printf("<<Tree empty>>\n");
}
return;
}
void syntreePrint_rec(const Syntree *self, SyntreeNodeID root) {
if (self == NULL)
return;
if (self->node_list[root].amount_of_children == 0)
printf("(%d)", self->node_list[root].val);
else {
printf("{");
for (int i = 0; i < self->node_list[root].amount_of_children; ++i) {
syntreePrint_rec(self, self->node_list[root].children[i]);
};
printf("}");
}
return;
}
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
void syntree_allocateNewSpaceForNodes(Syntree *self) {
/* DEBUG */
//printf("syntree_allocateNewSpaceForNodes(...), size: %d\n", self->size);
Node * new_space = realloc(self->node_list, (self->capacity + NODE_LIST_ADD_WHEN_FULL_IN_UNITS) * SIZE_OF_UNIT);
if (new_space == NULL) {
free(self->node_list);
fprintf(stderr, "ERROR in syntree_allocateNewSpaceForNodes(...): realloc() out of memory or other reason for NULL\n");
exit(ERR_ALLOCATING_MEM);
} else {
self->capacity += NODE_LIST_ADD_WHEN_FULL_IN_UNITS;
self->node_list = new_space;
}
}
void syntree_allocateNewSpaceForChildren(Syntree *self, SyntreeNodeID id) {
/* DEBUG */
//printf("syntree_allocateNewSpaceForChildren(...), size: %d\n", self->size);
SyntreeNodeID * new_space = realloc( self->node_list[id].children, (self->node_list[id].capacity_children + NODE_CHILDREN_LIST_ADD_WHEN_FULL_IN_UNITS) * (sizeof (SyntreeNodeID)) );
if (new_space == NULL) {
free(self->node_list[id].children);
fprintf(stderr, "ERROR in syntree_allocateNewSpaceForChildren(...): realloc() out of memory or other reason for NULL\n");
exit(ERR_ALLOCATING_MEM);
} else {
self->node_list[id].capacity_children += NODE_CHILDREN_LIST_ADD_WHEN_FULL_IN_UNITS;
self->node_list[id].children = new_space;
}
}