#!/usr/bin/perl -w

#
# insertion-sort.pl
#
# Programma che legge ed ordina dei dati usando l'algoritmo insertion-sort
# Input: una successione di numeri interi terminata da EOF (end of file)
# Output: i numeri ordinati
#

&main;	# eseguo il programma principale

#-------------------------------------------------------------------------
sub insertionSort ($@) {
	# Inserisco un elemento in una lista ordinata in modo da tenerla ordinata
	# Input: 	il primo argomento è l'elemento da inserire
	# 		il resto è la lista (di almeno 1 elemento)
	# Output: 	la nuova lista ordinata
	my ($datoDaInserire, @lista) = @_;	# assegno gli argomenti a variabili locali
	my @listaNuova = ();			# creo una nuova lista vuota
	my $trovato = 0;			# uso un flag per indicare se ho trovato l'elemento (0=FALSE)
	my $elemento = 0;			# variabile locale usata dal foreach
	foreach $elemento (@lista) {		# per ogni elemento della lista in input
#		print "esamino $elemento \> $datoDaInserire\n";
		if (!$trovato && 				# se ancora non ho trovato il punto di inserimento
		     $elemento > $datoDaInserire) { 		# E se l'elemento della lista è maggiore
			$trovato = 1;				# allora ho trovato il punto!
			push @listaNuova, $datoDaInserire;	# aggiungo il dato alla lista che sto costruendo
		}
		push @listaNuova, $elemento;			# continuo aggiungendo gli elementi della vecchia lista
	}
	# se non l'ho ancora inserito vuol dire che va in fondo alla lista
	if (!$trovato) {
		push @listaNuova, $datoDaInserire;
	}
	return @listaNuova;			# torno la nuova lista
}

#-------------------------------------------------------------------------
sub main {
	# Programma principale
	my $numeroDati = 0;			# contiene il numero di dati letti
	my $ultimoDatoLetto = 0;		# contiene l'ultimo dato letto
	my @listaDatiOrdinati = ();		# contiene la lista di dati letti, ordinata

	while ($ultimoDatoLetto = <STDIN>) {	# leggo un dato da STDIN (torna undef se EOF)
		chomp $ultimoDatoLetto;		# tolgo l'eventuale accapo letto
		$numeroDati ++;			# incremento di 1 il numero di dati letti
		if ($numeroDati == 1) {		# se siamo al primo dato
			@listaDatiOrdinati = ($ultimoDatoLetto);	# inizializzo la lista
		} else {
						# altrimenti inserisco il dato letto nella lista
			@listaDatiOrdinati = insertionSort($ultimoDatoLetto, @listaDatiOrdinati);
		}
	}

	# alla fine stampo i risultati
	print "Ho letto $numeroDati dati:\n";
	my $dato;
	foreach $dato (@listaDatiOrdinati) {
		print "$dato \n";
	}
}
#---------------------------------- fine ----------------------------------