#!/usr/bin/perl
#
# Timing a radix sort of a list of random numbers.
#
# Note that this is just measuring wall clock time,
# which is only a reasonable estimate if the system
# isn't too busy with other stuff.
# 
# Usage:
#         ./radix.pl > radix_out.txt
#   
# 
# Jim Mahoney, April 17
#
use strict;
use warnings;
use Time::HiRes qw(time);
my $DEBUG = 0;             # Set to 1 for one $n run with diagnostic output.

if ($DEBUG){
  time_sort(1e4, 1e6, 5);  # ($n, $max_number, $show)
}
else {
  print("# Radix sort timing.\n");
  printf("# %12s %12s \n", 'n', 'time');
  my @ns = (1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6, 3e6);
  for my $n (@ns){
    my $time = time_sort($n, 1e7, 0);  # ($n, $max_number, $show)
    printf("  %12d  %12.5f \n", $n, $time);
  }
}
exit;

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

# Usage: $sec = time_sort($n, $max_number, $show)
# First generate a list of $n random numbers from 0 to $max_number,
# then return the time in seconds it takes to sort them.
# If $show > 0, print that many numbers and some other diagnostics.
sub time_sort {
  my ($n, $max_number, $show) = @_;
  if ($show){
    print "** Radix sort **\n";
    print "Using random numbers in the range 0 .. $max_number.\n";
  }

  my $numbers = random_numbers( $n, $max_number );

  if ($show){
    print "Here's the inital list : \n";
    print_list($numbers, $show);
    print "Starting sort.\n";
  }

  start_timer();
  my $sorted     = radix_sort($numbers, 0, $show);  # ($n, $opt_digits, $debug)
  my $time = elapsed_time();

  if ($show){
    print "Done.  Elapsed time with n=$n is $time .\n";
    print "Here's the sorted list : \n";
    print_list($sorted, $show);
  }

  return $time;
}

# Usage:
#   start_timer();
#   print "elapsed seconds = " . elapsed_time();
my $saved_time;
sub start_timer {
  $saved_time = time();
}
sub elapsed_time {
  return time() - $saved_time;
}

# Return a list of random numbers
#  $numbers = random_numbers($how_many, $max_value)
sub random_numbers {
  my ($n, $max_number) = @_;
  my $numbers = [];
  for (my $i=0; $i<$n; $i++){
    push @$numbers, int(rand($max_number));
  }
  return $numbers;
}

# print_list($list, $how_many)
# prints $how_many entries from the start and end of @$list.
sub print_list {
  my ($list, $how_many) = @_;
  print 'Oops - not a reference to a list' unless ref($list) eq 'ARRAY';
  my $length = scalar(@$list);
  printf(" %12d  %12d \n", $_, $list->[$_])
    for (0 .. ($how_many-1), $length-($how_many+1) .. $length-1);
  return 1;
}

# Return 10**nth digit of a number, e.g.
#   nth_digit(3145, 0) = 5
#   nth_digit(3145, 2) = 1
sub nth_digit {
  my ($x, $which) = @_;
  return int($x/(10**$which)) % 10;
}

# Sort a list of numbers using the radix algorithm.
#  This is slightly faster if the rough size largest number of the list is given
#  by specifying its number of digits base 10 (eg "3" for "999").
#  You can also specify how many numbers from the start 
#  and end of the list to print for debugging.
#    $sorted_list_ref = radix_sort($list_ref)
#  or
#    $sorted_list_ref = radix_sort($list_ref, $max_digits)
#  or
#    $sorted_list_ref = radix_sort($list_ref, $max_digits, $show_debug_numbers)
sub radix_sort {
  my $numbers    = shift;
  my $max_digits = shift || 1e6; # 10**(1e6) is effectively infinity
  my $show       = shift || 0;   # how many to show for debugging; 0 => no debug
  my $digit = 0;
  my $continue = 1;
  while ($continue and $digit < $max_digits){
    $continue = 0;
    print " Starting sort on digit $digit .. \n" if $show;
    my $sorting_list;
    $sorting_list->[$_] = [] for 0..9;
    for my $number (@$numbers){
      my $key = nth_digit($number, $digit);
      $continue = 1 if $key > 0;             # stop if all nth_digit's are zero.
      push @{$sorting_list->[$key]}, $number;
    }
    $numbers = [];
    push @$numbers, @{$sorting_list->[$_]} for 0..9;

    if ($show){
      print " .. done digit $digit\n";
      print_list($numbers, $show);
    }

    $digit++;
  }
  return $numbers;
}
