
  sub pad {
    my $str = shift;
    my $len = shift;

    # pad $str with spaces to make it $len characters long

    $str .= " " while ($len > length $str);
    return $str;
  }

  sub center {
    my $str = shift;
    my $len = shift;
    my $pad = shift;

    # center $str within a space $len characters long. if $pad is
    # specified, pad $str with spaces after centering to make it $len
    # characters long.

    if ($len > length $str) {
      $str = " " x (($len - length $str) / 2) . $str;
      $str = pad ($str, $len) if $pad;
    }

    return $str;
  }

  sub layout_tree {
    my $tree = shift;
    my @text = @{$tree->text};
    my @children = $tree->children;

    # recurse depth-first, left-right through $tree, returning a
    # downward view of the tree at each stop

    # if we're at a leaf node, then just return it; this is where the
    # recursion stops

    return @text unless @children;

    # build a picture of this node's children

    my @out = ();
    foreach my $child (@children) {

      if (@out) {

        # find the length of the longest line seen so far (in the
        # picture of this node's children), and pad all the lines seen
        # so far to that length

        my $pad_len = (sort {$b <=> $a} map (length, @out))[0];
        @out = map { pad $_, $pad_len } @out;

        # get the downward picture from this child, and tack each line
        # of that picture on to the right of the current picture

        my @child = layout_tree ($child);
        $out[$_] .= " $child[$_]" for (0..$#child);

      } else {

        # this is the first child seen

        @out = layout_tree ($child);

      }
    }

    # now we have the picture of all of this node's children, so we need
    # to add the text of the node itself to the top

    # we're going to want to center this node above the picture of its
    # children, but there may be additional padding on the left side if
    # any of those children have children of their own; so for the
    # purposes of centering, find the space occupied only by this node's
    # immediate children, and center the text over that

    my $blank = ($out[0] =~ /^( *)/)[0];
    my $len0 = length $out[0];
    my $center = $len0 - length $blank;

    if ($#children == 0) {

      # if this node has only one child, then just center a "|" above it

      unshift (@out, pad ($blank . center ("|", $center), $len0));

    } else {

      # if this node has multiple children, then we're not so lucky...
      # we're going to take the first line of the existing output,
      # duplicate it, and transform all of the cell borders into
      # connection points

      # start by stripping off any whitespace to the left, and holding
      # it for later

      my ($pad, $lines) = ($out[0] =~ /^( *)(.*)$/);

      # replace each block of non-whitespace (ie, a cell border) with a
      # ".", centered in the space where the border was

      $lines =~ s/(\S+)/center (".", length $1, 1)/ge;

      # this is going to make some additional whitespace on the left, so
      # strip that off too (and add it to what we've saved). any
      # remaining spaces are part of the connection lines, so turn them
      # into "-"'s.

      $pad .= $1 if ($lines =~ s/^( *)//);
      $lines =~ s/ *$//;
      $lines =~ s/ /-/g;

      # now we have a line that connects all of the children; figure out
      # where to attach it to its parent

      my $text0 = $blank . center ($text[-1], $center);
      $text0 =~ s/(\S+)/center ("x", length $1)/e;

      my $pos = index ($text0, "x") - length $pad;

      # attach it with a reasonable character ("|" if directly over a
      # child's connection point, "v" otherwise)

      substr ($lines, $pos, 1) =
        (substr ($lines, $pos, 1) eq "v" ? "|" : "^");

      # add this mess to the output

      unshift (@out, pad ($pad . $lines, $len0));
    }

    # now add this cell itself, properly positioned, to the output, and
    # we're done

    unshift (@out, $blank . center ($_, $center)) for reverse @text;

    return @out;
  }

