I've tried to implement a tree with variable number of children for each
node.The data for the tree is written as tuples of the form (child,parent)
and there is code for parsing that data and entering it into the tree
First a root for the tree is found,that is inserted first in the tree.
After that all the other nodes are inserted.
The code works,but I would like your oppinion on it and suggestions on how to optimise it.

#!/usr/bin/perl 
#=====================================================================
+==========
#
#         FILE:  test.pl
#
#        USAGE:  ./test.pl 
#
#  DESCRIPTION:  
#
#      OPTIONS:  ---
# REQUIREMENTS:  ---
#         BUGS:  ---
#        NOTES:  ---
#      COMPANY:  
#      VERSION:  1.0
#      CREATED:  01/27/2008 03:11:51 AM EET
#     REVISION:  ---
#=====================================================================
+==========

use strict;
use warnings;
use Data::Dumper;
my $tree;
my $s = "f b, b c, a c, e b, d a, g a";
my @tuples = map{ 
    my @tuple=split ' ',$_; 
    {
        child    => shift @tuple,
        parent    => shift @tuple,
    };  
} 
    split ',',$s;
sub insert_node {
    my ($root,$parent,$child) = @_;
    foreach my $node (@$root) {
        foreach my $child_of_root (@{ $node->{children} }) {
            my $retval = insert_node([$child_of_root],$parent,$child);
            return $retval if $retval eq 1;
        };
        if($node->{node} eq $parent){
            # if we've found our parent then
            # put the node to be inserted as its child
            push @{ $node->{children} },
            {
                node    =>$child,
                children=>[],
            };
            return 1;
        };
        if($node->{node} eq $child) { 
            # if the current node is the child of the node to be inser
+ted
            # then replace the name of the current node with the paren
+ts name
            # and put the old current node as its child
            my $old_node     = { 
                node        =>$node->{node},
                children    =>$node->{children}  
            };
            $node->{node} = $parent;
            $node->{children} = [$old_node];
            return 1;
        }
    };
    #after the loop has ended if we arrive here
    #it means that there is no right place for the node to be
    #so we return it and append it to the tuples if we haven't
    #found a right place for it this moment we will in the future
    #but until the program ends
    return 0;
}

sub find_root { 
    # this finds the root of the tree by progressively going from pare
+nt to its parent and so forth
    my $count = scalar @tuples;
    my $root=$tuples[0]->{parent};
    my $temp;
    $temp->{$_->{child}} = $_->{parent} 
        foreach @tuples;
    while(exists $temp->{$root}) {
        $root=$temp->{$root};
    }
    return $root;
}


$tree= [ { node => find_root(),children=>[]} ]; #build the tree with o
+nly one node,namely the root
foreach(@tuples) {#add progressively nodes to the tree
    my $retval = insert_node($tree,$_->{parent},$_->{child}) ;
    warn $retval;
    unless($retval) {
        #because insert_node did not find a proper place for that node
        #we pre-pend it to the @tuples array for later insertion
        push @tuples,$_;
    };
};


print Dumper($tree);
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.