#!/usr/bin/perl -w
# 演算法: radix sort
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)

use Getopt::Std;
use strict;

my (%opts) = (
    d => 3,	# number of digits in each input value
    r => 10,	# radix
    n => 8,	# number of input values
    e => "ansi",# type of emphasis, either "ansi" or "html"
);

getopts('d:e:n:r:', \%opts);

my ($ES) = {
    ansi => { pre=>"\x1b[7m", post=>"\x1b[m", nl=>"\n" },
    html => { pre=>"<em>", post=>"</em>", nl=>"<br /><br />\n" },
};

sub ord2chr { return chr($_[0] + ord($_[0]<10 ? '0' : 'A')); }

sub cntsort {
    my ($A, $wd) = @_;
    my ($B, $C, $i);
    $#$B = $#$A;
    $C->[0] = 0;
    foreach $i (@$A) { ++$C->[$i->[$wd]]; }
    for ($i=1; $i<$opts{r}; ++$i) { $C->[$i]+=$C->[$i-1]; }
    foreach $i (reverse @$A) {
	$B->[--$C->[$i->[$wd]]] = $i;
    }
    return $B;
}

sub print_array {
    my ($A, $emph) = @_;
    my ($x, $d);
    # prefix and postfix of emphasis strings
    if (not exists $ES->{$opts{e}} ) {
	$opts{e} = "ansi";
	warn "-e must be followed by one of ", join(",",keys %$ES),
	    "; assuming '-e ansi' now\n";
    }
    foreach $x (@$A) {
	print " ";
	for ($d=0; $d<$opts{d}; ++$d) {
	    if (defined $emph and $d == $emph) {
		print $ES->{$opts{e}}{pre},
		    ord2chr($x->[$d]), $ES->{$opts{e}}{post};
	    } else {
		print ord2chr($x->[$d]);
	    }
	}
    }
    print $ES->{$opts{e}}{nl};
}

my ($A, $x, $d);

# 如果要測試自己設計出來的資料, 請:
# 1. 更改下句陣列內容
# 2. 將 「*** 用亂數產生測試資料 ***」 註解下面那一句註解掉
$A = [ qw(326 506 496 583 625 320 531 406 491) ];
foreach $x (@$A) {
    $x = [ map {
	$_ le "9" ? $_ :
	$_ le "Z" ? ord($_)-ord("A")+10 :
		    ord($_)-ord("a")+10
    } split(//, $x) ];
}

# *** 用亂數產生測試資料 ***
$A = [ map { [map { int(rand()*$opts{r}) } 1..$opts{d}] } 1..$opts{n} ];
print_array($A);
for ($d=$opts{d}-1; $d>=0; --$d) {
    print $ES->{$opts{e}}{nl} x 2;
    print_array($A, $d);
    $A = cntsort($A, $d);
    print_array($A, $d);
}