#!/usr/bin/perl
use strict;
use warnings;

#
# In class on Tue April 18
# 
# Playing with the radix sort.

my $debug = 1;             # 1 => show debug output

my $n		= 100;     # How many numbers
my $max_number  = 1e7;     # Size of largest number
my $show        = 5;       # How many lines to show when printing.

my $random_list = make_random_list($n, $max_number);
if ($debug){
  print "Here's a sample random list: \n";
  print_list($random_list, $show);
}

# Test nth_digit
if ($debug){
  print "Testing nth_digit.  Output should be '0 0' '1 1' ...\n";
  for my $i (0..5){
    print $i , "  ", nth_digit(543210, $i), "\n";
  }
}

# Test log10_largest
if ($debug){
  print "Test log10_largest.  Output should be 0 1 2 3 ... \n";
  print " 10**i " . log10_largest( [ 10**$_   ] ) for 0..10;
  print "\n";
  print " 99... " . log10_largest( [ 0+('9'x$_) ] ) for 1..11;
  print "\n";
}

# ----- subroutines ----------------------------------

# Usage: 
#  $sorted_list = radix_sort( $list );
sub radix_sort {
  my ($list) = @_;
  my $number_of_digits = log10_largest($list);
}

# Usage:
#  $digits = log10_largest($list);   (assumed all positive)
#  For example, if $list = [512, 1234, 7, 21]
#  largest is 1234 which has a 10**3 part, so $digits is 3.
#  This has been tested only for numbers up to 10 digits.
sub log10_largest {
  my ($list) = @_;
  my $largest = 0;
  for my $element (@$list){
    $largest = $element if $largest < $element;
  }
  my $kludge_round_off = 1e-12;
  return int($kludge_round_off + log($largest)/log(10));
}

# Usage:
#  $array_ref = make_random_list($how_many, $largest);
sub make_random_list {
  my ($how_many, $largest) = @_;   # Argument list.
  my $answer = [];                 # Create a reference to empty array
  for (my $i=0; $i<$how_many; $i++){
    push @$answer, int(rand($largest));
  }
  return $answer;
}

# Usage:
#  print_list($list_ref, $lines);   # lines is something like 10
sub print_list {
  my ($list, $lines) = @_;
  for my $i (0 .. $lines-1){
    printf(" %12d  %12d \n", $i, $list->[$i]);
  }
  my $length = scalar @$list;
  for my $i ($length-$lines .. $length-1){
    printf(" %12d  %12d \n", $i, $list->[$i]);
  }  
}

# Usage: 
#   $value = nth_digit($number, $digit);
#   If $number = 51620 and $digit=2 return value=6, 
#   namely the 10**$digit part of $number.
sub nth_digit {
  my ($number, $digit) = @_;
  return int( $number / 10**$digit ) % 10;
}
