#!/usr/bin/perl
#
# eg17: third benchmarking test: deduce O() for two algorithsm..
#

use strict;
use warnings;
use Function::Parameters qw(:strict);
use Benchmark qw(:all);

my $t = shift @ARGV || 1;		# time per alg per value of N

my @array;


fun On2_uniq()		# original O(n^2) uniq alg
{
	# build @uniq, an array of all unique elements of @array
	my @uniq;
	foreach my $i (0..$#array)		# foreach index i in @array
	{
		# count how many elements array[j] (i!=j) are the same as array[i]
		my $count = 0;
		foreach my $j (0..$#array)
		{
			$count++ if $i != $j && $array[$i] == $array[$j];
		}
		# unique if $count == 0
		push @uniq, $array[$i] if $count == 0;
	}
}


fun On_uniq()		# final pretty O(n) uniq alg
{
	my %freq; map { $freq{$_}++ } @array;	   # build element -> frequency
	my @uniq = grep { $freq{$_} == 1 } @array; # find unique elements
}


foreach my $scale (1,10,100)
{
	my $str = "17, 5, 3, 17, 2, 5, 7, 6, 6, 10, " x $scale;
	chop $str;				   # remove last ,
	@array = split( /,\s*/, $str );
	my $n = @array;

	my $on2 = countit( $t, \&On2_uniq ); my $on2_iter = $on2->iters;
	my $on = countit( $t, \&On_uniq ); my $on_iter = $on->iters;

	printf( "n=%6d,    O(n^2):iter=%8d,    O(n):iter=%8d\n",
		$n, $on2_iter, $on_iter );
}
