/*
    For R2 reprezentation I used a structure called multiNode with a key, number of children and children array of pointers.
    For R3 reprezentation I used a structure called binaryNode with a key, and 2 pointers(i.e. first child and next brother).

    For T1 (i.e. convertParentToMultiway) we do it in O(n) efficiency. Despite the fact when we create a new node, we first create its parent,
the implementation manages to do it in O(n) because when we call to create a node we stop if it is already created
    For T2(i.e. convertMultiwayToBinary) we do it in O(n) efficiency. We travel each node once.

    I have an array of pointers to keep track of the nodes I create for R2.
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX_NR_CHILDREN 10
#define PRINT_SPACE 3

typedef struct multiNode_ {
    int key;
    int countChildren;
    struct multiNode_ *children[MAX_NR_CHILDREN];
} multiNode;

typedef struct binaryNode_ {
    int key;
    struct binaryNode_ *firstChild, *nextBrother;
} binaryNode;

multiNode *createMultiwayNode(int key)
{
    multiNode *newNode = NULL;
    newNode = (multiNode*)malloc(sizeof(multiNode));
    if (newNode == NULL)
    {
        printf("Not enough memory");
        exit(-2);
    }
    newNode->countChildren = 0;
    newNode->key = key;
    return newNode;
}

binaryNode *createBinaryNode(int key)
{
    binaryNode *newNode = NULL;
    newNode = (binaryNode*)malloc(sizeof(binaryNode));
    if (newNode == NULL)
    {
        printf("Not enough memory");
        exit(-2);
    }
    newNode->key = key;
    newNode->firstChild = newNode->nextBrother = NULL;
    return newNode;
}

void createNode(int i, int parent[], multiNode **nCreated, multiNode** root)
{
    //if node is already created
    if (nCreated[i] != NULL)
        return;

    nCreated[i] = createMultiwayNode(i);

    //if root found
    if (parent[i] == -1)
    {
        (*root) = nCreated[i];
        return;
    }

    //if parent isn't created, create it first
    if (nCreated[parent[i]] == NULL)
        createNode(parent[i], parent, nCreated, root);

    //by now we have parent created. Add node to its children list
    multiNode *parentNode = nCreated[parent[i]];
    parentNode->children[parentNode->countChildren] = nCreated[i];
    parentNode->countChildren++;

}

void convertParentToMultiway(int parent[], int size, multiNode **root)
{
    //need a vector to keep track if parent is created
    multiNode **nCreated = (multiNode**)malloc(size * sizeof(multiNode*));
    for (int i = 1; i < size; i++)
        nCreated[i] = NULL;

    for (int i = 1; i < size; i++)
        createNode(i, parent, nCreated, root);

}

void convertMultiwayToBinaryRec(multiNode *multiRoot, binaryNode *binaryRoot)
{
    binaryNode *brother = NULL;
    for (int i = 0; i < multiRoot->countChildren; i++)
    {

        if (i == 0)
        {
            binaryRoot->firstChild = createBinaryNode(multiRoot->children[0]->key);
            brother = binaryRoot->firstChild;
            convertMultiwayToBinaryRec(multiRoot->children[i], brother);
        }
        else
        {
            brother->nextBrother = createBinaryNode(multiRoot->children[i]->key);
            brother = brother->nextBrother;
            convertMultiwayToBinaryRec(multiRoot->children[i], brother);

        }
    }
}

void convertMultiwayToBinary(multiNode *multiRoot, binaryNode **binaryRoot)
{
    (*binaryRoot) = createBinaryNode(multiRoot->key);
    convertMultiwayToBinaryRec(multiRoot, *binaryRoot);
}

void prettyPrint(multiNode *binaryRoot, int level)
{
    for (int i = 1; i <= level * PRINT_SPACE; i++)
        printf(" ");
    printf("%d\n", binaryRoot->key);
    for (int i = 0; i < binaryRoot->countChildren; i++)
        prettyPrint(binaryRoot->children[i], level + 1);
}

void prettyPrint(binaryNode *binaryRoot, int level)
{
    for (int i = 1; i <= level * PRINT_SPACE; i++)
        printf(" ");
    printf("%d\n", binaryRoot->key);
    if (binaryRoot->firstChild != NULL)
        prettyPrint(binaryRoot->firstChild, level + 1);
    if (binaryRoot->nextBrother != NULL)
        prettyPrint(binaryRoot->nextBrother, level);
}

void printArray(int array[], int size)
{
    for (int i = 1; i < size; i++)
        printf("%2d ", i);
    printf("\n");
    for (int i = 1; i < size; i++)
        printf("%2d ", array[i]);
    printf("\n\n");
}

int main()
{
    int input[] = { 0, 2, 7, 5, 2, 7, 7, -1, 5, 2 };
    int inputSize = sizeof(input) / sizeof(int);

    multiNode *multiRoot = NULL;
    binaryNode *binaryRoot = NULL;

    convertParentToMultiway(input, inputSize, &multiRoot);
    convertMultiwayToBinary(multiRoot, &binaryRoot);

    printArray(input, inputSize);
    prettyPrint(binaryRoot, 0);
    return 0;
}