#include "RN_arbre.h"
#include <vector>
#include "Noeud.h"

using namespace std;

const int BLACK = 0;
const int RED = 1;

vector<int>::iterator ptr;

RN_arbre::RN_arbre()
{
}

RN_arbre::RN_arbre(vector<int> tableau)
{
	this->nil = new Noeud(BLACK);
	this->root = new Noeud(BLACK);

	for (ptr = tableau.begin(); ptr < tableau.end(); ptr++) {
		arbre_inserer(tableau[*ptr]);
	}


}

RN_arbre::~RN_arbre()
{
}

void RN_arbre::affiche()
{
	cout << "Les noeuds de l'arbre sont: ";
}

void RN_arbre::arbre_inserer(int i) {
	Noeud* n = new Noeud(i, RED, 0, this->nil, this->nil, this->nil, this->nil, this->nil);

	Noeud* tempNil = new Noeud(0, BLACK, 0, this->nil, this->nil, this->nil, this->nil, this->nil);
	tempNil = this->nil;
	Noeud* tempRoot = new Noeud(0, RED, 0, this->nil, this->nil, this->nil, this->nil, this->nil);
	tempRoot = this->root;
	while (tempRoot != this->nil) { //x part de la racine et descend jusqu'à nil
		tempNil = tempRoot;
		if (n->getKey() < tempRoot->getKey()) {
			tempRoot = tempRoot->getEnfantGauche();
		}
		else {
			tempRoot = tempRoot->getEnfantDroit();
		}
	}
	n->setParent(tempNil);
	if (tempNil == this->nil){ // Arbre est vide (n est la racine)
		this->root = n;
	}
	else if (n->getKey() < tempNil->getKey()) { // Si la clé de n est plus petite que celle de son noeud parent
		tempNil->setEnfantGauche(n);
	}
	else { // Si la clé de n est plus petite que celle de son noeud parent
		tempNil->setEnfantDroit(n);
	}
	n->setEnfantGauche(this->nil);
	n->setEnfantDroit(this->nil);
	n->setCouleur(RED);
	inserer_correction_rn(this->root);
}

void RN_arbre::inserer_correction_rn(Noeud* n) {
	Noeud* y = this->nil;
	while (n->getParent()->getCouleur() == RED) {
		if (n->getParent() == n->getParent()->getParent()->getEnfantGauche()) {
			y = n->getParent()->getParent()->getEnfantDroit();
			if (y->getCouleur() == RED) {
				n->getParent()->setCouleur(BLACK);
				y->setCouleur(BLACK);
				n->getParent()->getParent()->setCouleur(RED);
				n = n->getParent()->getParent();
			}
			else if (n == n->getParent()->getEnfantDroit()) {
				n = n->getParent();
				//left rotate
				n->getParent()->setCouleur(BLACK);
				n->getParent()->getParent()->setCouleur(RED);
				//right rotate
			}
		}
		else {
				//
				y = n->getParent()->getParent()->getEnfantGauche();
				if (y->getCouleur() == RED) {
					n->getParent()->setCouleur(BLACK);
					y->setCouleur(BLACK);
					n->getParent()->getParent()->setCouleur(RED);
					n = n->getParent()->getParent();
				}
				else if (n == n->getParent()->getEnfantGauche()) {
					n = n->getParent();
					//right rotate
					n->getParent()->setCouleur(BLACK);
					n->getParent()->getParent()->setCouleur(RED);
					//left rotate
				}
		}
	}

	this->root->setCouleur(BLACK);
}

/*int RN_arbre::lire_rang(int x) {

}*/