Skip to content
Snippets Groups Projects
syntree.c 4.21 KiB
Newer Older
Marc-Jan Szpineter's avatar
Marc-Jan Szpineter committed
#include <stdio.h> // fprintf(), printf(), ...
#include <stddef.h> // NULL
#include <stdlib.h> // malloc(), ...

#include "syntree.h"

#define NODE_LIST_INIT_SIZE_IN_UNITS 1024
#define NODE_LIST_ADD_WHEN_FULL_IN_UNITS 1024
#define SIZE_OF_UNIT (sizeof (Node))

#define NODE_CHILDREN_LIST_INIT_SIZE_IN_UNITS 10
#define NODE_CHILDREN_LIST_ADD_WHEN_FULL_IN_UNITS 10

#define ERR_ALLOCATING_MEM -1

int syntreeInit(Syntree *self) {

    self->next_ID = 0;
    self->root = self->next_ID;
    self->next_ID++;

    self->size = 1;
    self->node_list = malloc(SIZE_OF_UNIT * NODE_LIST_INIT_SIZE_IN_UNITS);
    self->capacity = NODE_LIST_INIT_SIZE_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) {

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

    SyntreeNodeID id = self->next_ID++;

    if (self->size < self->capacity) {
        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;
    } else {
        /*TODO realloc()*/
    }

    return id;

}

SyntreeNodeID syntreeNodeTag(Syntree *self, SyntreeNodeID id) {

    SyntreeNodeID new_id = self->next_ID++;

    if (self->size < self->capacity) {
        self->node_list[new_id].val = 0;
        self->node_list[new_id].amount_of_children = 1;
        self->node_list[new_id].capacity_children = NODE_CHILDREN_LIST_INIT_SIZE_IN_UNITS;
        self->node_list[new_id].children = malloc( (sizeof (SyntreeNodeID)) * NODE_CHILDREN_LIST_INIT_SIZE_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;

    } else {
        /*TODO realloc()*/
    }

    if (self->root == 0) {
        self->root = new_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) {

    if (self->node_list[list].amount_of_children < self->node_list[list].capacity_children) {
        
        self->node_list[list].children[self->node_list[list].amount_of_children++] = elem;

    } else {
        /*TODO realloc()*/
    }

    return list;

}

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

    if (self->node_list[list].amount_of_children < self->node_list[list].capacity_children) {

        // 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++;

    } else {
        /*TODO realloc()*/
    }

    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;

}