What I mean by "re-order" is as follows. I have a set of data that I am parsing into a tree. The data is hierarchical but not position-sensitive (meaning that in what I am parsing the ordering at a particular level does not matter, just that the data is present {so b,e, and c, can as easily appear as b,c, and e}). I want to re-organize the data so that I can easily "dump" the data in a particular ordering (to diff, for example). For instance,

Original data
 
Desired re-ordered data

a      
  b    
  e    
    f  
      g
  c    
    d  
h      
  i    
    j  


 
a
  b
  c
    d
  e
    f
      g
h
  i
    j

At the moment, my test code (minus a way to re-order the data) is:

#!/usr/bin/perl

use strict;
use warnings;

use Tree::DAG_Node;

$| = 1;

my @test_data = (
    'a',          #
    '  b',        #
    '  e',        #
    '    f',      #
    '      g',    #
    '  c',        #
    '    d',      #
    'h',          #
    '  i',        #
    '    j',      #
);

my $indent_width = 0;
my $idw = get_indent_width( { td => [@test_data], } );

my $nc = 0;
my $tree =
  Tree::DAG_Node->new(
    { name => 'root', attributes => { nc => $nc++, top_foo => 1, }, },
  );
foreach my $i ( 0 .. $#test_data ) {
    my $target = $tree;
    my $line   = $test_data[$i];
    $line =~ m/^(\s*)(.*)$/msx;
    my ( $indent, $text, ) = ( length $1, $2, );
    my $indent_depth = $indent / $idw;
    while ($indent_depth) {
        if ( $target->is_root ) {
            my @daughter = $target->daughters;
            $target = $daughter[-1];
        }
        else {
            my @sister = $target->daughters;
            $target = $sister[-1];
        }
        $indent_depth--;
    }
    if ( !defined $target ) {
        $tree->new_daughter( 
          {
            name => $text, 
            attributes => { nc => $nc++, }, 
          },
        );
        next;
    }
    $target->new_daughter( 
      { 
        name => $text, 
        attributes => { nc => $nc++, }, 
      },
    );
}

# print $tree->dump_names, "\n";
$tree->walk_down(
    {
        callback => sub {
            my $attr = $_[0]->attributes;
            print sprintf "%5s %7s (%-12s): { %s }\n",
              $_[0]->name,
              ref $_[0]->attributes, 
              $_[0]->address, 
              join( ", ",
                  map  { "$_ => $attr->{$_}"; }
                  sort { $a cmp $b } keys %{$attr}
              );
        }
    }
);

#
# Subroutines
#
sub get_indent_width {
    my ($param) = shift;
    my @td = $param->{td};
    my %found_indent;
    foreach my $i ( 0 .. $#test_data ) {
        my $line = $test_data[$i];
        $line =~ m/^(\s*)(.*)$/msx;
        my ( $indent, $text, ) = ( length $1, $2, );
        $found_indent{$indent}++;
    }
    my @fi = grep { $_; } sort { $a <=> $b } keys %found_indent;

    while ( scalar(@fi) > 1 ) {
        my $n1 = shift @fi;
        my $n2 = shift @fi;
        my $n3 = gcd( sort { $a <=> $b } ( $n1, $n2, ), );
        push @fi, $n3;
    }

    $indent_width = $fi[0];
}

sub gcd {
    my ( $n1, $n2, ) = @_;
    if ( $n2 == 0 ) {
        return $n1;
    }
    return gcd( $n2, $n1 % $n2, );
}

sub lcm {
    my ( $n1, $n2, ) = @_;
    if ( $n1 == 0 and $n2 == 0 ) {
        return 0;
    }
    return abs( $n1 * $n2 ) / gcd( $n1, $n2, );
}
[download]

Sample output:

 root    HASH (0           ): { nc => 0, top_foo => 1 }
    a    HASH (0:0         ): { nc => 1 }
    b    HASH (0:0:0       ): { nc => 2 }
    e    HASH (0:0:1       ): { nc => 3 }
    f    HASH (0:0:1:0     ): { nc => 4 }
    g    HASH (0:0:1:0:0   ): { nc => 5 }
    c    HASH (0:0:2       ): { nc => 6 }
    d    HASH (0:0:2:0     ): { nc => 7 }
    h    HASH (0:1         ): { nc => 8 }
    i    HASH (0:1:0       ): { nc => 9 }
    j    HASH (0:1:0:0     ): { nc => 10 }
[download]