
use Treedemo;
use strict;

sub layout_tree {
  my ($lines) = layout_tree_aux(@_);
  @$lines;
}

# Like layout_tree, but return two values:
# 1. reference to array of lines to be printed
# 2. index of which line in this drawing is to be
#    attached to the larger drawing

sub layout_tree_aux {
    my($tree) = @_;

    # Get the representation of the root node
    my $node_lines = $tree->text;

    my $node_height = scalar(@$node_lines);

    # find the index of the line nearest the middle  of the array
    my $middle = int(($node_height-1)/2);

    # Get the children of the node
    my @children = $tree->children;
    my $child_count = scalar(@children);

    # If no children, return the existing lines
    return ($node_lines,  $middle) unless($child_count);

    # Combine the children with the current node

    # Get the layout for each sub tree.
    my (@child_lines, %attachment_point);
    my ($total_height, $min_attach, $max_attach) = (0, undef, 0);
    foreach my $child (@children) {
        my ($lines, $attach) = layout_tree_aux($child);
        $attach += $total_height;
        push(@child_lines, @$lines);
        $attachment_point{$attach} = 1;
        $min_attach = $attach unless defined $min_attach;
        $max_attach = $attach;
        $total_height += @$lines;
#        push @child_lines, ""; $total_height++;
    }

    $min_attach = $middle if $middle < $min_attach;
    $max_attach = $middle if $middle > $max_attach;
    $total_height = $node_height if $node_height > $total_height;

    # Determine the width of the current node and create a string of
    # spaces to pad lines in the subtrees with.
    my $node_width = length($node_lines->[0]);
    my $node_pad = " " x $node_width;

    # Printing children to the right of the parent.
    # So prepend the lines to the child lines. Need to prepend spaces
    # to the other lines.
    # If there is only one child join with ---
    # multiple children are joined with -+- for the first and +- for subseuqent

    for my $y (0 .. $total_height - 1) {
      my $separator = "   ";
      if ($y >= $min_attach && $y <= $max_attach) {
        $separator = " | ";
      }
      if ($attachment_point{$y}) {
        $separator = " +-";
      }
      if ($y == $middle) {
        if ($attachment_point{$y} && $child_count == 1) {
          substr($separator, 0, 2) = "--";
        } else {
          substr($separator, 0, 2) = "-+";
        }
      }

      if($y < $node_height) {
        $node_lines->[$y] = $node_lines->[$y] . $separator . $child_lines[$y];
      } else {
        $node_lines->[$y] = $node_pad . $separator .  $child_lines[$y];
      }
    }

    return ($node_lines, $middle);
}


