// TreeHeader.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include "pch.h"
#define _CRT_SECURE_NO_WARNINGS
#define MAX_OFFSET_SIZE 100
#define OFFSET_BETWEEN_ONE_PARENT_SIBLINGS 15
#define OFFSET_BETWEEN_SIBLINGS 30
#define OFFSET_DELTA 15
#include <stdio.h>
#include <stdlib.h>


struct Tnode {
    int value;
    int id;
    Tnode* leftSibling;
    Tnode* rightSibling;
    Tnode* leftChild;
    Tnode* parent;
};

Tnode* findLastChild(Tnode* parent) {
    Tnode* child = parent->leftChild;
    while (child->rightSibling != NULL)
    {
        child = child->rightSibling;
    }
    return child;
}


void findNodeWithId(Tnode* firstNode, int id, Tnode** resultNode) {
    if (firstNode != NULL)
    {
        if (firstNode->id == id)
        {
            *resultNode = firstNode;

        }
    }
    Tnode* thisNode = firstNode->leftChild;
    if (thisNode != NULL) {
        while (thisNode != NULL) {
            findNodeWithId(thisNode, id, resultNode);
            thisNode = thisNode->rightSibling;
        }
    }

}

struct Tnode* addNodeToTree(Tnode* root, int parentId, int value, int id) {

    if (parentId == -1) {
        struct Tnode* node = (struct Tnode*)malloc(sizeof(struct Tnode));
        node->value = value;
        node->id =id;
        node->parent = NULL;
        node->rightSibling = NULL;
        node->leftSibling = NULL;
        node->leftChild = NULL;
        return node;
    }
    else {
        Tnode* parent = NULL;
        Tnode** resultS = &parent;
        findNodeWithId(root, parentId, resultS);
        struct Tnode* child = (struct Tnode*)malloc(sizeof(struct Tnode));
        if (parent->leftChild!=NULL)
        {
            Tnode* lastChild = findLastChild(parent);
            lastChild->rightSibling = child;
            child->leftSibling = lastChild;
            child->parent = parent;
            child->value = value;
            child->leftChild = NULL;
            child->rightSibling = NULL;
            child->id = id;
            return child;
        }
        else {
            parent->leftChild = child;
            child->value = value;
            child->id = id;
            child->leftSibling = NULL;
            child->parent = parent;
            child->leftChild = NULL;
            child->rightSibling = NULL;
            return child;
        }

    }


}


int findDegree(Tnode* node) {
    int degree = 0;
    Tnode* currentNode = node->leftChild;
    while (currentNode != NULL)
    {
        currentNode = currentNode->rightSibling;
        ++degree;

    }
    return degree;
}


void deleteLeaf(Tnode* node) {
    if (node->parent != NULL)
    {
        if (node->parent->leftChild == node && node->rightSibling != NULL) {
            node->parent->leftChild = node->rightSibling;
        }
        if (node->parent->leftChild == node && node->rightSibling == NULL) {
            node->parent->leftChild = NULL;
        }
    }
    if (node->rightSibling != NULL)
    {
        node->rightSibling->leftSibling = NULL;
    }

    if (node->leftSibling != NULL && node->rightSibling != NULL)
    {
        node->leftSibling->rightSibling = node->rightSibling;
        node->leftSibling = node->rightSibling->leftSibling;
    }
    if (node->leftSibling != NULL && node->rightSibling == NULL)
    {
        node->leftSibling->rightSibling = NULL;
    }
    free(node);

}




void deleteNode(Tnode* node) {
    if (node->parent != NULL)
    {
        if (node->parent->leftChild == node && node->rightSibling != NULL) {
            node->parent->leftChild = node->rightSibling;
        }
        if (node->parent->leftChild == node && node->rightSibling == NULL) {
            node->parent->leftChild = NULL;
        }
    }
    if (node->leftSibling != NULL && node->rightSibling != NULL)
    {
        node->leftSibling->rightSibling = node->rightSibling;
        node->leftSibling = node->rightSibling->leftSibling;
    }
    if (node->leftSibling != NULL && node->rightSibling == NULL)
    {
        node->leftSibling->rightSibling = NULL;
    }
    if (node->rightSibling != NULL)
    {
        node->rightSibling->leftSibling = NULL;
    }
    if (node->leftChild == NULL) {
        if (node->rightSibling != NULL) {
            deleteNode(node->rightSibling);
            node->rightSibling = NULL;
        }

        free(node);
    }
    else
    {
        if (node->rightSibling != NULL) {
            deleteNode(node->rightSibling);
        }
        deleteNode(node->leftChild);

        free(node);
    }


}

char* makeOffsetStr(int offset) {
    char arr[512];
    _itoa(offset, arr, 10);
    char result[1024];
    snprintf(result, sizeof  result, "%s%s%s", "%", arr, "s");
    return result;
}



void traverseTree(Tnode* root) {
    Tnode* thisNode = root->leftChild;
    if (thisNode != NULL) {
        while (thisNode != NULL) {
            printf("%d\n", thisNode->id);
            traverseTree(thisNode);
            thisNode = thisNode->rightSibling;
        }
    }

}


void printTree(Tnode* root,int offset,int offsetDelta) {
    int thisOffset = offset;
    if (root->id == 0) {
        thisOffset += offsetDelta;
        printf(makeOffsetStr(offset), "");
        printf("%s%d%s%d%s\n", "(", root->id, ":", root->value, ")");
    }
    Tnode* thisNode = root->leftChild;
    if (thisNode != NULL) {
        while (thisNode != NULL) {
            printf(makeOffsetStr(thisOffset), "");
            printf("%s%d%s%d%s\n","(", thisNode->id,":",thisNode->value,")");
            printTree(thisNode,thisOffset +offsetDelta, offsetDelta);
            thisNode = thisNode->rightSibling;
        }
    }

}




int isNodeALeaf(Tnode* node) {
    if (node->leftChild!=NULL)
    {
        return 0;
    }
    else {
        return 1;
    }
}


void menu() {
    printf("---MENU-------\n");
    printf("a - add node\n");
    printf("v - view tree \n");
    printf("d - del node\n");
    printf("f - find node degree \n");
    printf("q - exit      \n");
}

int main()
{
    int id = 0;
    Tnode* root =NULL;
    Tnode* result = NULL;

    //++id;
    menu();
    while (1) {
        char typ;
        printf("type command\n");
        scanf(" %c", &typ);
        switch (typ) {
            int val;
        case 'a':
            int value;
            printf("type parent id and value, if you want to add root type -1 and value:\n");
            scanf("%d%d", &val, &value);

            if (val == -1) {
                root = addNodeToTree(NULL, val, value, id);
            }
            else {
                addNodeToTree(root, val, value, id);
            }
            ++id;

            break;
        case 'v':
            printf("each vertex is in format (id:value)\n");
            printTree(root, 0, OFFSET_DELTA);
            break;
        case 'd':
            printf("type node id:\n");
            scanf("%d", &val);
            findNodeWithId(root, val, &result);
            if (isNodeALeaf(result)) {
                deleteLeaf(result);
            }
            else {
                deleteNode(result);
            }
            break;
        case 'f':
            printf("type node id\n");
            scanf("%d", &val);
            findNodeWithId(root, val, &result);
            printf("%d\n",findDegree(result));
            break;
        case 'q':
            exit(0);
            break;
        case '?':
            menu();
            break;
        default:
            printf("Wrong value\n");
            break;
        }
    }

}