#!/usr/local/bin/perl -w

use strict;
use Algorithm::Numerical::Shuffle qw(shuffle);
use List::Util qw(min max sum);
use POSIX qw(ceil floor);
use Benchmark;

my $Max_Questions = 0;
my $Max_Lines = 0;

{
   my $results;
   my %hash;

   for (([100,30]), ([500,150]), ([1000,300]))
   {
      $Max_Lines = @$_[0];
      $Max_Questions = @$_[1];

      printf ("%d Lines, %d Questions\n", $Max_Lines, $Max_Questions);

      timethese (100000, {
                          'test_jcwren'      => sub { test_jcwren ()       },
                          'test_lucs'        => sub { test_lucs ()         },
                          'test_lucsjcwren'  => sub { test_lucsjcwren ()   },
                          'test_lucsjcwren2' => sub { test_lucsjcwren2 ()  },
                         }
                );

      print "\n";
   }

=cut
   #
   #  Be sure to set $Max_Lines and $Max_Questions at the top
   #
   for (0..1000)
   {
      $results = test_lucsjcwren ();
      $hash {$_}++ foreach (@$results);
   }

   show_array ($results);
   show_histogram (1, \%hash);
=cut
}

#
#  Test cases
#
sub test_jcwren
{
   return \@{[(shuffle (0..$Max_Lines-1)) [0..$Max_Questions-1]]};
}

sub test_lucs
{
   my $m = $Max_Questions;
   my $j = $Max_Lines - $m + 1;
   my %sample;

   while ($m-- > 0)
   {
      my $val = int ($j * rand (1));
      $sample{ exists $sample{$val} ? $j - 1 : $val } = 0;
      ++$j;
   }

   return (\@{[keys %sample]});
}

sub test_lucsjcwren
{
   my $m = $Max_Questions;
   my $j = $Max_Lines - $m + 1;
   my %sample;

   while ($m--)
   {
      my $val = int (rand ($j++));

      $sample {exists $sample{$val} ? $j - 2 : $val} = 0;
   }

   return (\@{[keys %sample]});
}

sub test_lucsjcwren2
{
   my $m = $Max_Questions;
   my $j = $Max_Lines - $m + 1;
   my %sample;

   while ($m--)
   {
      my $val = int (rand ($j++));

      $sample {exists $sample{$val} ? $j - 2 : $val} = undef;
   }

   return (\@{[keys %sample]});
}

#
#  Utilities
#
sub show_array
{
   my $array = shift;

   my @sorted = sort {$a <=> $b} @$array;

   print"Element\t\tUnsorted\tSorted\n";
   print"-------\t\t--------\t------\n";

   for (my $z = 0; $z < $Max_Questions; $z++)
   {
      print"   $z";
      print"\t\t    @$array[$z]\t\t";
      print"   $sorted[$z]\n";
   }
}

sub show_histogram
{
   my $bin_size = shift;
   my $articles = shift;

   my $width = 50;
   my $max_count = max (values %$articles);
   my $scale = ceil($max_count / $width);

   print "  Index        Count\n";
   print "------------- -------", "-" x 50, "\n";

   my @bins = sort {$a <=> $b} keys %$articles;

   foreach my $bin (min(@bins)..max(@bins))
   {
      my $count = $articles->{$bin} || 0;
      my $extra = ($count % $scale) ? '.' : '';
      my $start = $bin * $bin_size;
      my $end = $start + $bin_size - 1;
      printf "%4d .. %4d  \[%4d\] %s$extra\n",
      $start, $end, $count, '#' x floor ($count / $scale);
   }

   print "\n  Scale: #=$scale\n\n" if $scale > 1;
}