#!/usr/bin/perl -w
#
# Copyright (c) 2002 Erik Oliver
#
# $Id: ETree.pm,v 1.9 2003/05/11 04:21:07 erik Exp $
# 
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use, copy,
# modify, merge, publish, distribute, sublicense, and/or sell copies
# of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.

package SimpleTree;
use strict;
#use warnings;

sub new
{
	my $class = shift;
	my $object = {};
	bless $object, $class;

	# optional 3rd arg: node label
	if(@_) {
		my $label = shift;
		$object->SetLabel($label);
	} else {
		$object->SetLabel("");
	}
	$object->{'Children'} = [];
	
	return $object;
}

sub GetLabel
{
	my $self = shift;
	return $self->{"Label"};
}

sub SetLabel
{
	my $self = shift;
	my $newlabel = shift;
	$self->{"Label"} = $newlabel;
}

sub GetChildren
{
	my $self = shift;
	return @{$self->{"Children"} || []};
}

sub IsLeaf
{
	my $self = shift;
	return (scalar(GetChildren $self) == 0 ? 1 : 0);
}

sub AddChildrenRight
{
	my $self = shift;
	push @{$self->{"Children"}}, @_;
	return $self;
}

sub AddChildrenLeft
{
	my $self = shift;
	@{$self->{"Children"}} = (@_,@{$self->{"Children"}});
	return $self;
}

sub PrintableName
{
	my $self = shift;
	my $name = GetLabel $self;
	return "<$name>";
}

sub _evenwidth
{
	# took in an array ref
	my $array = shift;

	# find the length of longest line
	my $max = 0;
	foreach my $line (@$array) {
		my $w = length($line);
		$max = $w if $w > $max;
	}

	# pad all lines to that length
	foreach my $line (@$array) {
		my $toadd = $max - length ($line);
		next unless $toadd;

		my $left = int($toadd / 2);
		my $right = $toadd-$left;
		$line = (' ' x $left) . $line . (' ' x $right);
	}
}

sub _evenheight($)
{
	#took in an array ref
	my $arrays = shift;

	# find tallest
	my $max = 0;
	foreach my $self_print (@$arrays) {
		my $h = @$self_print;
		$max = $h if $h > $max;
	}

	foreach my $self_print (@$arrays) {
		# figure out constant line width
		my $length = length($self_print->[0]);
		# how tall am I?
		my $height = @$self_print;
		my $toadd = $max - $height;

		if($toadd > 0) {
			push @$self_print, ( scalar( ' ' x $length ) ) x $toadd;
		}
	}

	return $max;
}

sub _tacktogether($$) {
	my $self_print = shift;
	my $daughters_print = shift;

	my $h = scalar(@$self_print);

	foreach my $to_tack (@$daughters_print) {
		# possibly strip horizontal space
		# in a future implementation

		foreach my $line (0..($h - 1)) {
			$self_print->[$line] .= $to_tack->[$line] . ' ';
		}
	}
}

sub _center ($$$$) {
	my $init_space = shift;
	my $length = shift;
	my $end_space = shift;
	my $string = shift;

	# total width
	my $totalwidth = length($init_space) + $length + length($end_space);

	# center point
	my $centerpoint = length($init_space) + int($length/2);

	my $curlength = length($string);
	my $initialspaces = $centerpoint - int($curlength/2) ;
	my $output = (' ' x $initialspaces) . $string;
	$output .= (' ' x ($totalwidth-length($output)));
	
	return $output;
}

sub _pipeup($$) {
	my $self_print = shift;
	my $printname = shift;

	my $new_pipes = $self_print->[0];
	my $pipe_count = $new_pipes =~ tr<|><+>;
	my ($init_space,$end_space) = ('','');

	# strip off the leading space on either side
	if($new_pipes =~ s<^( +)><>s ) {
		$init_space = $1;
	}

	if($new_pipes =~ s<( +)$><>s ) {
		$end_space = $1;
	}
	
	# "true" length of non white space on line below...
	my $length = length($new_pipes);

	if($pipe_count < 2) {
		$new_pipes = _center($init_space,$length,$end_space,"|");
	} else {
		# make the sideways pipes
		$new_pipes =~ tr< ><->;
		substr($new_pipes,0,1) = "/";
		substr($new_pipes,-1,1) = "\\";
		$new_pipes = $init_space . $new_pipes . $end_space;
	}
	my $bar = _center($init_space,$length,$end_space,"|");
	my $centername = _center($init_space,$length,$end_space,$printname);

	# formatting for this node
	unshift @$self_print, $bar, $centername, $new_pipes
}

sub PrintTree
{
	my $self = shift;
	my (@self_print, @daughter_print);
	my $printname = PrintableName $self;


	# am I a leaf?
	if(IsLeaf $self) {
		@self_print = ("|", $printname);
		_evenwidth(\@self_print);
		# debug print:
		#print map "$_\n", @self_print;
	} else {
		# generate print boxes for my daughters
		@daughter_print = map {&PrintTree($_)} (GetChildren $self);

		# even the heights out
		my $height = _evenheight(\@daughter_print);
		@self_print = ('') x $height; # box of max height
		_tacktogether(\@self_print,\@daughter_print);
		_pipeup(\@self_print,$printname);
		_evenwidth(\@self_print);
	}
	
	return \@self_print;
}

1;