syntree.c

/*
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 root node hat ID 0 und wird erstmal nicht gebraucht, hat aber den Effekt, dass damit die Rechnung bei 1 beginnt.
(Der root node ist ein dummy node, denn der Baum waechst von den Blaettern zur Wurzel
und es kann isolierte Knoten geben).

Der aktuelle ID-Wert wird im syntree gespeichert und bei jedem Knoten einfach hochgezaehlt.

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 SIZE_OF_UNIT (sizeof (Node))

#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->size = 0;
    self->next_ID = 0;
    self->root = self->next_ID++;

    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;

    self->size++;

    return 0;

}

void syntreeRelease(Syntree *self) {

    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

    self->size = 0;

}

SyntreeNodeID syntreeNodeNumber(Syntree *self, int number) {

    SyntreeNodeID id = self->next_ID++;

    // 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) {

    SyntreeNodeID new_id = self->next_ID++;

    // realloc() on node_list
    if (self->size >= self->capacity) {
        syntree_allocateNewSpaceForNodes(self);
    }

    self->size++; // added the list node

    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;

    return new_id;

}

SyntreeNodeID syntreeNodePair(Syntree *self, SyntreeNodeID id1, SyntreeNodeID id2) {

    return syntreeNodeAppend(self, syntreeNodeTag(self,id1), id2);

}

SyntreeNodeID syntreeNodeAppend(Syntree *self, SyntreeNodeID list, SyntreeNodeID elem) {

    // '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) {

    // '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) {

    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;

}

void syntree_allocateNewSpaceForNodes(Syntree *self) {

    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) {

    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;
	}

}