#!/usr/bin/perl -wT

#
# radix-sort.pl
#
# Ordinamento di un vettore di N valori con l'algoritmo radix-sort
#


my $RADIX = 10;

&main();

#--------------------------------------------------------------------------
#
# Programma principale
#
sub main {
	my @dati = &leggiDati();		# leggo i dati
	my $massimo = &cercaMassimo(@dati);	# cerco il massimo
	my $potenza = 1;			# potenza di 10 corrente (si parte dalle unità)
	while ($massimo) {			# finchè ci sono cifre da esaminare
		@dati = &passata($potenza, @dati);	# faccio una passata
		$massimo /= $RADIX;		# divisione (intera) per 10 del massimo
		$potenza *= $RADIX;		# passo alla potenza di 10 seguente
	}
	&stampaDati(@dati);			# alla fine stampo i risultati
}

#----------------------------------------------------------------------------
#
# stampo i dati
#
sub stampaDati (@) {
	my @dati = @_;
	my $numeroDati = $#dati + 1 ;
	print "Ho letto $numeroDati dati:\n";
	print join( "\n", @dati), "\n";
}

#----------------------------------------------------------------------------
#
# leggo i dati da STDIN e li filtro tenendo i soli validi
#
sub leggiDati () {
	print "inserisci i numeri (positivi)\n";
	my @dati = <STDIN>;		# contiene la lista di dati letti da STDIN
	chop @dati;			# tolgo gli spazi e \n che seguono
	# filtro i dati letti tenendo:
	@dati = grep	{defined 	# butto i valori indefiniti
			&&
			/^[+]?[0-9]+$/	# tengo solo i numeri (interi e positivi)
			}
			@dati;
	return @dati;
}

#----------------------------------------------------------------------------
#
# inserisco i valori nella matrice a seconda della cifra corrente e poi li rileggo
# riga per riga dall'alto a SX verso il basso a DX
#
sub passata ($@) {
	my $potenza = shift;
	# una matrice è un vettore di (riferimenti a) vettori
	my @matrice;
	my $dato;
	foreach $dato (@_) {
		$cifra = ($dato / $potenza) % $RADIX;	# calcolo la cifra corrente
		# aggiungo il numero nella riga della matrice che corrisponde alla cifra corrente
		# se la riga non c'è viene creata automaticamente
		push @{$matrice[$cifra]}, $dato;
	}
	my @risultati;
	my $riga;
	foreach $riga (@matrice) {		# riga per riga ...
		# aggiungo i valori al risultato (se ce ne sono)
		push @risultati, @$riga if ($riga);
	}
	return @risultati;			# torno la matrice "appiattita"
}

#----------------------------------------------------------------------------
#
# cerco il massimo valore che mi servirà per sapere quante passate devo fare
#
sub cercaMassimo (@) {
	my $max = shift;			# per iniziare prendo il primo valore
	my $dato;
	foreach $dato (@_) {
		$max = $dato if ($dato > $max);	# se ne trovo uno maggiore lo ricordo
	}
	return $max;				# torno il massimo trovato
}

#----------------------------------------------------------------------------