[PERL] Построитель дерева на Perl

Yevgen
Дата: 23.08.2006 15:13:52
Проблема такая. Есть список имен функций, которые нужно выполнить каким-то образом. У этих функций есть зависимости, т.е. каждая функция должна быть выполнена либо переда какими-то функциями, либо после, либо и то, и другое. Может случиться ситуация, когда она не имеет таких ограничений, тогда ее можно выполнить в любой момент. Нужно построить дерево, которое определяло бы последовательность выполнения функций. Причем, если функции B и C должны обязательно выполняться после функции A, то ветвь дерева должна выглядеть не так A -> B -> C, а так :
A--------> B
|-------->C

Т.е. это будет не одна сплошная ветвь, а две параллельные, выходящие из вершины A. Корней у дерева может быть несколько в том случае, если функция не имеет условий, что должна быть выполнена до или после каких-то др. функций.

Значит так, имеем такой пакет с объявлением элемента дерева:
package tree;

my %fields = (
val => undef, #Value
child => undef, #Childs
);

sub new {
my $classname = shift;
my $self = {%fields,};
bless($self,$classname);
$self->{val} = shift;
return $self;
}

sub AddNode {
my $self = shift;
my $new_node = shift;
push(@{$self->{child}}, $new_node);
}

__END__

Имеем построитель дерева:
package tree_builder;

use tree;

my %fields = (
tree => undef, #tree
bv => undef, #List with the variants of the inserions

);

sub new {
my $classname =shift;
my $self = {%fields,};
bless($self,$classname);
$self->{tree} = new tree(0);
return $self;
}

sub ClearTree {
my $self = shift;
$self->{tree} = undef;
}

sub MakeTree {
my $self = shift;
my $afns = shift;
my @fns;
my $i;
my $status;

@fns = keys %{$afns};
foreach $i(@fns)
{
#Forming a new node with pointer to a hash elemnt wich contains API-command description
my $node = tree(\%{$afns->{$i}});
$status = $self->GetConstStatus(\%{$afns->{$i}});
SWITCH: {
if($status == 0) {
$self->{tree}->AddNode($node);
last SWITCH;
}
if($status == 1) {
last SWITCH;
}
if($status == 2) {
last SWITCH;
}
if($status == 3) {
last SWITCH;
}
}

}
print "";
}

sub GetConstStatus {
my $self = shift;
my $fn = shift;

if(!defined $fn->{after} && !defined $fn->{before})
{
return 0;
}
if(defined $fn->{after} && !defined $fn->{before})
{
return 1;
}
if(!defined $fn->{after} && defined $fn->{before})
{
return 2;
}
if(defined $fn->{after} && defined $fn->{before})
{
return 3;
}
}

__END__

В подпрограмму MakeTree передаю хэш с функциями $afns, где ключи - номера функции $i ($afns->{$i}). Каждая функция имеет свойство name ($afns->{$i}->{name}) и массивы after и before (@{$afns->{$i}->{after}} и @{$afns->{$i}->{before}}), где содержатся соответственно списки функций после и до которых должна выполняться данная функция. Если функция не имеет таких условияй, то указатели на эти массивы равны null или, что то же самое, не определены.

Цель: написать подпрограмму, которая будет добавлять новые вершины $afns->{$i} в дерево согласно спискам функций @{$afns->{$i}->{after}} и @{$afns->{$i}->{before}}.

Люди, срочно нужна помощь! Помогите дописать построитель дерева. Или, если у кого уже есть готовый, то поделитесь.

Заранее спасибо.