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

use List::Util qw( reduce );
use Benchmark qw( cmpthese );

my %code = (
	limbic => sub {
		my ($x, $list) = @_;
		$x--;
		my @top;
		$#top = $x;
		for my $item ( @$list ) {
			next if defined $top[ -1 ] && $item <= $top[ -1 ];
			for my $id ( 0 .. $#top ) {
				$top[ $id ] = $item and last if ! defined $top[ $id ];
				if ( $item > $top[ $id ] ) {
					@top[ $id .. $#top ] = ($item, @top[ $id .. $#top - 1]);
					last;
				}
			}
		}
		return @top;
	},
	browseruk => sub {
		my( $n, $aref ) = @_;
		my @topN;
		push @topN, reduce{ 
			$a > $b && (!@topN || $a < $topN[ -1 ] )
			? $a : ( !@topN || $b < $topN[ -1 ] )
			? $b : $a;
		} @$aref for 1 .. $n;
		return @topN;
	},
	aristotle => sub {
		my ( $n, $list ) = @_;
		my @top = @$list[ 0 .. $n - 1 ];
		@top = ( sort { $a <=> $b } $_, @top )[ 1 .. $n ] for @$list[ $n .. $#$list ];
		return @top;
	},
);

my @bench = (
	[ qw/ 10 5 / ],
	[ qw/ 100 5 / ],
	[ qw/ 1000 5 / ],
	[ qw/ 10000 5 / ],
	[ qw/ 100000 5 / ],
	[ qw/ 100 50 / ],
	[ qw/ 1000 50 / ],
	[ qw/ 10000 50 / ],
	[ qw/ 100000 50 / ],
	[ qw/ 1000 500 / ],
	[ qw/ 10000 500 / ],
	[ qw/ 100000 500 / ],
);

$|++;

while( @bench ) {
	my ( $max, $n ) = @{ shift @bench };

	my $duration = sprintf "%.2g", ( log( $max ) / log( 20 ) ) ** 2;

	print "\nLooking for top $n in $max (running for $duration CPU secs)\n";

	my @values = 1 .. $max; 

	my @top = ( sort { $a <=> $b } @values )[ @values - $n .. $#values ];


	for( keys %code ) {
		my @result = sort { $a <=> $b } $code{ $_ }->( $n, \@values );
		die "$_ not ok: [@result] ne [@top]\n" if "@result" ne "@top";
	}

	cmpthese -$duration => {
		map { my $x = $code{ $_ }; $_ => sub { my @x = $x->( $n, \@values ) } } keys %code
	};
}

##</code><code>##

	baseline => sub {
		my ( $n, $list ) = @_;
		return ( sort { $a <=> $b } @$list )[ @$list - $n .. $#$list ];
	},