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

using namespace std;



//---------------------------------------------------------------------------------
// Definition du srtuct 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-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 4 machines, ayant les cles 0, 2^(n-2), 2^(n-1) et 2^(n-1)+2^(n-2)


  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=Puiss(2,n-2)+Puiss(2,n-1)+1;
  machine1->fin_resp=machine1->cle;

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

  machine3->debut_resp=Puiss(2,n-2)+1;
  machine3->fin_resp=machine3->cle;

  machine4->debut_resp=Puiss(2,n-1)+1;
  machine4->fin_resp=machine4->cle;

  machine1->voisin_sort.push_back(machine2);
  machine1->voisin_sort.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(machine3);
  machine2->voisin_entr.push_back(machine1);

  machine3->voisin_sort.push_back(machine4);
  machine3->voisin_sort.push_back(machine2); 
  machine3->voisin_entr.push_back(machine4);
  machine3->voisin_entr.push_back(machine1);
  machine3->voisin_entr.push_back(machine2);
 
  machine4->voisin_sort.push_back(machine1);
  machine4->voisin_sort.push_back(machine3);
  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-1 elements.


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


}




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

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


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


}


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


void Ajout_machine(int valeur_cle){

  //Ajoute une machine de cle valeur_cle



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




 
}


//---------------------------------------------------------------------------------
// 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)-2< 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)-2< valeur_cle)){ cout << "Cle erronee" << 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();
}