/* esempio di gestione liste circolari: si generano un certo numero di nodi
 * posti in una lista circolare, quindi si utilizza una ``conta'' (Problema
 * di Josephus) per determinare gli elementi da eliminare.
 * Determinare l'elemento che soppravvive */

#include<stdio.h>
#include<stdlib.h>
#include"util.h"

#undef DEBUG

#ifdef DEBUG
 #define dprintf(a) printf((a))
#else 
 #define dprintf(a)
#endif

struct nodo{
	int indice;
	float value;
	struct nodo *next;
};

int main(int argc, char *argv[]){

 struct nodo *p, *ii;
 int jj;
 int N, M;

 /* controllo argomenti */
 if(argc<3){
   fprintf(stderr, "Utilizzo: josephus N M\n");
   fprintf(stderr, "          N numero di nodi\n");
   fprintf(stderr, "          M numero di passi\n");
   exit(1);
   }
 N=atoi(argv[1]);
 M=atoi(argv[2]);

 /* alloco N elementi in lista circolare 
  * mi servono 2 puntatori */
 p=ii=Malloc(sizeof(struct nodo));
 
 for(jj=0;jj<N;++jj){
   ii->next=Malloc(sizeof(struct nodo));
   ii=ii->next;
   dprintf(".");
 }
 /* chiudo la lista */
 ii->next=p;
 dprintf("\n");

 /* riempo la lista con
  * gli indici */
 ii=p;
 jj=1;
 do{
   ii->indice=jj;
   ii->value=((float)rand()/rand());
   dprintf(",");
   ii=ii->next;
   ++jj;
 }while(p!=ii);
 dprintf("\n");

 /* inizio la conta */
 while(p!=p->next){
   for(jj=1;jj<M;++jj)
     p=p->next;
   dprintf("+");
   ii=p->next->next;
   free(p->next);
   p->next=ii;
 }
 dprintf("\n");

 printf("È rimasto: %d con %f\n",p->indice,p->value);
 free(p);
 return 0;
}