
use Treedemo;

sub max {
  my $max = shift;
  foreach $foo (@_) { $max = $foo if $max < $foo; }
  return $max;
}

# We keep track of the dimensions of subtrees.  A 'dimensions'
# structure consists of an array of pairs, one per line of the
# representation, each pair containing the left and right extents of
# the line.

# Returns whether $this_dim, moved down by $offset lines, does not
# conflict with $dim.
sub test_dimensions {
  my ($this_dim, $dim, $offset) = @_;
  for $i (0..$#{$this_dim}) {
    return 1 if ($i+$offset > $#{$dim});    # passed the end of $dim
    return 0 if ($this_dim->[$i]->[1] > $dim->[$i+$offset]->[0]); # conflict
  }
  return 1;                     # passed the end of $this_dim
}

# Returns a new dimensions array resulting from combining $this_dim,
# moved down by $offset lines, with $dim.
sub compute_dimensions {
  my ($this_dim, $dim, $offset) = @_;
  my @new_dim = ();
  for $i (0.. max( $#{$this_dim}+$offset, $#{$dim} )) {
    my ($x, $y);
    if ($i < $offset ||               # haven't gotten to $this_dim yet
        $i-$offset > $#{$this_dim}) { # past the end of $this_dim
      $x = $dim->[$i]->[0];
      $y = $dim->[$i]->[1];
    } else {
      $x = $this_dim->[$i-$offset]->[0]; # $this_dim is farther to left
      if ($i > $#{$dim}) {
        $y = $this_dim->[$i-$offset]->[1]; # $dim ran out
      } else {
        $y = $dim->[$i]->[1];   # $this_dim is farther to right
      }
    }
    push @new_dim, [$x, $y];
  }
  return \@new_dim;
}

# Returns a new dimensions array resulting from prepending a box of the 
# given height and width to $dim.
sub prepend_box_to_dimensions {
  my ($height, $width, $dim) = @_;
  my @new_dim = ();
  for $i (0.. max( $height-1, $#{$dim} )) {
    my ($x, $y);
    if ($i < $height) {
      $x = 0;
    } else {
      $x = $width + $dim->[$i]->[0];
    }
    if ($i <= $#{$dim} ) {
      $y = $width + $dim->[$i]->[1];
    } else {
      $y = $width;
    }
    push @new_dim, [$x, $y];
  }
  return \@new_dim;
}

# Creates our new tree structure: each node is a hash with values
#  - text: array of strings for this node
#  - height: height of this node
#  - width: width of this node
#  - dimensions: dimensions array of the whole subtree rooted at this node
#  - y_offset: vertical offset from parent
#  - children: ref to array of children nodes
sub copy_tree {
  my ($orig_tree) = @_;
  my @children = map {copy_tree($_)} $orig_tree->children;
  my $height = @{$orig_tree->text};
  my $width = max( map {length} @{$orig_tree->text} );
  my $dimensions = [];
  my $i = 0;           # must be ascending over children, so outside the loop
  for my $child (@children) {
    my $child_dimensions = $child->{dimensions};
    while (test_dimensions( $child_dimensions, $dimensions, $i ) == 0) {++$i;}
    $dimensions = compute_dimensions( $child_dimensions, $dimensions, $i );
    $child->{y_offset} = $i;
  }
  # The +1 and +3 are to add a little extra space between boxes.
  $dimensions = prepend_box_to_dimensions( $height+1, $width+3, $dimensions );
  return {
          text => $orig_tree->text,
          height => $height,
          width => $width,
          dimensions => $dimensions,
          y_offset => 0,
          children => \@children
         };
}

# Given our tree as defined above, determines the x/y position of each node.
sub set_coords {
  my ($node, $x, $y) = @_;
  $node->{"x"} = $x;
  $node->{"y"} = $y;
  my $childx = $x + $node->{width} + 3;
  for my $child (@{$node->{children}}) {
    set_coords ($child, $childx, $y + $child->{y_offset});
  }
}

# Paints a line from ($x0,$y0) to ($y0,$y1) in $field.
# The silly s/// stuff is to prevent things like possibly overwriting
# pluses from previous paintings with dashes.
sub paint_line {
  my ($field, $x0, $y0, $x1, $y1) = @_;
  my $mid_x = int( ($x0 + $x1) / 2 );
  substr( $field->[$y0], $x0, $mid_x - $x0 ) =~ s/ /-/g;
  substr( $field->[$y1], $mid_x, $x1 - $mid_x ) =~ s/ /-/g;
  if ($y0 != $y1) {
    substr( $field->[$_], $mid_x, 1 ) = "+" for ($y0, $y1);
    substr( $field->[$_], $mid_x, 1 ) =~ s/[^+]/|/ for ($y0+1..$y1-1);
  }
}

# Paint the 2d array referred to by $field with $node and its
# desecendants.
sub paint {
  my ($field, $node) = @_;
  for $line (0 .. $#{$node->{text}})
  {
    substr( $field->[$node->{"y"}+$line],
            $node->{"x"},
            length( $node->{text}->[$line] ) )
      = $node->{text}->[$line];
  }
  for $child (@{$node->{children}}) {
    paint( $field, $child );
    paint_line( $field,
                $node->{"x"} + $node->{width},
                $node->{"y"} + ($node->{height}-1)/2,
                $child->{"x"},
                $child->{"y"} + ($child->{height}-1)/2 );
  }
}

sub layout_tree {
  my $layout = copy_tree (shift @_);
  set_coords( $layout, 0, 0 );
  my $total_width = max( map {$_->[1]} @{$layout->{dimensions}} );
  my $total_height = @{$layout->{dimensions}};
  my @field = map {" " x ($total_width)} (0..($total_height-1));
  paint \@field, $layout;
  return @field;
}

