use strict;
use warnings;

#use Math::Random qw(random_uniform random_set_seed_from_phrase random_binomial random_set_seed);
#use Math::Random qw(random_binomial random_set_seed);
#use Data::Dumper;
use List::Util qw(sum);
use Carp;
#use Crypt::Random qw( makerandom );
#use File::Slurp; #for large list of real randoms

#my @rands = read_file('rand.txt');
#print sum(@rands), "\n";
#croak;
#my $r = makerandom ( Size => 10, Strength => 1 );
#print $r;
#croak;

#random_set_seed_from_phrase(2);
#my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#random_set_seed(@seed);
#my @a = random_uniform($n);
#my $runs = 1000;
#my $counter = 1; # global: subroutine entry counter
#my $counter = 0; # global: subroutine entry counter
#increment($runs, \@rands);

sub makecounterold {
	my $counter = shift;
#	sub {return $counter++}
#	return {sub $counter++};
	return sub {$counter++};
}

sub makecounter  {
	my $counter = shift;
  my $plusser = sub {
    $counter++;
  };
  return $plusser;
}

start();

sub start {
	my $runs = 1000;
	my $n = 2**8;
	increment($runs, $n);
}

sub increment {
#	my ($runs, $randsref) = @_;
	my ($runs, $n) = @_;
	my (@axis, @data);
#	my @axis = 0;
#	my @data = 1;
#	my $start = 16655;
#	my $end = 16675;
#	my $start = 1;
	my $start = 0;
	my $end = 100;
#	for my $inc (16655..16675) {
	for my $inc ($start..$end) {

#		my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#		random_set_seed(@seed);
	#	my $counter = 0;
		my $av = 0;
		my $p = $inc/100;

		for (1..$runs) {
#			my $p = $inc/100;
#			my $p = $inc/100000;
#			$counter = 1;
#			$counter = 0;
			my $count = makecounter(0);
#print "start count is ", $count->(), "\n";
	#		my $p = 0.002374;
#			countit($p, $randsref);
			countit($p, $n, $count);
#			$av += $counter;
#print "count is ", $count->(), "\n";
#			$av += $count;
			$av += $count->();
	#		$counter = 0;
#			$counter = 1;
		}

		print $inc/100, ' ', sprintf("%.1f", $av/$runs), "\n";
#		push @axis, $inc/100;# if $inc/10 == int($inc/10);
		push @axis, $p;
		push @data, sprintf("%.1f", $av/$runs);

	}
	
	dograph(\@axis, \@data, $start, $end);

}

sub countit {
	my ($p, $n, $count) = @_;
#	my ($p, $randsref) = @_;
#	my $nt = 1;
#	my $n = 2**8;
#	my @seed = (1 + int(rand(2147483562)), 1 + int(rand(2147483398)));
#	random_set_seed(@seed);
#	my @a = random_binomial($n, $nt, $p);
#	my $bits = 10;
#	my $r = makerandom ( Size => $bits, Strength => 1 );
#	my $divfactor = 2**$bits;
#	my $pmult = $p*$divfactor;
#	my @a = map {makerandom ( Size => $bits, Strength => 1 ) > $pmult ? 0 : 1} 1..$n;
#print Dumper @a;
#print "pmult $pmult\n";
#print makerandom ( Size => $bits, Strength => 1 ), "\n";
#croak;
	my @a = map {rand > $p ? 0 : 1} 1..$n;
#	my @a = map {(rand > $p)} 1..$n;
#	print $offset*$n, "\n";
#	my $r = shift @rands;
#print "$r, $p\n";
#	my @a = map {shift(@rands) > $p ? 0 : 1} 1..$n;

# my @a = makedist($n, $randsref, $p);

#	@a = (0, 1, 0, 0, 0, 0, 1, 0);
	my %h = map {$_ => 0} 0..$#a;

#	print Dumper @a;
#croak;
#	print Dumper %h;
#	print "bs\n";
#	if (sum(@a) > 0) {
#		my %temp = map {$h{$_} == 1} keys %h;
#		%h = %temp;
#		$counter++;
#	} else {
#		$counter++;
		binary_search(\@a, 0, \%h, $count);
		my @misses = grep {$h{$_} != 1} keys %h;
		if (scalar @misses) {
			print join('', $_, ' ', $misses[$_], "\n") for @misses;
			croak "missed some\n";
		}
#	}
#	my @misses = grep {$h{$_} != 1} keys %h;
#	croak "missed some\n/" if scalar @misses;

#	print "bs over $counter\n";
#	print Dumper %h;
#	print Dumper @misses;
}

sub binary_search {
  my ($aref, $pos, $href, $count) = @_;
#	$counter++;
	$count->();
#print scalar @$aref;
#print " $pos \n";
#print Dumper $aref;
#  my $mid;
#	my @aref = @$aref;
	my $bigness = scalar(@$aref);
	if ($bigness == 1) {
		$href->{$pos}++;
	} else {
		my $mid = $bigness/2;
		if (sum(@$aref) > 0) {
		  my @aref1 = @$aref[$mid..$#$aref];
		  binary_search(\@aref1, $mid+$pos, $href, $count);
		  my @aref2 = @$aref[0..--$mid];
		  binary_search(\@aref2, $pos, $href, $count);
		} else {
			$href->{$_}++ for $pos..$pos+$bigness-1;			
		}
	}
}

sub makedist {
	my ($n, $randsref, $p) = @_;
	my @a;

	for (1..$n) {
		my $thisone = shift @$randsref;
		my $bit = $thisone > $p ? 0 : 1;
		push @a, $bit;
	}

	return @a;
}

sub dograph {
#	my ($axisref, $dataref, $p, $n) = @_;
	my ($axisref, $dataref, $start, $end) = @_;
#	use GD::Graph::bars;
	use GD::Graph::points;
	use GD::Graph::Data;
	#use Carp;

	#my $data = GD::Graph::Data->new([
	#    ["1st","2nd","3rd","4th","5th","6th","7th", "8th", "9th"],
	#    [    1,    2,    5,    6,    3,  1.5,    1,     3,     4],
	#]) or croak GD::Graph::Data->error;

#	my $data = GD::Graph::Data->new([\@xaxis, \@data]) or croak GD::Graph::Data->error;
	my $data = GD::Graph::Data->new([$axisref, $dataref]) or croak GD::Graph::Data->error;

#	my $graph = GD::Graph::lines->new(800, 600);
#	my $graph = GD::Graph::bars->new(800, 600);
	my $graph = GD::Graph::points->new(800, 600);

	$graph->set( 
	#    x_label         => 'X Label',
	#    y_label         => 'Y label',
#		title           => $p,
		transparent     => 0,
		t_margin				=> 10,
		b_margin				=> 10,
		l_margin				=> 10,
		r_margin				=> 10,
#		y_max_value     => 520,
		y_max_value     => 528,
#		y_max_value     => 0.2,
#		y_min_value     => -0.2,
		y_min_value     => 0,
#		y_label_skip		=> 10
#		x_label_skip		=> 10,
		x_label_skip		=> 4,
#		y_tick_number		=> 16,
#		y_tick_number		=> 8,
		y_tick_number		=> 33,
#		x_tick_number		=> 10,
#		x_tick_number		=> 26,
		markers					=> 8,
		marker_size			=> 2,
		long_ticks			=> 1,
#		x_max_value			=> 1,
		x_min_value     => 0,
	) or croak $graph->error;
	 
	$graph->plot($data) or croak $graph->error;
	 
	my $file = "bars$start-$end.png";
#	my $file = $n."bars$p.png";
	#my $file = "barssplicy$p.png";
	open(my $out, '>', $file) or croak "Cannot open '$file' for write: $!";
	binmode $out;
	print $out $graph->gd->png;
	close $out;

#	use GD::Graph::lines;
	use GD::Graph::points;
}