#include "mainwindow.h"
#include "ui_mainwindow.h"

MainWindow::MainWindow(QWidget *parent)
    : QMainWindow(parent)
    , ui(new Ui::MainWindow)
{
    ui->setupUi(this);
    scene = new QGraphicsScene(this);
    ui->treeView->setScene(scene);
}

MainWindow::~MainWindow()
{
    delete ui;
}

int TreeNode::getKey() const {
    return key;
}

void TreeNode::setKey(int key) {
    TreeNode::key = key;
}

TreeNode * TreeNode::getLeft() const {
    return left;
}

void TreeNode::setLeft(TreeNode *left) {
    TreeNode::left = left;
}

TreeNode * TreeNode::getRight() const {
    return right;
}

void TreeNode::setRight(TreeNode *right) {
    TreeNode::right = right;
}

TreeNode * TreeNode::getParent() const {
    return parent;
}

void TreeNode::setParent(TreeNode *parent) {
    TreeNode::parent = parent;
}


void MainWindow::addTreeNode(TreeNode *root, int key) {
    if (!root) {
        return;
    }
    TreeNode *toAdd = new TreeNode(key);
    TreeNode *cur = root;
    TreeNode *prev = root;
    while (cur) {
        prev = cur;
        if (cur->getKey() > key) { // going to the left
            cur = cur->getLeft();
        } else if (cur->getKey() < key) { // going to the right
            cur = cur->getRight();
        } else { // considering all nodes in a tree as unique
            return;
        }
    }
    if (prev->getKey() > key) {
        prev->setLeft(toAdd);
    } else if (prev->getKey() < key) {
        prev->setRight(toAdd);
    }
    toAdd->setParent(prev);
    return;
}

void MainWindow::removeTreeNode(Tree *tree, TreeNode *node, int key) {
    if (!node) {
        return;
    }
    if (key > node->getKey()) {
        removeTreeNode(tree, node->getRight(), key);
    } else if (key < node->getKey()) {
        removeTreeNode(tree, node->getLeft(), key);
    } else {
        if (node->getLeft() == nullptr && node->getRight() == nullptr) {
            if (node->getParent()) {
                TreeNode *parent = node->getParent();
                if (parent->getLeft() == node) {
                    parent->setLeft(nullptr);
                } else {
                    parent->setRight(nullptr);
                }
            }
            if (tree->getRoot() == node) {
                tree->setRoot(nullptr);
            }
            delete node;
        } else if (node->getLeft() == nullptr || node->getRight() == nullptr) {
            TreeNode *child = node->getLeft() == nullptr ? node->getRight() : node->getLeft();
            node->setKey(child->getKey());
            node->setRight(child->getRight());
            node->setLeft(child->getLeft());
            if (child->getLeft()) {
                child->getLeft()->setParent(node);
            }
            if (child->getRight()) {
                child->getRight()->setParent(node);
            }
            delete child;
        } else {
            if (node->getRight()->getLeft() == nullptr) {
                TreeNode *child = node->getRight();
                node->setKey(child->getKey());
                node->setRight(child->getRight());
                if (child->getRight()) {
                    child->getRight()->setParent(node);
                }
                delete child;
            } else {
                TreeNode *cur = node->getRight();
                while (cur->getLeft()) {
                    cur = cur->getLeft();
                }
                node->setKey(cur->getKey());
                removeTreeNode(tree, node->getRight(), cur->getKey());
            }
        }
    }
}


int MainWindow::height(TreeNode * a) {
    if (!a) return 0;
    return std::max(height(a->getLeft()), height(a->getRight())) + 1;
}

void MainWindow::print_tree(TreeNode* a, int x, int y)
{
    if (!a) return;

    const int offset = 30;
    const int r = 25;

    if (a->getLeft())
    {
        QLine line(x + r, y + r, x - offset * height(a->getLeft()) * height(a->getLeft()) + 10, y + 90);
        scene->addLine(line, QPen(Qt::black));
    }

    if (a->getRight())
    {
        QLine line(x + r, y + r, x + offset * height(a->getRight()) * height(a->getRight()) + 35, y + 90);
        scene->addLine(line, QPen(Qt::black));
    }

    for (double i = 2.0; i >= 0.0; i -= 0.1)
        scene->addEllipse(x - i, y - i, 2 * (r + i), 2 * (r + i), QPen(Qt::black), QBrush(Qt::white));


    QGraphicsTextItem* txtItem =
            new QGraphicsTextItem(QString(a->getKey()));


    txtItem->setPos(x + 15, y + 15);
    scene->addItem(txtItem);

    if (a->getLeft()) {
        print_tree(a->getLeft(), x - offset * height(a->getLeft()) * height(a->getLeft()), y + 75);
    }

    if (a->getRight()) {
        print_tree(a->getRight(), x + offset * height(a->getRight()) * height(a->getRight()), y + 75);
    }

}




void MainWindow::on_pushButton_clicked()
{
    scene->clear();
    int cur;
    TreeNode *root = nullptr;
    QString input =  ui->line->text();
    const char* str = input.toStdString().c_str();
    int n = input.length();
    for (int i = 0; i < n; ++i) {
            cur = str[i];
            if (!root) {
                root = new TreeNode(cur, nullptr);
            } else {
                addTreeNode(root, cur);
            }
        }
    print_tree(root, ui->treeView->geometry().x()/2, 0);

}