3

我有一系列路径

C:\A
C:\B\C
D:\AB

我想把这些放在哈希数组树中，这样我就可以在 TT2 模板中浏览它们。

我的意思是这样的：

@dirs = [
          {
            name => "C:",
            subs => [
                      {
                        name => "A",
                        subs => [],
                      },
                      {
                        name => "B",
                        subs => [
                                  {
                                    name => "C",
                                    subs => [],
                                  }
                                ],
                      }
                    ]
          },
          { 
            name => "D:",
            subs => [
                      {
                        name => "AB",
                        subs => [],
                      }
                    ],
          }
        ]

我也知道我可能在这里做 Brainderp，所以我对其他方法持开放态度，唯一的要求是将路径列表转换为可以使用 TT2 模板工具包重建为树的东西。

还有那个结构叫什么？我只是想到了哈希数组树，但我敢打赌这是错误的。

4

3 回答 3

3

这是一个非常简短的方法。请注意，这只能如此简单，因为我将您的数据格式更改为与您的树结构完全匹配的哈希哈希。请参阅下面的代码以将结果结构转换为您的结构。

my $tree = {root => {}};
foreach my $input (<DATA>) { chomp $input;
    my $t = $tree;
    $t = $t->{$_} //= {} for split /\\/ => $input;
}

use Data::Dumper; print Dumper $tree;

__DATA__
C:\A
C:\B\C
D:\AB
C:\B\A
C:\B\A\C

输出：

$VAR1 = {
          'C:' => {
                    'A' => {},
                    'B' => {
                             'A' => {
                                      'C' => {}
                                    },
                             'C' => {}
                           }
                  },
          'D:' => {
                    'AB' => {}
                  }
        };

要将此数据结构转换为您的数据结构，只需使用以下代码：

sub transform {
    my $tree        = shift;
    my @children    = ();
    while (my ($name, $children) = each %$tree) {
        push @children, {
            name => $name,
            subs => [ transform($children) ],
        }
    }
    return @children;
}

my $AoH_tree = {name => 'root', subs => [transform($tree)] };

完毕。:) 对于具有更多糖、功能和可读性但更多 LOC 的完全不同的方法，请参阅我的其他答案。

于 2012-11-03T12:37:46.557 回答
2

这是一个更长但更具可读性和更舒适的解决方案。您不必（并且可能不想）使用它，但也许它可以帮助（不仅是您）了解更多关于不同方法的信息。它为树节点引入了一个小的Moo类，它可以通过可读的排序和字符串化方法递归地为其自身添加名称。

编辑：对于完全不同且极短的替代方案，请参阅我的其他答案。我把它分成两个答案，因为它们是完全不同的方法，而且这个答案已经足够长了。;)

树类

请注意，这基本上只不过是您的嵌套 AoHoAoH... 结构 - 添加了一点点糖。;)

# define a tree structure
package Tree;
use Moo; # activates strict && warnings
use List::Util 'first';

# name of this node
has name => (is => 'ro');

# array ref of children
has subs => (is => 'rw', isa => sub { die unless ref shift eq 'ARRAY' });

现在在基本准备之后（我们的对象有一个标量name和一个数组 ref subs），我们来到这个答案的主要部分：递归add_deeply方法。请注意，从这里开始，一切都反映了数据结构的递归性质：

# recursively add to this tree
sub add_deeply {
    my ($self, @names)  = @_;
    my $next_name       = shift @names;

    # names empty: do nothing
    return unless defined $next_name;

    # find or create a matching tree
    my $subtree = first {$_->name eq $next_name} @{$self->subs};
    push @{$self->subs}, $subtree = Tree->new(name => $next_name, subs => [])
        unless defined $subtree;

    # recurse
    $subtree->add_deeply(@names);
}

以下两种方法并不重要。基本上他们在这里是为了使输出漂亮：

# sort using node names
sub sort {
    my $self = shift;
    $_->sort for @{$self->subs}; # sort my children
    $self->subs([ sort {$a->name cmp $b->name} @{$self->subs} ]); # sort me
}

# stringification
use overload '""' => \&to_string;
sub to_string {
    my $self    = shift;
    my $prefix  = shift // '';

    # prepare
    my $str = $prefix . '{TREE name: "' . $self->name . '"';

    # stringify children
    if (@{$self->subs}) {
        $str .= ", children: [\n";
        $str .= $_->to_string("    $prefix") for @{$self->subs};
        $str .= "$prefix]";
    }

    # done
    return $str . "}\n";
}

如何使用这个

现在是简单的部分。只需阅读输入（从__DATA__这里）和add_deeply：

# done with the tree structure: now use it
package main;

# parse and add names to a tree
my $tree = Tree->new(name => 'root', subs => []);
foreach my $line (<DATA>) {
    chomp $line;
    $tree->add_deeply(split /\\/ => $line);
}

# output
$tree->sort;
print $tree;

__DATA__
C:\A
C:\B\C
D:\AB
C:\B\A
C:\B\A\C

输出：

{TREE name: "root", children: [
    {TREE name: "C:", children: [
        {TREE name: "A"}
        {TREE name: "B", children: [
            {TREE name: "A", children: [
                {TREE name: "C"}
            ]}
            {TREE name: "C"}
        ]}
    ]}
    {TREE name: "D:", children: [
        {TREE name: "AB"}
    ]}
]}
于 2012-11-03T11:57:38.540 回答
1

我做了一个复杂的哈希结构来跟踪已经放置的节点，然后我做了这个。更多步骤，但代码更精简。

while ( <> ) {
    chomp;
    my $ref = \@dirs;
    foreach my $dir ( split /\\/ ) {
        my $i = 0;
        $i++ while ( $ref->[$i] and $ref->[$i]{name} ne $dir );
        my $r = $ref->[$i] ||= { name => $dir, subs => [] };
        $ref  = $r->{subs};
    }
}
于 2012-11-02T20:00:32.237 回答