#!/usr/bin/perl
# $Id$
use strict;
use warnings;
our $VERSION = sprintf '0.%d.%d', '\$Revision: 1.0 $' =~ /(\d+)\.(\d+)/xm;
use English qw( -no_match_vars );
use Data::Dumper;

sub d {
    print Data::Dumper->new( [@_] )->Indent(1)->Sortkeys(1)->Terse(1)->Dump;
    return;
}

d thread( get_list('data.txt') );

# construct list from file
sub get_list {
    my $file = shift;
    open my $fh, q{<}, $file
        or die "Cannot open read data from $file: $OS_ERROR\n";
    my @list;
    while ( my $line = <$fh> ) {
        $line =~ /^ (\S+) \s+ (\S+) \s+ (\d+) \s* $/xm
            and push @list, [ $1, $2, $3 ];
    }
    close $fh;
    return \@list;
}

# return an AoA containing threaded Nodes
sub thread {
    my $list = shift;
    return [] if !@{$list};

    # twist the list (keeping the timestamp): parent -> child
    # as an HoA:
    #   { Parent_ID => [ Child_ID, Child_TS ] }
    my $ch = {};
    foreach my $rec ( @{$list} ) {
        push @{ $ch->{ $rec->[1] } }, [ $rec->[0], $rec->[2] ];
    }

    # abuse this structure, moving elements recursively beside their parents
    # => Nodes Array will get one more element: the "Children" A-ref
    foreach my $id ( keys %{$ch} ) {
        next if !exists $ch->{$id};
        _threader( $ch, $ch->{$id} );
    }

    # drop timestamp info keeping only IDs
    return _reduce_thread( $ch->{0} );
}

# recursive nodes mover: it will move nodes from the "main" Hash
# into the Children Array besides their Parent
sub _threader {
    my ( $ch, $where ) = @_;
    my $found = 0;
    foreach my $c ( @{$where} ) {
        if ( exists $ch->{ $c->[0] } ) {
            push @{$c}, delete $ch->{ $c->[0] };
            $found++;
        }
        if ( @{$c} > 2 ) {
            $found += _threader( $ch, $c->[2] );
        }
    }
    return $found;
}

# sorts the resulting Nodes AoA and drops TS info
sub _reduce_thread {
    my ($aref) = @_;
    $aref = [ sort { $a->[1] <=> $b->[1] } @{$aref} ];
    foreach my $c ( @{$aref} ) {
        if ( @{$c} < 3 ) {
            $c = [ $c->[0], [] ];
        }
        else {
            $c = [ $c->[0], _reduce_thread( $c->[2] ) ];
        }
    }
    return $aref;
}