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

// esempio di creazione di una lista ordinata di numeri a 
// virgola mobile (l'algoritmo utilizzato e' detto insertion sort)

// PROTOTIPI
long double *inserisci_in_elenco(long double *,long double);
void stampa_lista(long double *);

// VARIABILI GLOBALI
int dim_lista=0;

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

 unsigned int nn; // numero di valori da generare/ordinare
 long double *lista=NULL; // e' la nostra lista
 double gg;          // numero da inserire
 char *risposta;
 char stampa=0; // devo stampare ? 0=no
 
 if(argc<2){
   cout << "Utilizzo: " << argv[0] << " <numero valori> <stampa[s/n]>\n";
   exit(EXIT_FAILURE);
 }


 nn=atoi(argv[1]);

 // controllo se si desidera la stampa
 if(argc==3&&(argv[2][0]=='s'||argv[2][0]=='S'))
   stampa = 1;

  
 for(int ii=0;ii<nn;++ii){
   gg=rand()/((long double)rand()+0.1);
   lista=inserisci_in_elenco(lista,gg);
 }

 if(stampa)
   stampa_lista(lista);

 return 0;
}

long double *inserisci_in_elenco(long double *elenco,long double nuovo){

  long double *new_buffer;
  int ii;

  // prima cosa, controllo se l'elenco e' vuoto
  if(!elenco){
    elenco=new long double[dim_lista=1];
    if(!elenco)
      exit(EXIT_FAILURE);
    *elenco=nuovo;
    return elenco;
  }

  // l'elenco non e' vuoto, devo cercare dove inserire
  // per semplicita' ho implementato una ricerca sequenziale
  // ma e' sensato l'utilizzo di ricerca binaria O(log2(n))
  for(ii=0;(ii<dim_lista)&&(elenco[ii]<nuovo);++ii);
  
  
  // alloco un nuovo buffer dove creare l'elenco aggiornato
  new_buffer=new long double[dim_lista+1];
  if(!new_buffer)
    exit(EXIT_FAILURE);

  // copio i dati
  memcpy(new_buffer, elenco, ii*sizeof(long double));
  new_buffer[ii]=nuovo;
  memcpy(&new_buffer[ii+1], &elenco[ii],(dim_lista-ii)*sizeof(long double));
  ++dim_lista;
  // questa fase e' obbligatoriamente O(n)!

  // libero la vecchia lista
  delete[] elenco;

  return new_buffer;
}

long double *elimina_elemento_lista(long double *elenco, int indice){
  long double *new_buffer;

  new_buffer=new long double[dim_lista-1];

  memcpy(new_buffer, elenco, indice*sizeof(long double));
  memcpy(&new_buffer[indice], &elenco[indice+1], (dim_lista-indice-1)*sizeof(long double));

  --dim_lista;
  delete[] elenco;

  return new_buffer;
}

void stampa_lista(long double *elenco){
  for(int ii=0;ii<dim_lista;++ii)
    cout << ii << " - " << elenco[ii] << endl;
}