//
//  Tree.cpp
//  ADS P3
//

#include "Tree.h"
#include "TreeNode.h"
#include <iomanip>
#include <iostream>
#include <string>
#include <queue>

Tree::Tree() : m_anker{ nullptr }, m_currentNodeChronologicalID{ 0 } {}

Tree::~Tree() {
	deleteAll(m_anker);
}

void Tree::deleteAll(TreeNode* _anker) {
	if (_anker != nullptr) {
		deleteAll(_anker->getLeft());
		deleteAll(_anker->getRight());
		delete _anker;
	}
	return;
}

bool Tree::isLeaf(TreeNode* _node) {
	if (!_node->getLeft() && !_node->getRight())
		return true;
	return false;
}

void Tree::balance(TreeNode* node) {
	TreeNode* ptr = node;
	TreeNode* par = ptr->getParent();

	while (par) {
		// parent & ptr sind rot
		if (ptr->getRed() && par->getRed()) {
			// Knoten ist links von parent
			if (par->getLeft() == ptr) {
				// parent ist links von grandparent
				if (par->getParent()->getLeft() == par)
					rotateTreeRight(par->getParent(), par);
				//			PP
				//	P
				//		ptr
				else {
					rotateTreeRight(par, ptr);
					rotateTreeLeft(ptr->getParent(), ptr);
				}
			}
			// Knoten ist rechts von parent
			else {
				// parent ist rechts von grandparent
				if (par->getParent()->getRight() == par)
					rotateTreeLeft(par->getParent(), par);
				//		PP
				//				p
				//			ptr
				else {
					rotateTreeLeft(par, ptr);
					rotateTreeRight(ptr->getParent(), ptr);
				}
			}
		}
		ptr = par;
		par = ptr->getParent();
	}
	return;
}

bool Tree::split4Node(TreeNode* node) {
	TreeNode* left = node->getLeft();
	TreeNode* right = node->getRight();

	if (!node || node->getRed() || !left || !right)
		return false;
	else {
		if (left->getRed() && right->getRed()) {
			left->setRed(false);
			right->setRed(false);
			if (node != m_anker)
				node->setRed(true);
			return true;
		}
	}
	return false;
}

void Tree::height() {
	int proof = proofRBCriterion(m_anker);
	if (proof == -1)
		std::cout << "Error proofRBCriterion()" << std::endl;
	else {
		std::cout << std::endl
			<< "Root has height: " << proof << std::endl;
	}
}

int Tree::proofRBCriterion() {
	return proofRBCriterion(this->m_anker);
}

int Tree::proofRBCriterion(TreeNode* node) {
	if (!node)
		return 0; // -1, da nicht existend

	int left = proofRBCriterion(node->getLeft());
	int right = proofRBCriterion(node->getRight());

	// Fall 1: nur ein Nachfolger
	if ((!node->getRight() && node->getLeft()) || (!node->getLeft() && node->getRight())) {
		// Nachfolger ist rechts
		if (node->getRight()) {
			if (node->getRight()->getRed()) // roter Nachfolger ist auf dem selben Nivau
				return right;
			else // schwarzer Nachfolger ist ein Niveau tiefer
				return ++right;
		}
		// Nachfolger ist links
		else {
			if (node->getLeft()->getRed()) // roter Nachfolger ist auf dem selben Nivau
				return left;
			else // schwarzer Nachfolger ist ein Niveau tiefer
				return ++left;
		}
	}

	// Fall 2-4: mit zwei Nachfolgern
	else if (node->getRight() && node->getLeft()) {

		// Fall 2: ein Nachfolger ist rot
		if ((node->getLeft()->getRed() && !node->getRight()->getRed()) || (!node->getLeft()->getRed() && node->getRight()->getRed())) {

			if (node->getLeft()->getRed() && left == right + 1) // links ist rot
				return left;
			else if (node->getRight()->getRed() && right == left + 1) // rechts ist rot
				return right;
			else // Fehler in der Zählung
				return -1;
		}
		// Fall 3: beide Nachfolger sind rot => 4er Knoten
		if (node->getLeft()->getRed() && node->getRight()->getRed()) {
			if (left == right) // beide müssen auf dem selben Niveu sein
				return left;
			else // Fehler in der Zählung
				return -1;
		}
		// Fall 5: beide Nachfolger sind schwarz
		else {
			if (left == right) // beide müssen auf dem selben Niveu sein
				return ++left;
			else
				return -1;
		}
	}
	// Fall 5: keine Nachfolger
	else
		return 0;
}

bool Tree::rotateTreeRight(TreeNode* _parent, TreeNode* _child) {
	_parent->setLeft(_child->getRight());
	if (_child->getRight())
		_child->getRight()->setParent(_parent);

	_child->setParent(_parent->getParent());

	if (!_parent->getParent())
		m_anker = _child;

	else if (_parent == _parent->getParent()->getLeft())
		_parent->getParent()->setLeft(_child);

	else
		_parent->getParent()->setRight(_child);

	_child->setRight(_parent);
	_child->setRed(false);
	_parent->setParent(_child);
	_parent->setRed(true);
	return true;
}

bool Tree::rotateTreeLeft(TreeNode* _parent, TreeNode* _child) {
	_parent->setRight(_child->getLeft());
	if (_child->getLeft())
		_child->getLeft()->setParent(_parent);

	_child->setParent(_parent->getParent());

	if (!_parent->getParent()) {
		m_anker = _child;
	}
	else if (_parent == _parent->getParent()->getLeft()) {
		_parent->getParent()->setLeft(_child);
	}
	else
		_parent->getParent()->setRight(_child);

	_child->setLeft(_parent);
	_child->setRed(false);
	_parent->setParent(_child);
	_parent->setRed(true);
	return true;
}

bool Tree::searchNode(std::string _name) {
	bool found = false;
	helpSearch(m_anker, _name, found);
	if (!found)
		std::cout << "+  Datensatz nicht gefunden." << std::endl;
	return found;
}

void Tree::helpSearch(TreeNode* _anker, std::string _name, bool& _found) {
	if (_anker != nullptr) {
		if (_anker->getName() == _name) {
			_found = true;
			std::cout << "+ Fundstelle:";
			printerHeader();
			_anker->print();
		}
		helpSearch(_anker->getLeft(), _name, _found);
		helpSearch(_anker->getRight(), _name, _found);
	}
	return;
}

bool Tree::addNode(std::string _name, int _age, double _income, int _postCode) {
	TreeNode* leaf = new TreeNode(0, m_currentNodeChronologicalID, _name, _income, _postCode, _age);
	m_currentNodeChronologicalID++;

	if (m_anker == nullptr) {
		leaf->setRed(false);
		m_anker = leaf;
		return true;
	}

	TreeNode* ptr = m_anker;
	TreeNode* par = ptr;
	while (ptr != nullptr) {
		par = ptr;
		split4Node(ptr);
		if (leaf->getNodeOrderID() < ptr->getNodeOrderID())
			ptr = ptr->getLeft();
		else
			ptr = ptr->getRight();
	}

	if (leaf->getNodeOrderID() < par->getNodeOrderID())
		par->setLeft(leaf);
	else
		par->setRight(leaf);
	leaf->setParent(par);

	m_anker->setRed(false);
	balance(leaf);
	return true;
}


// Print Funktionen 

void Tree::printAll() {
	printerHeader();
	printer(m_anker);
	std::cout << "-----+-------------+-----+----------+----------+--------+" << std::endl;
	height();
}

void Tree::printer(TreeNode* node) {
	if (!node)
		return;
	node->print();
	printer(node->getLeft());
	printer(node->getRight());
	return;
}

void Tree::printLevel(TreeNode* _anker) {
	if (!_anker)
		return;
	if (!_anker->getRed())
		_anker->print();
	if (_anker->getLeft()) {
		if (_anker->getLeft()->getRed())
			_anker->getLeft()->print();
	}
	if (_anker->getRight()) {
		if (_anker->getRight()->getRed())
			_anker->getRight()->print();
	}
	printLevel(_anker->getLeft());
	printLevel(_anker->getRight());
}

void Tree::printLevelOrder() {
	std::cout << "Ausgabe in LevelOrder als Binaer Baum" << std::endl;
	printerHeader();
	printLevel(m_anker);
	std::cout << "-----+-------------+-----+----------+----------+--------+" << std::endl;
	std::cout << "Ausgabe in LevelOrder als 234-Tree: " << std::endl;
	print234Tree();
	height();
}

void Tree::printLevelOrder(int niveau) {
	print234Tree(niveau);
}

void Tree::print234Tree() {
	if (!m_anker)
		return;
	int niv = 0;
	std::queue<int> nivQ;
	std::queue<TreeNode*> nodeQ;
	nodeQ.push(m_anker);
	nivQ.push(niv);

	std::cout << "Niveau " << niv << ":";

	TreeNode* ptr;
	int nivOut;
	while (!nodeQ.empty()) {
		ptr = nodeQ.front();
		nivOut = nivQ.front();
		nodeQ.pop();
		nivQ.pop();

		if (niv < nivOut) {
			std::cout << std::endl
				<< "Niveau " << nivOut << ":";
			niv++;
		}

		std::cout << " (";
		if (ptr->getLeft()) {
			TreeNode* left = ptr->getLeft();
			if (left->getRed()) {
				if (left->getLeft()) {
					nodeQ.push(left->getLeft());
					nivQ.push(left->depth() + 1);
				}
				if (left->getRight()) {
					nodeQ.push(left->getRight());
					nivQ.push(left->depth() + 1);
				}
				left->printOrderID();
			}
			else {
				nodeQ.push(left);
				nivQ.push(left->depth());
			}
		}

		ptr->printOrderID();

		if (ptr->getRight()) {
			TreeNode* right = ptr->getRight();
			if (right->getRed()) {
				if (right->getLeft()) {
					nodeQ.push(right->getLeft());
					nivQ.push(right->depth() + 1);
				}
				if (right->getRight()) {
					nodeQ.push(right->getRight());
					nivQ.push(right->depth() + 1);
				}
				right->printOrderID();
			}
			else {
				nodeQ.push(right);
				nivQ.push(right->depth());
			}
		}
		std::cout << ")";
	}
}

void Tree::print234Tree(int niveau) {
	if (!m_anker)
		return;
	int niv = 0;
	std::queue<int> nivQ;
	std::queue<TreeNode*> nodeQ;
	nodeQ.push(m_anker);
	nivQ.push(niv);

	TreeNode* ptr;
	int nivOut;
	while (!nodeQ.empty()) {
		ptr = nodeQ.front();
		nivOut = nivQ.front();
		nodeQ.pop();
		nivQ.pop();

		if (niveau + 1 == nivOut)
			return;

		if (niv < nivOut) {
			if (nivOut == niveau)
				std::cout << std::endl << "Niveau " << niveau << ":";
			niv++;
		}

		if (niv == niveau && niveau == 0)
			std::cout << std::endl << "Niveau " << niveau << ":";

		if (niv == niveau)
			std::cout << " (";

		if (ptr->getLeft()) {
			TreeNode* left = ptr->getLeft();
			if (left->getRed()) {
				if (left->getLeft()) {
					nodeQ.push(left->getLeft());
					nivQ.push(left->depth() + 1);
				}
				if (left->getRight()) {
					nodeQ.push(left->getRight());
					nivQ.push(left->depth() + 1);
				}
				if (niv == niveau)
					left->printOrderID();
			}
			else {
				nodeQ.push(left);
				nivQ.push(left->depth());
			}
		}

		if (niv == niveau)
			ptr->printOrderID();

		if (ptr->getRight()) {
			TreeNode* right = ptr->getRight();
			if (right->getRed()) {
				if (right->getLeft()) {
					nodeQ.push(right->getLeft());
					nivQ.push(right->depth() + 1);
				}
				if (right->getRight()) {
					nodeQ.push(right->getRight());
					nivQ.push(right->depth() + 1);
				}
				if (niv == niveau)
					right->printOrderID();
			}
			else {
				nodeQ.push(right);
				nivQ.push(right->depth());
			}
		}
		if (niv == niveau)
			std::cout << ")";
	}
	std::cout << std::endl << std::endl;
}

void Tree::printerHeader() {
	std::cout << std::endl;

	std::cout.width(5);
	std::cout << "ID"
		<< "|";
	std::cout.width(13);
	std::cout << "Name"
		<< "|";
	std::cout.width(5);
	std::cout << "Age"
		<< "|";
	std::cout.width(10);
	std::cout << "Income"
		<< "|";
	std::cout.width(10);
	std::cout << "PostCode"
		<< "|";
	std::cout.width(8);
	std::cout << "OrderID"
		<< "|" << std::endl;
	std::cout << "-----+-------------+-----+----------+----------+--------+" << std::endl;
}