#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream.h>

// prototypes des fonctions
void   Exo_Enfance(int n,int k);
void   Exo_Cartes(void);

// le main
int    main(int argc,char* argv[])
{
  int n;
  int k;

  cout << "Amstramgram\n";
  cout << "taille de la ronde ? ";
  cin >> n;
  cout << "duree de la comptine ? ";
  cin >> k;
  Exo_Enfance(n,k);
  cout << "\n\n\n";

  cout << "Cartes\n";
  Exo_Cartes();
  cout << "\n\n\n";
}

// exo 1
// la liste circulaire est simplement chainee
typedef struct gosse {
  int     numero;
  gosse*  suiv;
} gosse;

// insere un numero (ie un gosse) dans une liste cirulaire
// renvoie la liste circulaire commencant par celui qui vient d'etre ajoute
gosse*   Insere(gosse* ronde,int n)
{
  gosse*  nouv=new gosse;
  nouv->numero=n;
  nouv->suiv=NULL; // pour l'intant
  if ( ronde == NULL ) {
    nouv->suiv=nouv; // on fait une boucle = liste circulaire de taille 1
    return nouv;
  }
  // le nouveau est insere devant celui qui est indique
  nouv->suiv=ronde;
  gosse*  dernier=ronde;
  while ( dernier->suiv != ronde ) dernier=dernier->suiv;
  dernier->suiv=nouv;
  return nouv;
}

// parcourt x gosses sur une ronde (=fait x sauts d'un gosse au suivant)
gosse* Parcourt(gosse* ronde,int x)
{
  if ( ronde == NULL ) return NULL;
  for (int i=0;i<x;i++) ronde=ronde->suiv;
  return ronde;
}
// fait un tour de amstramgram
// renvoie le gosse qui se fait virer
// et fait pointer ronde sur le gosse duquel on part au tour suivant
gosse* Joue(gosse* &ronde,int k)
{
  if ( k <= 0 ) {
    cout << "pas sense arriver\n";
    return NULL;
  }
  // on parcourt la ronde k-1 fois pour avoir le gosse qui precede celui qui vire
  gosse* dernier=Parcourt(ronde,k-1);
  // le gosse vire est le suivant
  gosse* vire=dernier->suiv;
  // il faut maintenant enlever vire de la ronde
  if ( dernier == vire ) {
    // c'etait en fait une ronde de taille 1
    ronde=NULL;
    vire->suiv=NULL;
  } else {
    dernier->suiv=vire->suiv;
    vire->suiv=NULL;
    // on repart de celui qui suit celui qui se fait virer
    ronde=dernier->suiv;
  }
  return vire;
}
void   Exo_Enfance(int n,int k)
{
  // creation de la ronde: on insere les gosses les uns apres les autres
  gosse* ronde=NULL; // liste vide pour commencer
  for (int i=0;i<n;i++) ronde=Insere(ronde,i);
  // on en tire un au hasard
  int   no=random()%n;
  // et on se deplace dessus
  ronde=Parcourt(ronde,no);

  cout << "on elimine: ";
  while ( ronde && ronde->suiv != ronde ) {
    gosse* elimine=Joue(ronde,k);
    cout << elimine->numero << " ";
    delete elimine;
  }
  cout << endl;
  if ( ronde ) {
    cout << "gagnant= " << ronde->numero;
    delete ronde;
  }
}


// exo 2

typedef struct carte {
  int     numero;
  int     couleur;
  carte*  suiv;
} carte;
// affichage d'une (et une seule) carte
void   CarteAffiche(carte *c)
{
  if ( c == NULL ) return;
  cout << "(" << c->numero << " de ";
  switch ( c->couleur ) {
  case 0:
    cout << "pique)";
    break;
  case 1:
    cout << "coeur)";
    break;
  case 2:
    cout << "carreau)";
    break;
  case 3:
    cout << "trefle)";
    break;
  default:
    cout << "rien)";
    break;
  }
}
//insertion au debut
carte* CarteInsere(carte* paquet,int no,int coul)
{
  carte*  nouv=new carte;
  nouv->numero=no;
  nouv->couleur=coul;
  // et on la met au debut
  nouv->suiv=paquet;
  return nouv;
}
// initialisation d'un paquet trie
carte*   CarteInitialise(void)
{
  // on les insere au debut=> il faut les insere a partir de la derniere valeur
  carte* paquet=NULL; // on commence avec un paquet vide
  for (int coul=3;coul>=0;coul--) {
    for (int val=7;val>=0;val--) {
      paquet=CarteInsere(paquet,val,coul);
    }
  }
  return paquet;
}
// afficher un paquet (=afficher une liste...)
void   PaquetAffiche(carte* paquet)
{
  cout << "paquet: ";
  while ( paquet ) {
    // on affiche la carte
    CarteAffiche(paquet);
    paquet=paquet->suiv;
  }
  cout << endl;
}
// couper le paquet
// retourne le nouveau paquet (ie la nouvelle premiere carte)
carte* Coupe(carte* paquet,int val)
{
  if ( paquet ==NULL ) return paquet;
  if ( val <= 0 ) return paquet;
  if ( val > 128 ) return paquet;
  // a partir d'ici, comme val > 0, les deux parties du paquet que l'on coupe
  // contiennent au moins une carte
  // on recherche la derniere carte du paquet (pour remettre le
  // debut dessus)
  carte* fin=paquet;
  while ( fin->suiv != NULL ) fin=fin->suiv;
  fin->suiv=paquet;

  carte* derniere=paquet;
  for (int i=0;i<val-1;i++) {
    derniere=derniere->suiv;
    if ( derniere == NULL ) {
      cout << "pas sense arriver\n";
      return NULL;
    }
  }
  // on prend la carte au niveau de la coupe
  carte* debut=derniere->suiv;
  if ( debut == NULL ) {
    cout << "pas sense arriver\n";
    return NULL;
  }
  derniere->suiv=NULL;
  return debut;
}
void   Exo_Cartes(void)
{
  // on cree un paquet
  carte* paquet=CarteInitialise();
  PaquetAffiche(paquet);
  // on tire une valeur de coupe
  int val=random()%128; // il y a 128 cartes
  cout << "valeur de coupe= " << val << endl;
  // et on coupe 31 fois
  for (int i=0;i<31;i++) paquet=Coupe(paquet,val);
  PaquetAffiche(paquet);
}