use strict;
use warnings;
use integer;

use ExampleTree;
*main::layout_tree = \&ExampleTree::layout_tree;

print join "\n",
    @{ExampleTree->new(
        "0",
        ["0 1",
            ["0 1 1", 
                ["0 1 1 1",
                        ["0 1 1 1 1"],
                        ["0 1 1 1 2"]
                ],
            ],
            ["0 1 2"]
        ], 
        ["0 2",
            ["0 2 1",
                ["0 2 1 1"]
            ],
            ["0 2 2",
                ["0 2 2 1"],
                ["0 2 2 2"]
            ],
            ["0 2 3",
                ["0 2 3 1"]
            ]
        ],
        ["0 3",
            ["0 3 1"]
        ],
        ["0 4"],
        ["0 5",
            ["0 5 1",
                ["0 5 1 1"],
                ["0 5 1 2"],
                ["0 5 1 3"],
                ["0 5 1 4"],
                ["0 5 1 5"],
                ["0 5 1 6"]
            ],
            ["0 5 2",
                ["0 5 2 1",
                    ["0 5 2 1 1",
                        ["0 5 2 1 1 1"]
                    ]
                ]
            ]
        ]
    )->layout_tree($ARGV[0])}
;

exit;

sub ExampleTree::layout_tree {
    my($tree, $format)=@_;
    $format ||= 'horiz';
    
    my @ret=eval "layout_tree_$format(\$tree)";
    
    if($@) {
        if($@ =~ /Undefined subroutine &main::layout_tree_(\w+) called/) {
            die "Invalid format $1 used";
        }
        else {
            die $@;
        }
    }
    else {
        return \@ret;
    }
}

sub layout_tree_indent {
    my($node)=@_;
    
    my(@ret)=@{$node->text};
    
    for my $child($node->children) {
        push @ret, map { "    $_" } layout_tree_indent($child);
    }
    
    return @ret;
}

sub layout_tree_file {
    my($node)=@_;
    
    my(@ret)=(@{$node->text});
    
    my @children=($node->children);
    
    if(@children) {
        for my $n(@children[0..$#children-1]) {
            my @node=layout_tree_file($n);
            push @ret, "  |";
            push @ret, "  | $node[0]";
            push @ret, "  +-$node[1]";
            for my $l(@node[2..$#node]) {
                push @ret, "  | $l";
            }
        }
        
        my @node=layout_tree_file($children[$#children]);
        push @ret, "  |";
        push @ret, "  | $node[0]";
        push @ret, "  `-$node[1]";
        for my $l(@node[2..$#node]) {
            push @ret, "    $l";
        }
    }
    
    return @ret;
}

#Horizontal layout engine.
sub layout_tree_horiz {
    my $node=shift;
    
    return unless defined $node;
    
    my @text=@{$node->text};
    my @children=$node->children;
    my @ret;
    
    my $space=" " x (length($text[0]));
    
    if(@children == 0) {
        #REALLY easy.
        return @text;
    }
    elsif(@children == 1) {
        #Easy.
        return horiz_line_child(
               "$space   ",
            ["$text[0]   ",
             "$text[1]---",
             "$text[2]   "],
               "$space   ",
            $children[0]
        );
    }
    else {
        #Not-so-easy.
        
        my $even = @children % 2 ? 0 : 1;
        my $ctr;    #The middle child, so to speak.
        
        {
            no integer;
            $ctr=int(@children / 2);
        }

        #Process everything before the half-way point
        @ret=horiz_loop(\@children, $space, 0..$ctr-1);
        
        if($even) {
            #Just branch out to either side.
            
            pop @ret;   #Drop last extra pipe
            
            $text[0] .= ' |';
            $text[1] .= '-+';
            $text[2] .= ' |';
            
            push @ret, @text;
        }
        else {
            #Place a child right next to the parent.
            push @ret, (horiz_line_child(
                   "$space | ",
                ["$text[0] | ",
                 "$text[1]-+-",
                 "$text[2] | "],
                   "$space | ",
                $children[$ctr++]
            ), "$space | ");
       }
        
        #Process everything after the half-way point
        push @ret, horiz_loop(\@children, $space, $ctr..$#children);
        
        # Final formatting goodies
        @ret=horiz_compact($even, horiz_prettify(@ret));
    }
    
    return @ret;
}

#Miscellaneous prettification things
sub horiz_prettify {
    my @ret=@_;
    
    # Drop the final extra pipe.
    pop @ret;

    # Round off the top and bottom, and
    #  delete extraneous pipes.
    local $_;

    for(@ret) {
        s/\+/,/, last if /^\s*\+/;
        s/\|/ /;
    }
    
    for(reverse @ret) {
        s/\+/`/, last if /^\s*\+/;
        s/\|/ /;
    }
    
    return @ret;
}

#        +---
#      ,-|
#      | +---
# ---+ | 
#    |-+
# ---+ |
#      | +---
#      `-|
#        +---
# 
#   to:
# 
#        +---
#      ,-|  
# ---+ | +---
#    |-+
# ---+ | +---
#      `-| 
#        +---
# 
# (makes it *much* more compact in the long run)
sub horiz_compact {
    my($even, @ret)=@_;
    
    if($even) {
        my($fctr)=grep { $ret[$_] =~ /^\|/ } 0..$#ret;
        
        my $b2=$ret[$fctr-2];
        my $b1=$ret[$fctr-1];
        
        $b2 =~ s/\s*\|//;
        $b1 .= $b2;
        splice @ret, $fctr-2, 2, $b1;

        $fctr--;
        my $a1=$ret[$fctr+1];
        my $a2=$ret[$fctr+2];                
        $a2 =~ s/\s*\|//;
        $a1 .= $a2;
        #Remember, we've already lost an element.
        splice @ret, $fctr + 1, 2, $a1;
    }
    
    return @ret;
}

#Loop over a range of children
sub horiz_loop {
    my($children, $space, @indices)=@_;
    my @ret;

    if(@$children > 1) {
        for my $i(@indices) {
            push @ret, (
                horiz_line_child(
                     "$space | ",
                    ["$space +-"],
                     "$space | ",
                    $children->[$i]
                ),
                "$space | "
            );
        }
    }
    
    return @ret;
}

# Add the various sorts of lines around things.
#
# The arguments to this guy are complicated.  The
# best example I can give is:
#   horiz_line_child('a', ['b', 'c', 'd'], 'e', ...)
# where the ... ends up evaluating to 'A'..'H':
#   aA
#   aB
#   aC
#   bD
#   cE
#   dF
#   eG
#   eH
sub horiz_line_child {
    my($top, $centers, $bottom, $child)=@_;
    my @child=layout_tree_horiz($child);
    
    my $ctrcnt=@$centers;
    
    #Find the center of the most senior box.
    my($ctr)=grep { $child[$_] =~ /^\|/ } 0..$#child;

    my($lowctr, $highctr);
    {
        no integer;
        #I have no idea why these numbers work, but they do.
        $lowctr  = $ctr - int(($ctrcnt/2)+0.5);
        $highctr = $ctr + int(($ctrcnt/2)-0.5);
    }
    
    #All the top things
    for my $l(@child[0..$lowctr]) {
        $l = $top . $l;
    }
    
    #The centers
    for my $i($lowctr+1..$highctr) {
        $child[$i] = $centers->[$i - $lowctr - 1] . $child[$i];
    }
    
    #All the bottom things
    for my $l(@child[$highctr+1..$#child]) {
        $l = $bottom . $l;
    }
    
    return @child;
}
