#!/usr/local/bin/perl
use strict;
use Data::Dumper;

use vars qw/
  @list
  @depth_matrix
  $leaf_count
/;

sub true  { return 1; }
sub false { return 0; }

sub insertRow($;$)
{
  my ($name, $parent) = @_;
  #print "insertRow($name,$parent)\n";

  my %obj = ();
  my $pid = findParent( $parent );
  my $depth = 0;
  
  if ( $pid > -1 ) 
  {
    $depth = $list[ $pid ]{ 'depth' } + 1;
    $list[ $pid ]{ 'is_leaf' } = false;
    $leaf_count--;
  }

  $leaf_count++;
  $obj{ 'name'        } = $name   || "";
  $obj{ 'parent_name' } = $parent || "";
  $obj{ 'parent_node' } = $pid;                 # WARNING: DON'T Override ZERO with -1
  $obj{ 'is_leaf'     } = true;                 # child will set it to false
  $obj{ 'is_root'     } = ( $parent ? 0 : 1 );  # root don't have parents
  $obj{ 'x'           } = -1 * $leaf_count;
  $obj{ 'y'           } = $depth;
  $obj{ 'depth'       } = $depth;               # depth = parent.depth + 1
  $obj{ 'min'         } =  99999 + $leaf_count;
  $obj{ 'max'         } = -99999;

#  print Dumper \%obj;

  push @list, \%obj;

  push @{ $depth_matrix[ $depth ] }, $#list;

  #print Dumper \@list;
}

sub findParent($)
{
  my ( $parent ) = @_;
  if ( !$parent ) { return -1; }

  #print "findParent($parent)\n";

  my $count = $#list + 1;

  for my $i ( 0 .. $count - 1 )
  {
    my $elem = $list[ $i ];
    #print "\n$i. NAME[".$elem->{ 'name' } . "]\n";
    if ( $elem->{ 'name' } eq $parent ) { return $i; }
  }

  return -1;
}

sub fixLeaf()
{
  my $x = 0;
  my $count = $#list + 1;
  
  for my $i ( 0 .. $count - 1 )
  {
    my $elem = $list[ $i ];
    my $leaf = $elem->{ 'is_leaf' };

    if ( $leaf ) 
    {
      $elem->{ 'x'   } = $x; 
      $elem->{ 'min' } = $x; 
      $elem->{ 'max' } = $x; 
      $x++;
    }
    else
    {
      #$elem->{ 'x'   } = -1 - $x; 
      #$elem->{ 'min' } = -1 - $x; 
      #$elem->{ 'max' } = -1 - $x; 
    }
  }
}

sub layout()
{
  # Start from the deepest leaf, then from left to right, then up by one depth
  my $count  = $#list + 1;
  my $parent = ""; 
  
  my $depth_count = $#depth_matrix + 1;

  for my $i ( reverse 0 .. $depth_count - 1 )
  {
    #print "HI $i";
    my @depth_row = @{ $depth_matrix[ $i ] };
    my $depth_row_count = $#depth_row + 1;

    my $pid = -1;

    for my $j ( 0 .. $depth_row_count - 1 )
    {
      print "($i,$j):\t";

      my $elem_id  = $depth_matrix[ $i ][ $j ];
      my $elem     = $list[ $elem_id ];

      print Dumper $elem;

      my $curr_pid = $elem->{ 'parent_node' };
      my $curr_x   = $elem->{ 'x' };

      if ( $curr_pid != $pid )
      {
        if ( $pid > -1 )
        {
          # SAVE results
          # calculate center
          SaveResult($pid);
        }

        $pid = $curr_pid;
      }

      # Recalculate min/max pairs
      {
        if ( $list[ $pid ]{ 'min' } > $curr_x ) { $list[ $pid ]{ 'min' } = $curr_x; print "min: $curr_x"; }
        if ( $list[ $pid ]{ 'max' } < $curr_x ) { $list[ $pid ]{ 'max' } = $curr_x; print "max: $curr_x"; }
      }
    }

    if ( $pid > -1 )
    {
      # SAVE
      # calculate center
      SaveResult($pid);
    }
  }
}

# calculate center
sub SaveResult($)
{
  my ($pid) = @_;

  my $x = ($list[ $pid ]{ 'max' } - $list[ $pid ]{ 'min' })/2 + $list[ $pid ]{ 'min' };
#     $x = int($x) + 0;

  $list[ $pid ]{ 'x' } = $x;

  print "SaveResult($pid):". Dumper( $list[$pid] ). "\n";
}

sub test()
{
  @list = ();
  @depth_matrix = ();
  $leaf_count = 0;
                                         
  #             NAME          PARENT,    PID, isLeaf, isRoot,   x,  y, depth
  insertRow( "Object" );
  insertRow( "Stream",     "Object"   );
  insertRow( "InStream",   "Stream"   );
  insertRow( "OutStream",  "Stream"   );
  insertRow( "InFile",     "InStream" );

  fixLeaf();

  #print ( defined( undef ) ? 1 : 0 );

#  print Dumper \@list;
#  print Dumper \@depth_matrix;

  layout();
  print Dumper \@list;
}

sub display()
{
  my $x = 0;
  my $count = $#list + 1;

  for my $i ( 0 .. $count - 1 )
  {
    my $elem = $list[ $i ];
    my $x = $elem->{'x'} * 55;
    my $y = $elem->{'y'} * 15;
    my $t = $elem->{'name'};
    print "<text x='$x' y='$y' font-size='6pt' fill='blue'>$t</text>\n";
  }
}

test();
display();
exit;

1;

__END__

---------- Perl5 Compiler ----------
(3,0):	$VAR1 = {
          'name' => 'InFile',
          'is_leaf' => 1,
          'min' => 1,
          'depth' => 3,
          'max' => 1,
          'x' => 1,
          'y' => 3,
          'parent_name' => 'InStream',
          'parent_node' => 2,
          'is_root' => '0'
        };
min: 1max: 1SaveResult(2):$VAR1 = {
          'name' => 'InStream',
          'is_leaf' => '0',
          'min' => 1,
          'depth' => 2,
          'max' => 1,
          'x' => 1,
          'y' => 2,
          'parent_name' => 'Stream',
          'parent_node' => 1,
          'is_root' => '0'
        };

(2,0):	$VAR1 = {
          'name' => 'InStream',
          'is_leaf' => '0',
          'min' => 1,
          'depth' => 2,
          'max' => 1,
          'x' => 1,
          'y' => 2,
          'parent_name' => 'Stream',
          'parent_node' => 1,
          'is_root' => '0'
        };
min: 1max: 1(2,1):	$VAR1 = {
          'name' => 'OutStream',
          'is_leaf' => 1,
          'min' => '0',
          'depth' => 2,
          'max' => '0',
          'x' => '0',
          'y' => 2,
          'parent_name' => 'Stream',
          'parent_node' => 1,
          'is_root' => '0'
        };
min: 0SaveResult(1):$VAR1 = {
          'name' => 'Stream',
          'is_leaf' => '0',
          'min' => '0',
          'depth' => 1,
          'max' => 1,
          'x' => '0.5',
          'y' => 1,
          'parent_name' => 'Object',
          'parent_node' => '0',
          'is_root' => '0'
        };

(1,0):	$VAR1 = {
          'name' => 'Stream',
          'is_leaf' => '0',
          'min' => '0',
          'depth' => 1,
          'max' => 1,
          'x' => '0.5',
          'y' => 1,
          'parent_name' => 'Object',
          'parent_node' => '0',
          'is_root' => '0'
        };
min: 0.5max: 0.5SaveResult(0):$VAR1 = {
          'name' => 'Object',
          'is_leaf' => '0',
          'min' => '0.5',
          'depth' => '0',
          'max' => '0.5',
          'x' => '0.5',
          'y' => '0',
          'parent_name' => '',
          'parent_node' => -1,
          'is_root' => 1
        };

(0,0):	$VAR1 = {
          'name' => 'Object',
          'is_leaf' => '0',
          'min' => '0.5',
          'depth' => '0',
          'max' => '0.5',
          'x' => '0.5',
          'y' => '0',
          'parent_name' => '',
          'parent_node' => -1,
          'is_root' => 1
        };
min: 0.5$VAR1 = [
          {
            'name' => 'Object',
            'is_leaf' => '0',
            'min' => '0.5',
            'depth' => '0',
            'max' => '0.5',
            'x' => '0.5',
            'y' => '0',
            'parent_name' => '',
            'parent_node' => -1,
            'is_root' => 1
          },
          {
            'name' => 'Stream',
            'is_leaf' => '0',
            'min' => '0',
            'depth' => 1,
            'max' => 1,
            'x' => '0.5',
            'y' => 1,
            'parent_name' => 'Object',
            'parent_node' => '0',
            'is_root' => '0'
          },
          {
            'name' => 'InStream',
            'is_leaf' => '0',
            'min' => 1,
            'depth' => 2,
            'max' => 1,
            'x' => 1,
            'y' => 2,
            'parent_name' => 'Stream',
            'parent_node' => 1,
            'is_root' => '0'
          },
          {
            'name' => 'OutStream',
            'is_leaf' => 1,
            'min' => '0',
            'depth' => 2,
            'max' => '0',
            'x' => '0',
            'y' => 2,
            'parent_name' => 'Stream',
            'parent_node' => 1,
            'is_root' => '0'
          },
          {
            'name' => 'InFile',
            'is_leaf' => 1,
            'min' => '0.5',
            'depth' => 3,
            'max' => 1,
            'x' => 1,
            'y' => 3,
            'parent_name' => 'InStream',
            'parent_node' => 2,
            'is_root' => '0'
          }
        ];
<text x='27.5' y='0' font-size='6pt' fill='blue'>Object</text>
<text x='27.5' y='15' font-size='6pt' fill='blue'>Stream</text>
<text x='55' y='30' font-size='6pt' fill='blue'>InStream</text>
<text x='0' y='30' font-size='6pt' fill='blue'>OutStream</text>
<text x='55' y='45' font-size='6pt' fill='blue'>InFile</text>
Normal Termination
Output completed (0 sec consumed).