in reply to Flat hash to structured

Tame1,

Let's start by saying - you probably don't need recursion to solve this problem. Recursion is nice and it's neat (especially for academic questions) but it can really screw you in the real world. Check out Recursion and subroutine recurse vs goto LABEL for previous discussions. Suffice to say that every problem that can be solved through recursion can also be solved through iteration . Most of the times the recursion solution is more pleasing to view and is easier to follow but at the risk of blowing out stack space after x number of calls into the recursion.

From your description, I believe your initial data structure would look something like this: 

$flat = { 
0 =>   { 'parents'  => undef, 'children' => [2,3,5] },
2 =>   { 'parents'  => [0], 'children' => [20,23] },
3 =>   { 'parents'  => [0], 'children' => [23,30,35] },
5 =>   { 'parents'  => [0],  'children' => [35,50] },
20 =>  { 'parents'  => [2], 'children' => [200,223] },
23 =>  { 'parents'  => [2,3], 'children' => [223,230,233] },
30 =>  { 'parents'  => [3], 'children' => [233,300,335] },
35 =>  { 'parents'  => [3,5], 'children' => [335,350] },
50 =>  { 'parents'  => [5], 'children' => [350,500] },
200 => { 'parents'  => [20], 'children' => undef },
223 => { 'parents'  => [20,23], 'children' => undef },
230 => { 'parents'  => [23],  'children' => undef },
233 => { 'parents'  => [23,30], 'children' => undef },
300 => { 'parents'  => [30],   'children' => undef },
335 => { 'parents'  => [30,35], 'children' => undef },
350 => { 'parents'  => [35,50], 'children' => undef },
500 => { 'parents'  => [50],    'children' => undef },
};

[download]

It seems you have all the info you all ready need to answer any type of "tree" question. I don't see the difference between your $top and $flat and your $item and $child1. Will the flat structure not be completely populated?

You can find, directly, the grandkids of a node by doing something like this: 

$child = 2;
$gks   = @{$flat->{$flat->{$child}{children}[0]}{children}};
print join( ', ',  @$gks ), "\n";

[download]

If you really want to store this data in a tree, check out some of the tree modules on CPAN .

-derby

Replies are listed 'Best First'.
Re: Re: Flat hash to structured
by traveler (Parson) on Dec 27, 2001 at 01:43 UTC
    If I remember from my CompSci classes correctly, this is really a graph, not a tree. So the tree modules may not help. I don't think that trees allow nodes to have multiple parents. I suggest tame1 try the Graph modules or something similar.

    The problem, however, appears to be generating the particular structure tame1 needs. tame1 can you show us what derby's data should conver to in the new structure?

    --traveler

[reply]
      I'll give it a shot:

      Top item has an id number and a Children array. Each item in Children in turn has a Childeren array, and so on and so forth. Each item down the chain also has a Parents array, but instead of complex data, all the Parents array has is the id numbers, in reverse order, of the items above it (all the way to item 1). So ALL item's Parents array will have number 1 as it's last element in the array.

      Again, the Children's array actually holds the children, and so on and so forth ad infinitum.

      The end result is that I will be walking back down the chain, printing item names, etc. and total accumulated work hours for each item (which is in each item). Children of items are moved over 4 spaces, and so on. The "total hours" of each item is the total of it's children's hours plus any work hours done directly on the parent.
      So my end printout will look like:

      Main                                           450
    Project 1                              300
        Sub 1                           150
        Sub 2                           150
    Project 2                               150
        Sub 1                           75
        Sub 2                           75

      [download]

      As you can see, it is cummulative. And, because subs and projects can be "moved" within the main system, I cannot count on numerical order of their id numbers - I must rely on the Parent and Children arrays.

      My employer already has a module which will print this out correctly for me, but it requires a single complex hash as it's input, structured as mentioned above. And no, I cannot use anything else to print it - his module gives correct formatting, bg colors, etc. etc. so he insists I use it.

      Does this help?

      What does this little button do . .<Click>; "USER HAS SIGNED OFF FOR THE DAY"
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom