#!/usr/bin/perl

# Usage: 
# ./ssstgen.pl n h
# Where n is the number of balls, and h is the highest siteswap value.
# High values will take a while due to a bit of a hack I used to
# generate states.  The output is a file called nballmaxh.eps.  n and h
# must both be numbers, rather than their ss equivalent, although the
# output will use a,b,c etc for throws higher than 9.

# This code is open source.  If you want to distribute, modify or sell
# it then do so.  If you do sell it then please let me know at:
# guy.griffiths@rdg.ac.uk so we can laugh about the fact that you
# found someone stupid enough to pay for it.  Oh, also I'd rather you
# kept the next line intact, but I'm not going to stop you taking
# credit for it either.

# Written by Guy Griffiths

$balls=$ARGV[0];
$highss=$ARGV[1];
if($highss<$balls){die"No of balls must be greater than highest ss value\n";}

$nstates=factorial($highss)/(factorial($balls)*factorial($highss-$balls));

$picw=2*$nstates;
$papw=3*$picw+10;
$pich=$nstates+2+0.4*$highss;
$paph=3*$pich+10;
open(TEX,">temp.tex")||die "Cannot open file for writing";
print TEX "\\documentclass{article}\n\\pagestyle{empty}\n";
print TEX "\\special{papersize=$papw mm,$paph mm}\n";
print TEX "\\setlength{\\textwidth}{$papw mm}\n";
print TEX "\\setlength{\\textheight}{$paph mm}\n\\begin{document}\n\n";
print TEX "\\begin{center}\n\\setlength{\\unitlength}{3mm}\n";
print TEX "\\begin{picture}($picw,$pich)\n";
$temp=$pich/2;
print TEX "\\multiput(0,",$pich/2,")(1,0){$nstates}{\\oval(0.8,$pich)}\n";

for($i=0,$j=0;$i<2**($highss);$i++){
    $t=0;
    $curst=dec2bin($i);
    map$t+=$_,(split//,$curst);
    if($t==$balls){$state[$j]=bin2dec($curst);$j++;}
}



for($i=0;$i<$nstates;$i++){
#Find all transitions going to current state
    drawstate($state[$i],$i);
    $curst=$state[$i];
    for($j=0;$j<=$highss;$j++){
	$initialstate=2*$curst+1-2**$j;
	$valid=0;
	for($k=0;$k<$nstates;$k++){if($initialstate==$state[$k]){$valid=1;$inin=$k}}
	if($valid==1){drawtransition($inin,$i,$j);}
    }
}

print TEX "\\end{picture}\n\\end{center}\n\\end{document}";
system("latex temp.tex");
$psname=$balls."ballmax".$highss;
system("dvips -E -o $psname.eps temp.dvi");
system("rm temp.aux temp.log temp.tex temp.dvi");

sub drawstate{
    my @state=split(//,dec2bin($_[0]));
    while($#state<=$balls){unshift(@state,0);}
    my $x=$_[1];
    my $y=$pich-($highss*0.4);
    my $i;
    for($i=0;$i<$highss;$i++){
	$onoff=pop(@state);
	print TEX "\\put($x,$y){\\circle";
	if($onoff==1){print TEX "*";}
	print TEX "{0.3}}\n";
	$y+=0.4;
    }
}

sub drawtransition{
    # Arguments: State to draw from, state to draw to, ss value.
    my $fromx=$_[0];
    my $tox=$_[1];
    my $fromy=$pich-1-($highss*0.4)-$tox;
    my $ss=$_[2];
    if($ss>9){$ss=chr($ss+87)}
    print TEX "\\put(",$fromx,",",$fromy,"){\\circle{0.8}}\n";
    print TEX "\\put(",$fromx-0.2,",",$fromy-0.2,"){\\bf{\\tiny ",$ss,"}}\n";
    print TEX "\\put(",$fromx,",",$fromy-0.4,"){\\line(0,-1){0.1}}\n";
    unless($fromx==$tox){print TEX "\\put(",$fromx,",",$fromy-0.5,"){\\vector(",($tox-$fromx)/abs($tox-$fromx),",0){",abs($tox-$fromx),"}}\n";}
    else{print TEX "\\put(",$fromx,",",$fromy-0.5,"){\\line(0,-1){0.05}}\n";}


    return 0;
}

sub dec2bin {
    my $str = unpack("B32", pack("N", shift));
    $str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
    return $str;
}
sub bin2dec {
    return unpack("N", pack("B32", substr("0" x 32 . shift, -32)));
}

sub factorial {
    my $n = shift;
    return undef if $n < 0;
    return 1 if $n == 0;
    return $n * factorial($n - 1);
}