// esempio di primitive per
// la gestione di una catena 
// di dati ordinati per una
// chiave

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

// definizione chiave:
typedef int CHIAVE;

// definizione tipo di dato per il nodo:
struct nodo{
 CHIAVE key;
 // dati di esempio
 float f;
 int i;
 char c;
 // puntatore al prossimo elemento
 struct nodo *prossimo;
};

// ***************************************************************************
// FUNZIONI DA MODIFICARE A SECONDA DEL TIPO DI NODO
// ***************************************************************************

// confronto nodi:
int confronto_chiave(struct nodo *a, CHIAVE x){
 if(a->key==x)return 0;
 if(a->key>x)return 1;
 return -1;
} // con chiave stringa andrebbe cambiato


// copia nodi: copia un nodo in un altro
void nodicpy(struct nodo *dest, struct nodo *orig){
 memcpy(dest, orig, sizeof(struct nodo));
}

// stampa nodi: due funzioni per la stampa in senso
//              crescente o decrescente
void stampa_lista_dec(struct nodo *p){
 if (!p) return;
 stampa_lista_dec(p->prossimo);
 cout << "chiave = " << p->key << "\n";
 cout << "indir. = " << p      << "\n";
 //cout << "     f = " << p->f   << "\n";
 //cout << "     i = " << p->i   << "\n";
 //cout << "     c = " << p->c   << "\n";
}

void stampa_lista_cre(struct nodo *p){
 if (!p) return;
 cout << "chiave = " << p->key << "\n";
 cout << "indir. = " << p      << "\n";
 //cout << "     f = " << p->f   << "\n";
 //cout << "     i = " << p->i   << "\n";
 //cout << "     c = " << p->c   << "\n";
 stampa_lista_cre(p->prossimo);
}


// creazione nodo:
struct nodo *crea_nodo(void){
 struct nodo *nuovo;

 nuovo=new struct nodo[1];

 if(!nuovo){
  cerr << "crea_nodo: memoria esaurita";
  exit(EXIT_FAILURE);
 }

 return nuovo;
}

// distruzione nodo
void distruggi_nodo(struct nodo *x){

 if(!x) return;
 delete[] x;
}

// ***************************************************************************
// FUNZIONI GENERALI
// ***************************************************************************

// inserimento in lista ricorsivo
struct nodo *inserisci_in_lista(struct nodo *p, struct nodo *nuovo){

 // controllo che la lista non sia vuota
 if(!p){
   p=crea_nodo();
   nodicpy(p,nuovo);
   p->prossimo=NULL;
   return p;
  }
 
 // controllo se va inserito prima del nodo della
 // lista in esame
 if(confronto_chiave(p,nuovo->key)==1){
   struct nodo *nuovo_nodo;
   nuovo_nodo=crea_nodo();
   nodicpy(nuovo_nodo, nuovo);
   nuovo_nodo->prossimo=p;
   return nuovo_nodo;
  }

 // passo a confrontare i successivi
 p->prossimo=inserisci_in_lista(p->prossimo, nuovo);

 // restituisco l'indirizzo iniziale dell'elenco
 return p;
}
 
// disalloca la memoria utilizzata dall'elenco
void distruggi_lista(struct nodo *p){

 // controllo che ci sia qualcosa da distruggere (condizione di uscita)
 if(!p)return;
 
 // prima libero cio' che segue
 distruggi_lista(p->prossimo);

 // poi libero il nodo
 distruggi_nodo(p);
}

// ricerco il nodo in base alla chiave
// restituisco NULL se non lo trovo
struct nodo *ricerca_in_lista(struct nodo *p, CHIAVE x){
 if(!p) return NULL;
 if(!confronto_chiave(p,x))
   return p;
 return ricerca_in_lista(p->prossimo, x);
}

// eliminazione nodo con chiave x
struct nodo *elimina_nodo(struct nodo *p, CHIAVE x){
 // condizione di uscita
 if(!p) return NULL;

 // confronto chiave e nodo in esame
 if(!confronto_chiave(p,x)){
   struct nodo *a;
   a=p->prossimo;
   distruggi_nodo(p);
   return a;
  }

 // non coincidono passo al resto della lista
 p->prossimo=elimina_nodo(p->prossimo, x);
 return p;
}

// restituisce il numero di elementi in elenco
unsigned int dimensione_lista(struct nodo *p){
 if(!p) return 0;
 return 1+dimensione_lista(p->prossimo);
}

// recupero nodo di indice x oppure NULL
struct nodo *ricerca_in_lista_per_indice(struct nodo *p, unsigned int x){
 if(!x) return p;
 if(!p) return NULL;
 return ricerca_in_lista_per_indice(p->prossimo, x-1);
}

// eliminazione nodo di indice x 
struct nodo *elimina_nodo_per_indice(struct nodo *p, unsigned int x){
 // la lista e' vuota ?
 if(!p) return NULL;
 // e' il primo nodo quello da eliminare ?
 if(!x){
   struct nodo *a;
   a=p->prossimo;
   distruggi_nodo(p);
   return a;
 }
 // passo al nodo successivo
 p->prossimo=elimina_nodo(p->prossimo, x-1);
 return p;
}

// ***************************************************************************
// MAIN:  banale programma di esempio utilizzo primitive
// ***************************************************************************

int main(int argc, char **argv){
 struct nodo b;
 struct nodo *lista;
 int ii;
 CHIAVE z;

 // inizializzazione lista
 lista=NULL;

 cout << "Inserisco nodi in elenco\n";
 for(ii=0;ii<atoi(argv[1]);++ii){
   b.key=rand();
   b.f=rand()/(rand()+0.1f);
   b.i=rand();
   b.c=rand()%96+32;
   cout << "Inserisco nodo con chiave " << b.key << "\n";
   lista=inserisci_in_lista(lista, &b);
  }

 
 // stampo i dati
 cout << "Stampo nodi in elenco in senso crescente\n";
 stampa_lista_cre(lista);
 cout << "\nnumero elementi: " << dimensione_lista(lista) << "\n";

 cout << "Inserisci chiave da eliminare: ";
 cin >> z;
 lista=elimina_nodo(lista, z);

 cout << "\nStampo nodi in elenco in senso decrescente\n";
 stampa_lista_dec(lista);
 cout << "\nnumero elementi: " << dimensione_lista(lista) << "\n";

 cout << "\nInserisci chiave da ricercare: ";
 cin >> z;
 cout << "il nodo in esame si trova in " << ricerca_in_lista(lista, z) << endl;

 // libero la memoria
 distruggi_lista(lista);
}