#include<iostream>
#include <stdlib.h>
#include <math.h>
#include "ARN.h"

using namespace std;

//Constructeurs**********************************//

ARN::ARN(bool (*EgaleCleUSER)(int cle1,int cle2), bool (*InferieurCleUSER)(int cle1,int cle2)){
  //creer un arn vide et on fixe les operateurs de comparaison

  nul=new noeud;
  nul->pere=NULL;
  nul->fd=NULL;
  nul->fg=NULL;
  nul->cle=-1;
  nul->coul=noir;

  racine=nul;

  EgaleCle=EgaleCleUSER;
  InferieurCle=InferieurCleUSER;
}


ARN::ARN(int val, bool (*EgaleCleUSER)(int cle1,int cle2), bool (*InferieurCleUSER)(int cle1,int cle2)){
  //creer un arn avec une racine et on fixe les operateurs de comparaison

  nul=new noeud;
  nul->pere=NULL;
  nul->fd=NULL;
  nul->fg=NULL;
  nul->cle=-1;
  nul->coul=noir;

  racine= new noeud;
  racine->pere=nul;
  racine->fd=nul;
  racine->fg=nul;
  racine->cle=val;
  racine->coul=noir;

  EgaleCle=EgaleCleUSER;
  InferieurCle=InferieurCleUSER;

}

//Destructeur************************************//

ARN::~ARN(){
  noeud* courant = racine;
  if(racine!=nul){
    while(racine->fg!=nul && racine->fd!=nul){// Tant qu'il ne reste plus que la racine
      
      while(courant->fg!=nul && courant->fd!=nul){ //On descend dans l'arbre
	if(courant->fg!=nul){
	  courant=courant->fg;}
	if(courant->fd!=nul){
	  courant=courant->fd;}
      }
      

      if(courant==courant->pere->fg){// Le noeud courant est fils gauche de son pere
	courant=courant->pere;//On remonte d'un cran
	delete courant->fg; //On efface le fils gauche
	courant->fg=nul;}
      else{ //Le noeud courant est fils droit de son pere
	courant=courant->pere;//On remonte d'un cran
	delete courant->fd; //On efface le fils droit
	courant->fd=nul;}
    }
    
    delete racine;
    delete nul;
  
  }
}

//I.O.*******************************************//

void ARN::afficheNoeud(noeud *courant, int profondeur){//Appel reccursif, la profondeur indique l'indentation necessaire.
  if(courant->fg!=nul){ 
    for(int i=0;i<profondeur;i++){
      cout << '|';
    }
    cout << "-> Fils gauche de cle = " << courant->fg->cle << " et de couleur ";
    ( courant->fg->coul == noir ) ? cout << "noir" : cout << "rouge";  
    cout << " :"<<endl;
    afficheNoeud(courant->fg,profondeur+1);
  }
  if(courant->fd!=nul){ 
    for(int i=0;i<profondeur;i++){
      cout << '|';
    }
    cout << "-> Fils droit de cle = " << courant->fd->cle <<  " et de couleur ";
    ( courant->fd->coul == noir ) ? cout << "noir" : cout << "rouge";  
    cout << " :"<<endl;
    afficheNoeud(courant->fd,profondeur+1);
  }
}

void ARN::Affichage(){ //Affichage ecran avec indentation, on affiche reccursivement.

  if(racine!=nul){
    cout<< endl;
    cout<< "Racine de cle = " << racine->cle << " et de couleur ";
    ( racine->coul == noir ) ? cout << "noir" : cout << "rouge";  
    cout << " :"<<endl;
    afficheNoeud(racine,1);
    cout << endl;
  }
  else{
    cout << "Arn vide." << endl;
  }
}


//Chercher un noeud*******************************//


noeud* ARN::chercheNoeud(int val, noeud* courant){


  if((*EgaleCle)(val,courant->cle)){
    return courant;}
  if((*InferieurCle)(courant->cle,val)){
    if(courant->fd!=nul){
      return chercheNoeud(val,courant->fd);}
    else{
      return courant;}
  }  
  else{
    if(courant->fg!=nul){
      return chercheNoeud(val,courant->fg);}
    else{
      return courant;}
  }
}

noeud* ARN::Trouve(int val){//Cherche le noeud correspondant reccursivement
  //Si la valeur n'est pas presente, retourne un noeud ou val est inserable
  //comme fils droit ou gauche
  if(racine!=nul){
    return chercheNoeud(val, racine);
  }
  else{
    return nul;
  }
}


noeud* ARN::successeur(noeud* x){//Trouve le successeur de x sous reserve que x soit non nul
  if(x->fd!=nul){//Si x a un successeur droit, on prend le min de la sous arbo droite
    x=x->fd;
    while(x->fg!=nul){
      x=x->fg;}
    return x;
  }
  while(x->pere!=nul && x==x->pere->fd){//Sinon, on retourne le premier ancetre dont x descend a gauche
    x=x->pere;
  }
  return x->pere;//Au pire, si x est la racine, l'element de depart etait le plus grand et on retourne nul
}


noeud* ARN::predecesseur(noeud* x){//Trouve le predecesseur de x sous reserve que x soit non nul
  if(x->fg!=nul){//Si x a un successeur gauche, on prend le max de la sous arbo gauche
    x=x->fg;
    while(x->fd!=nul){
      x=x->fd;}
    return x;
  }
  while(x->pere!=nul && x==x->pere->fg){//Sinon, on retourne le premier ancetre dont x descend a droite
    x=x->pere;
  }
  return x->pere;//Au pire, si x est la racine, l'element de depart etait le plus grand et on retourne nul
}





//Inserer un noeud********************************//

void ARN::RotationGauche(noeud* x){//pivote x et son fils droit y sous l'hypothese que celui-ci soit non null

  noeud* y=x->fd;

  x->fd=y->fg; //Le fils gauche de y devient fils droit de x
  if(y->fg!=nul){
    y->fg->pere=x;
  }

  y->pere=x->pere;//On met a jour pere dans y
  if(x->pere==nul){//Cas ou x est racine
    racine=y;}
  else{//Sinon on met a jour le nouveau pere de y
    if(x==x->pere->fg){
      x->pere->fg=y;}
    else{x->pere->fd=y;}
  }
  
  y->fg=x;//Nouveau lien entre x et y
  x->pere=y;
}


void ARN::RotationDroite(noeud* x){//pivote x et son fils gauche y sous l'hypothese que celui-ci soit non null

  noeud* y=x->fg;

  x->fg=y->fd; //Le fils droit de y devient fils gauche de x
  if(y->fd!=nul){
    y->fd->pere=x;
  }

  y->pere=x->pere;//On met a jour pere dans y
  if(x->pere==nul){//Cas ou x est racine
    racine=y;}
  else{//Sinon on met a jour le nouveau pere de y
    if(x==x->pere->fg){
      x->pere->fg=y;}
    else{x->pere->fd=y;}
  }
 
  y->fd=x;//Nouveau lien entre x et y
  x->pere=y;
}


noeud* ARN::insertionClassique(int val){
  //Insere comme dans un arbre de recherche classique
 
  noeud* point_insertion=Trouve(val);
  if((*EgaleCle)(point_insertion->cle,val)){
    cout << "Valeur deja existante..."<<endl;
    return nul;}
  else{
    noeud *nouveau= new noeud;
    nouveau->pere=point_insertion;
    if((*InferieurCle)(point_insertion->cle,val)){
      point_insertion->fd=nouveau;}
    else{
      point_insertion->fg=nouveau;
    }
    nouveau->fd=nul;
    nouveau->fg=nul;
    nouveau->cle=val;
    nouveau->coul=rouge;
    return nouveau;
  }

}

void ARN::Insere(int val){
  //On insere un noeud de cle val et reequilibre l'arbre.

  if(racine!=nul){
    noeud *x=insertionClassique(val); //x est insere comme feuille rouge


    if(x!=nul){//Si le noeud n'existait pas deja, on reequilibre l'arbre

      while(x->pere!=nul && x->pere->coul==rouge && x->pere->pere!=nul){ //Tant que le pere existe, est rouge, et que le grand-pere existe:
	if(x->pere==x->pere->pere->fg){//Si le pere de x est un fils gauche


	  noeud *y=x->pere->pere->fd;// y est l'oncle de x
	  if(y!=nul && y->coul==rouge){ //x, son pere et son oncle sont rouges, on met son grand-pere a rouge et on remonte dans l'arbre
	    x->pere->coul=noir;
	    y->coul=noir;
	    x->pere->pere->coul=rouge;
	    x=x->pere->pere;
	  }
	  else{//l'oncle de x est noir ou n'existe pas
	    if(x==x->pere->fd){//Si x est fils droit
	      x=x->pere;
	      this->RotationGauche(x); //Maintenant, le noeud considere est fils gauche
	    }
	    x->pere->coul=noir;//On met le pere a noir, le grand-pere a rouge et on effectue une rot. droite sur le grand-pere, et c'est bon (le 
	    //nouvel ancetre est le pere qui est noir).
	    x->pere->pere->coul=rouge;
	    this->RotationDroite(x->pere->pere);
	  }
	}


	else{ // Si le pere de x est un fils droit (on fait de meme)

	
	  noeud *y=x->pere->pere->fg;// y est l'oncle de x
	  if(y!=nul && y->coul==rouge){ //x, son pere et son oncle sont rouges, on met son grand-pere a rouge et on remonte dans l'arbre
	    x->pere->coul=noir;
	    y->coul=noir;
	    x->pere->pere->coul=rouge;
	    x=x->pere->pere;
	  }
	  else{//l'oncle de x est noir ou n'existe pas
	    if(x==x->pere->fg){//Si x est fils gauche
	      x=x->pere;
	      this->RotationDroite(x); //Maintenant, le noeud considere est fils droit
	    }
	    x->pere->coul=noir;//On met le pere a noir, le grand-pere a rouge et on effectue une rot. gauche sur le grand-pere, et c'est bon (le 
	    //nouvel ancetre est le pere qui est noir).
	    x->pere->pere->coul=rouge;
	    this->RotationGauche(x->pere->pere);
	  }
	}
      }
      racine->coul=noir; //on s'est peut etre arrete avec un fils de la racine rouge.
    }
  }
  else{
    racine= new noeud;
    racine->pere=nul;
    racine->fd=nul;
    racine->fg=nul;
    racine->cle=val;
    racine->coul=noir;
  }
}
  
//Supprimer un noeud *****************************//


void ARN::SupprimerCorrection(noeud* x){
  while(x!=racine && x->coul==noir){//x a un pere et sa couleur est noire

    if(x->pere->fg==x){//x est fils gauche
      noeud* w=x->pere->fd;//Le frere de x, non nul car le nbre de noirs
                           //sous w est > celui sous x

      if(w->coul==rouge){//cas 1, on se ramene a un w noir
	w->coul=noir;
	x->pere->coul=rouge;
	RotationGauche(x->pere);
	w=x->pere->fd;}

      if(w->fg->coul==noir && w->fd->coul==noir){//pour les ms raisons w a 2 fils
	w->coul=rouge; //cas 2
	x=x->pere;}//on remonte d'un cran, si x est rouge on arete la boucle et on le mettra noir
      else{//Au moins un des 2 fils de w est rouge
	if(w->fd->coul==noir){//cas 3, on se ramene a un fils droit rouge
	  w->fg->coul=noir;
	  w->coul=rouge;
	  RotationDroite(w);
	  w=x->pere->fd;}

	w->coul=x->pere->coul;//Cas 4, le fils droit de w est rouge
	x->pere->coul=noir;//on reequilibre la branche deficiente
	w->fd->coul=noir;
	RotationGauche(x->pere);
	x=racine;//on remet la racine a noir
      }
    }else{//x est fils droit
      noeud* w=x->pere->fg;//Le frere de x, non nul car le nbre de noirs
                           //sous w est > celui sous x

      if(w->coul==rouge){//cas 1, on se ramene a un w noir
	w->coul=noir;
	x->pere->coul=rouge;
	RotationDroite(x->pere);
	w=x->pere->fg;}

      if(w->fg->coul==noir && w->fd->coul==noir){//pour les ms raisons w a 2 fils
	w->coul=rouge; //cas 2
	x=x->pere;}//on remonte d'un cran, si x est rouge on arete la boucle et on le mettra noir
      else{//Au moins un des 2 fils de w est rouge
	if(w->fg->coul==noir){//cas 3, on se ramene a un fils gauche rouge
	  w->fd->coul=noir;
	  w->coul=rouge;
	  RotationGauche(w);
	  w=x->pere->fg;}

	w->coul=x->pere->coul;//Cas 4, le fils gauche de w est rouge
	x->pere->coul=noir;//on reequilibre la branche deficiente
	w->fg->coul=noir;
	RotationDroite(x->pere);
	x=racine;//on remet la racine a noir
      }


    }
  }
  x->coul=noir;
}


void ARN::Supprime(int val){
 
  noeud*z = Trouve(val);
  if(!(*EgaleCle)(z->cle,val)){
    return;
  }

  noeud* y; //Un noeud qu'on va detacher de l'arbre
  if(z->fg==nul || z->fd==nul){
    y=z;}
  else{y=successeur(z);}//Normalement, ici, z n'est pas le max, car sinon il lui manque un fils.
  //On est sur que y n'est pas nul

  noeud* x=nul; //x prend la valeur du fils de y non null (si il existe)

  if(y->fg!=nul){
    x=y->fg;}
  else{x=y->fd;}

  x->pere=y->pere;//On mets a jour le pere dans x, marche meme si x=nul

  if(y->pere==nul)//Si y etait racine
    {if(x==nul){//c'est le cas ou il n'y a plus qu'un seul sommet dans l'arn
      delete z;
      racine=nul;
      return;
    }else{//La nouvelle racine est le fils de y
      racine=x;}
    }else{//Si y n'etait pas racine
      if(y==y->pere->fg){//le pere de y devient le pere de x
	y->pere->fg=x;}
      else{
	y->pere->fd=x;
      }
    }
  if(y!=z){//si le noeud supprime n'est pas z
    z->cle=y->cle;
  }
  if(y->coul==noir){//On a supprimer un sommet noir, les hauteurs noires ont changees, il faut reequilibrer
    SupprimerCorrection(x);
     }
  delete y;
}


//Predecesseur et Successeur*************************************//
//Retournent -1 comme cle si min (pour Predecesseur) ou max (pour
// Successeur)


int ARN::Successeur(int val){
  noeud* x=successeur(Trouve(val));
  if(x==nul){return -1;}
  else{
    return x->cle;
  }
}


int ARN::Predecesseur(int val){
  noeud* x=predecesseur(Trouve(val));
  if(x==nul){return -1;}
  else{
    return x->cle;
  }  

}