
$BOXWID = .30;
$BOXHT = .25;
$HSPACE = .2;
$VSPACE = -.5;
$ARROW = ''; # set to '->' to get arrows on verticals.

sub make_tree {
  my ($base, $degree, $x, $y, $labels) = @_;
  my $ind = '  ' x (4- $degree);
  ($x, $y) = (0,0) unless defined $x;
  print STDERR "${ind}make_tree($base, $degree) at ($x, $y)\n";

  # emit pic code for box with base number
  # call make_tree recursively for child trees
  # accumulate width of subtrees to compute total height and width
  # draw horizontal line
  # draw vertical line(s)
  # return total height and width
  my ($xs, $ys) = (0, $VSPACE);
  my $label = $labels->[$base] ;
  $label = $base unless defined $label;
  print qq{N$base: box "$label" at ($x, $y)\n};
#  $base = 2<<$degree if $base == 0;   # Fake this
  print STDERR "$ind loop is ", $degree-1, ".. 0\n";
  for my $bitpos (reverse (0 .. $degree-1)) {
    my $bit = 1 << $bitpos;
    print STDERR "$ind bit is $bit\n";
    next if $base & $bit;
    my $subnode = $base | $bit;
    my ($w, $h) = make_tree($subnode, $bitpos, $x+$xs, $y+$ys, $labels);
    if ($bitpos == $degree - 1) {
      # vertical line directly from node
      print qq{L$base: line from N$base.s to N$subnode.n $arrow\n};
      print qq{P$base: 1/2 of the way between L$base.start and L$base.end\n};
    } else {
      # vertical line from right part of horizontal line
      my $xx = $x + $xs;
      my $yy = $y + $VSPACE/2;
      print qq{line from ($xx, P$base.y) to N$subnode.n $arrow\n};
    }
    $xs += $w+$HSPACE;
#    $ys += $h;
  }
  # Horizontal line
  if ($degree > 1) {
    print qq{line from P$base right $xs-$HSPACE\n} ;
  }
  return ($xs, $ys);
}

print ".PS\n";
print "boxwid := $BOXWID; boxht := $BOXHT\n";
print "linethick=1;\n";
my $depth = shift;
make_tree(0, $depth, 0, 0, \@ARGV);
print ".PE\n";

sub position {
  my ($n, $d) = @_;
  my ($x, $y);
  return (0,0) if $n == 0;
  for my $b (0 .. $d-1) { 
    my $bv = $n & 1;
    $y += $bv;
    if ($saw1 && $bv == 0) {
      $x += 1<<($b-1);
    }
    $saw1 ||= $bv;
    $n >>= 1;
  }
  ($x, $y);
}
