#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;



//---------------------------------------------------------------------------------
// Definition du struct machine et donnees statiques
//---------------------------------------------------------------------------------



struct machine{
  int cle; //cle de la machine
  int debut_resp; //cle de la premiere donnee dont la machine est responsable
  int fin_resp; //cle de la derniere donnee dont la machine est responsable (=cle)
  vector<machine*> voisin_sort;//pointeurs sur les voisins sortants tries par distance croissante
  vector<machine*> voisin_entr;//pointeurs sur les voisins entrants tries par distance croissante
};



int n=10; // nombre de cles possibles: 2^n: de 0 a 2^n-1.
machine* point_d_entree; //pointant vers une machine du reseau (point d'entree sur le reseau)
int nbre_machine; //nbre de machines connectees (doit etre >= 2)



//---------------------------------------------------------------------------------
// Quelques fonctions utiles
//---------------------------------------------------------------------------------



int Puiss(int x, int k){ //Retourne x a la puissance k
  if(k==0){return 1;}
  else{return x*Puiss(x,k-1);}
}




void Affiche_machine( struct machine mach_a_afficher){ //Affiche sur le terminal la machine concernee

  cout <<"\t Cle: "<< mach_a_afficher.cle <<endl;
  cout <<"\t Cle de la premiere donnee sous responsabilite: "<< mach_a_afficher.debut_resp <<endl;
  cout <<"\t Cle de la derniere donnee sous responsabilite: "<< mach_a_afficher.fin_resp <<endl;
  cout <<"\t Cles des voisins sortrants:" << endl << "\t \t";
  for(int j=0;j<(mach_a_afficher.voisin_sort).size();j++){
    cout << mach_a_afficher.voisin_sort[j]->cle << " ";
  }
  cout << endl;
  cout <<"\t Cles des voisins entrants:" << endl << "\t \t";
  for(int j=0;j<(mach_a_afficher.voisin_entr).size();j++){
    cout << mach_a_afficher.voisin_entr[j]->cle << " ";
  }
  cout << endl;
  cout<<endl;

}





void Affiche_reseau(){ //Affiche sur le terminal la structure du reseau

  int cle_depart=point_d_entree->cle; //cle de la machine qui sert de point d'entree
  struct machine machine_courante=*point_d_entree; // machine courante dans la procedure d'affichage
                                                   //au depart, cette machine est la point d'entree
  int cpt=1;//compteur de machines affichees



  cout << endl;
  cout << "---------------------------------------------------------------" << endl <<
    "Affichage du reseau Chord:" << endl <<
    "---------------------------------------------------------------" << endl;   


  do{cout << "Machine n. " << cpt << " :" <<endl;
  Affiche_machine(machine_courante);
  machine_courante=*(machine_courante.voisin_sort[0]);
  cpt++;

 }
   while(machine_courante.cle != cle_depart);

   cout <<  "---------------------------------------------------------------" << endl;
   cout << endl;
}



//---------------------------------------------------------------------------------
// Initialisation du reseau
//---------------------------------------------------------------------------------



void init(){

  //Initialise le reseau avec 2 machines, une a la cle 0 et une a la cle 512


  struct machine * machine1= new machine; //
  struct machine * machine2= new machine; //
  struct machine * machine3= new machine; //
  struct machine * machine4= new machine; //

  machine1->cle=0;
  machine2->cle=Puiss(2,n-2);
  machine3->cle=Puiss(2,n-1);
  machine4->cle=Puiss(2,n-2)+Puiss(2,n-1);

  machine1->debut_resp=machine4->cle+1;
  machine1->fin_resp=machine1->cle;

  machine2->debut_resp=machine1->cle+1;
  machine2->fin_resp=machine2->cle;

  machine3->debut_resp=machine2->cle+1;
  machine3->fin_resp=machine3->cle;

  machine4->debut_resp=machine3->cle+1;
  machine4->fin_resp=machine4->cle;

  machine1->voisin_sort.push_back(machine2);
  machine1->voisin_sort.push_back(machine3);
  machine1->voisin_entr.push_back(machine3);
  machine1->voisin_entr.push_back(machine4);

  machine2->voisin_sort.push_back(machine3);
  machine2->voisin_sort.push_back(machine4);
  machine2->voisin_entr.push_back(machine4);
  machine2->voisin_entr.push_back(machine1);

  machine3->voisin_sort.push_back(machine4);
  machine3->voisin_sort.push_back(machine1); 
  machine3->voisin_entr.push_back(machine1);
  machine3->voisin_entr.push_back(machine2);
 
  machine4->voisin_sort.push_back(machine1);
  machine4->voisin_sort.push_back(machine2);
  machine4->voisin_entr.push_back(machine2);
  machine4->voisin_entr.push_back(machine3);

  point_d_entree=machine1;
  nbre_machine=4;

}



//---------------------------------------------------------------------------------
// Recherche de la machine responsable d'une donnee
//---------------------------------------------------------------------------------

bool Localise(int cle, int deb, int fin){

  //Retourne vrai ssi cle est entre deb et fin (au sens large) dans l'ordre circulaire a 2^n elements.

  if((deb<=cle) && (cle<=fin)){return true;}
  if((deb>fin) && ( (deb<=cle) || (cle<=fin))){return true;}
  return false;
}




machine* Recherche_responsable(int valeur_cle, struct machine *mach_dep){

  //Retourne un pointeur sur la machine qui est responsable de la cle valeur_cle

  //Cas ou le premier voisin est le responsable:
  if(Localise(valeur_cle, mach_dep->voisin_sort[0]->debut_resp, mach_dep->voisin_sort[0]->fin_resp)){
    return mach_dep->voisin_sort[0];} 

  //On trouve le voisin de plus grande cle etant place avant valeur_cle et on poursuit la recherche
  for(int i=0;i<mach_dep->voisin_sort.size()-1;i++){
    if(Localise(valeur_cle,((mach_dep->voisin_sort[i]->fin_resp)+1)%Puiss(2,n),
		mach_dep->voisin_sort[i+1]->fin_resp)){
      return Recherche_responsable(valeur_cle, mach_dep->voisin_sort[i]);}
  }

  //Cas ou la cle est apres le dernier voisin sortant, on lui poursuit la recherche a partir de celui-ci
  return Recherche_responsable(valeur_cle, mach_dep->voisin_sort.back() );

}


//---------------------------------------------------------------------------------
// Ajout d'une machine
//---------------------------------------------------------------------------------


void Ajout_machine(int valeur_cle){

  //Ajoute une machine de cle valeur_cle


  //Responsable de la cle ou la nouvelle machine sera inseree
  struct machine *ancienne=Recherche_responsable(valeur_cle,point_d_entree);

  //Creation de la nouvelle machine
  struct machine * nouvelle = new machine; 

  //cle et zone de responsabilite de la nouvelle machine
  nouvelle->cle=valeur_cle;
  nouvelle->debut_resp=ancienne->debut_resp;
  nouvelle->fin_resp=valeur_cle;

  //Mise a jour du debut de la zone de responsabilite de l'ancienne machine
  ancienne->debut_resp=((valeur_cle + 1)%Puiss(2,n));



  //Voisins sortant de la nouvelle machine

  nouvelle->voisin_sort.push_back(ancienne);
  //On met l'ancienne d'abord

  struct machine* voisin;
 
  for(int i=1;i<n;i++){
    voisin=Recherche_responsable((nouvelle->cle+Puiss(2,i))%Puiss(2,n),point_d_entree);
    if(voisin!=nouvelle->voisin_sort.back()){
      nouvelle->voisin_sort.push_back(voisin);

      //On met a jour voisin.voisin_entr:

      int k=0; //l'indice de ancienne dans voisin.voisin_entr
      while(voisin->voisin_entr[k]!=ancienne){
	k++;}
      //On stocke le dernier element de voisin.voisin_entr:
      struct machine* temp=voisin->voisin_entr[voisin->voisin_entr.size()-1];
      //On decale la liste:
      for(int l=voisin->voisin_entr.size()-1;l>k;l--){
	voisin->voisin_entr[l]=voisin->voisin_entr[l-1];
      }
      //On re-empile le dernier element:
      voisin->voisin_entr.push_back(temp);
      //On insere nouvelle a sa place:
      voisin->voisin_entr[k]=nouvelle;
    }
  }

  //Mise a jour des 2 listes de voisins entrants:

  //Copie des voisins entrants de l'ancienne machine dans copie_voisin_entrant
  vector<machine*> copie_voisin_entrant;
  int nb_voisins_entrants;

  for(int i=0;i<ancienne->voisin_entr.size();i++){
    copie_voisin_entrant.push_back(ancienne->voisin_entr[i]);
  }
  nb_voisins_entrants=ancienne->voisin_entr.size();

  //Effacement des voisins entrants de l'ancienne machine

  for(int i=0;i<nb_voisins_entrants;i++){
    ancienne->voisin_entr.pop_back();
  }

  //Pour chaque ancien voisin entrant de 'ancienne', on decide si son voisin sortant 
  //est 'ancienne' ou nouvelle ou les deux.

  for(int i=0;i<nb_voisins_entrants;i++){ //On traite la machine copie_voisin_entrant[i]

    //On regarde laquelle des deux machines est voisin sortant de copie_voisin_entrant[i]
    bool flag_nouvelle=false;
    bool flag_ancienne=false;

    for(int j=0;j<n;j++){

      if(Localise((copie_voisin_entrant[i]->cle+Puiss(2,j))%Puiss(2,n),nouvelle->debut_resp,nouvelle->fin_resp)){
	flag_nouvelle=true;}

      if(Localise((copie_voisin_entrant[i]->cle+Puiss(2,j))%Puiss(2,n),ancienne->debut_resp,ancienne->fin_resp)){
	flag_ancienne=true;}
    }


    //cas1: seule l'ancienne est voisin sortant de copie_voisin_entrant[i]

    if((!flag_nouvelle) && flag_ancienne){
      ancienne->voisin_entr.push_back(copie_voisin_entrant[i]);
    }

    //cas2: seule la nouvelle est voisin sortant de copie_voisin_entrant[i]

    if(flag_nouvelle && (!flag_ancienne)){
      nouvelle->voisin_entr.push_back(copie_voisin_entrant[i]);
      //On change la liste de voisins sortant de copie_voisin_entrant[i]
      for(int k=0; k<copie_voisin_entrant[i]->voisin_sort.size();k++){
	if(copie_voisin_entrant[i]->voisin_sort[k]==ancienne){
	  copie_voisin_entrant[i]->voisin_sort[k]=nouvelle;}
      }
    }

    //cas3: nouvelle et ancienne sont voisins sortants de copie_voisin_entrant[i]
 
   if(flag_nouvelle && flag_ancienne){
      nouvelle->voisin_entr.push_back(copie_voisin_entrant[i]);
      ancienne->voisin_entr.push_back(copie_voisin_entrant[i]);
      //On change la liste de voisins sortant de copie_voisin_entrant[i]
      int k=0; //l'indice de ancienne dans copie_voisin_entrant[i]->voisin_sort
      while(copie_voisin_entrant[i]->voisin_sort[k]!=ancienne){
	k++;}
      //On stocke le dernier element de copie_voisin_entrant[i]->voisin_sort:
      struct machine* temp=copie_voisin_entrant[i]->voisin_sort[copie_voisin_entrant[i]->voisin_sort.size()-1];
      //On decale la liste:
      for(int l=copie_voisin_entrant[i]->voisin_sort.size()-1;l>k;l--){
	copie_voisin_entrant[i]->voisin_sort[l]=copie_voisin_entrant[i]->voisin_sort[l-1];
      }
      //On re-empile le dernier element:
      copie_voisin_entrant[i]->voisin_sort.push_back(temp);
      //On insere nouvelle a sa place:
      copie_voisin_entrant[i]->voisin_sort[k]=nouvelle;
    }
  }
  

  //nouvelle est voisin entrant d'ancienne:
  ancienne->voisin_entr.push_back(nouvelle);


  nbre_machine++;
}



//---------------------------------------------------------------------------------
// Retrait d'une machine
//---------------------------------------------------------------------------------


void Retrait_machine(int valeur_cle){

  //Retire la machine responsable de la cle valeur_cle



  //
  //
  // A COMPLETER
  //
  //



}



//---------------------------------------------------------------------------------
// Affichage d'une interface
//---------------------------------------------------------------------------------

void Interface(){

  //Interface rudimentaire avec le reseau


  int choix=1;

  cout << endl;
  cout << "---------------------------------------------------------------" << endl <<
    "  Simulation du reseau Chord:" << endl <<
    "---------------------------------------------------------------" << endl;   

  while(choix!=0){
    cout << endl;
    cout<< "Choisissez :"<< endl;
    cout << "\t 1- Affichage des machines du reseau."<<endl;
    cout << "\t 2- Rechercher la machine responsable d'une cle."<<endl;
    cout << "\t 3- Insertion d'une machine dans le reseau."<<endl;
    cout << "\t 4- Suppression d'une machine du reseau."<<endl; 
    cout << "\t 0- Quitter" << endl;
    cout << endl;
    cout << "Choix: ";
    cin >> choix;
  
    if(choix==1){
      Affiche_reseau();
    }
    if(choix==2){
      int valeur_cle;
      cout << endl;
      cout << "Valeur de la cle dont on cherche la machine responsable: ";
      cin >> valeur_cle; 
      if((valeur_cle <0) || (Puiss(2,n)-1< valeur_cle)){ cout << "Cle erronee" << endl;}
      else{
	cout << "Machine responsable de la cle " << valeur_cle << ":" << endl;
	Affiche_machine(*Recherche_responsable(valeur_cle, point_d_entree));
      }
      cout <<  "---------------------------------------------------------------" << endl;     
    }
    if(choix==3){
    int valeur_cle;
      cout << endl;
      cout << "Valeur de la cle de la machine que l'on souhaite ajouter: ";
      cin >> valeur_cle; 
      if((valeur_cle <0) || (Puiss(2,n)-1< valeur_cle)){ cout << "Cle erronee" << endl;}
      else{if(Recherche_responsable(valeur_cle,point_d_entree)->cle==valeur_cle){
	cout << "Machine deja presente sur le reseau !" << endl;}
      else{
	Ajout_machine(valeur_cle);
      }
      }
    }
    if(choix==4){
      int valeur_cle;
      cout << endl;
      cout << "Valeur d'une cle dont la machine que l'on souhaite retirer est responsable: ";
      cin >> valeur_cle; 
      Retrait_machine(valeur_cle);
    } 

  }
}


//---------------------------------------------------------------------------------
// Programme principal
//---------------------------------------------------------------------------------



int main(){
  init();
  Interface();
}