Convert a flat datastructure into a tree

Question

I have an array of hashes. Each element in the array is a node in a hierarchical tree and has referential data for who the parent is. I will have thousands and hundreds of thousands of nodes in the tree... essentially an unknown set of nodes has to be converted to JSON (shown below) for use with http://bl.ocks.org/robschmuecker/7880033

UPDATE: position_id is a node in the heretical tree. placement_id is the parent's position_id (adjacency referential tree).

UPDATE: Here's the full AoH Data::Dumper result with Nested Set and Adjacency result from a modified version of DBIx::Tree::NestedSet (custom).

$VAR1 = [
          {
            'lft' => '673',
            'id' => '109',
            'date_created' => '2015-08-15',
            'level' => '7',
            'user_id' => '13',
            'placement_id' => '11',
            'position_id' => '13',
            'status' => '1',
            'structure_id' => '1',
            'rght' => '684'
          },
          {
            'placement_id' => '13',
            'position_id' => '22',
            'status' => '1',
            'structure_id' => '1',
            'rght' => '679',
            'lft' => '674',
            'date_created' => '2015-08-15',
            'id' => '116',
            'level' => '8',
            'user_id' => '22'
          },
          {
            'user_id' => '101',
            'level' => '9',
            'id' => '200',
            'date_created' => '2015-08-15',
            'lft' => '675',
            'rght' => '676',
            'structure_id' => '1',
            'status' => '1',
            'position_id' => '101',
            'placement_id' => '22'
          },
          {
            'date_created' => '2015-08-15',
            'id' => '201',
            'level' => '9',
            'user_id' => '374',
            'lft' => '677',
            'structure_id' => '1',
            'rght' => '678',
            'placement_id' => '22',
            'position_id' => '374',
            'status' => '1'
          },
          {
            'lft' => '680',
            'user_id' => '95',
            'level' => '8',
            'id' => '117',
            'date_created' => '2015-08-15',
            'status' => '1',
            'position_id' => '95',
            'placement_id' => '13',
            'rght' => '681',
            'structure_id' => '1'
          }
        ];

THIS IS THE GOAL, For this example I need to end up with:

{
    "name": "13",
    "children": [
        {
            "name": "22",
            "children": [
                {
                    "name": "101"
                },
                {
                    "name": "374"
                }
            ]
        },
        {
            "name": "95"
        }
    ]
}

You can also see the format I am trying to arrive at here (minus size): http://bl.ocks.org/robschmuecker/7880033#flare.json

My failed approach(es) included various attempts at looping through the array of hashes to create a recursive Hash of Hashes that can then be used with the JSON Perl module to create the actual JSON I need.

Answer 1

While it was @ikegami who ultimately answered the question that led to the solution. I believe the following adaptation adds 4 important elements/clarifications I found helpful, and thought others reading this question and answer would also find useful.

1- Clear addition of all key,value pairs from the originating AoH to the resulting HOH. See while loop.

2- A Child node counter.

3- Inclusion and use of the encode_json function from JSON

4- The result is also an Array with a Hash as the first element. Newbies (like me) might find the explicit @{$roots}[0] passed to encode_json as helpful.

At first I had a similar adapted solution posted as an UPDATE within my question, but was admonished that it was bad etiquette and instructed to post an answer.

@ikegami's deserves the credit for the core of the solution.

sub get_jsonTree {
    my ($array_of_hashes_ref) = @_;

    my $roots;
    my %recs_by_name;
    my %children_by_parent_name;
    my %count;
    for my $row (@$array_of_hashes_ref) {
        my $name        = $row->{position_id};
        my $parent_name = $row->{placement_id};

        my $rec = {
            name => $name,
        };

        ## Added to loop through all key,value pairs and add them to $rec
        while ( my ($key, $value) = each(%$row) ) {
            $rec->{$key} = $value;
        }

        ##Added To Count Child Nodes
        $count{$parent_name} = 0 if (!$count{$parent_name});        
        $rec->{'child_count'} = $count{$parent_name};
        $count{$parent_name}++;

        push @{ $children_by_parent_name{$parent_name // 'root'} }, $rec;
        $recs_by_name{$name} = $rec;
    }

    $roots = delete($children_by_parent_name{root}) || [];

    for my $name (keys(%children_by_parent_name)) {
        my $children = $children_by_parent_name{$name};
        if ( my $rec = $recs_by_name{$name} ) {
            $rec->{children} = $children;
        } else {
            $util{'test'} .=  "Parent $name doesn't exist.\n<BR>";
            push @$roots, @$children;
        }
    }

    use JSON;
    my $json_str = encode_json(@{$roots}[0]);

    return $json_str;
}

my $array_of_hashes_ref = [
    {  position_id => 123, placement_id => undef },
    {  position_id => 456, placement_id => 123 },
    {  position_id => 789, placement_id => 123 },
    # ...
];

my $json_str = &get_jsonTree($array_of_hashes_ref);

Answer 2

my $data = [
   {  position_id => 123, placement_id => undef },
   {  position_id => 456, placement_id => 123 },
   {  position_id => 789, placement_id => 123 },
   # ...
];

my $roots;
{
   my %recs_by_name;
   my %children_by_parent_name;
   for my $row (@$data) {
      my $name        = $row->{position_id};
      my $parent_name = $row->{placement_id};

      my $rec = {
         name => $name,
      };

      push @{ $children_by_parent_name{$parent_name // 'root'} }, $rec;
      $recs_by_name{$name} = $rec;
   }

   $roots = delete($children_by_parent_name{root}) || [];

   for my $name (keys(%children_by_parent_name)) {
      my $children = $children_by_parent_name{$name};
      if ( my $rec = $recs_by_name{$name} ) {
         $rec->{children} = $children;
      } else {
         die("Parent $name doesn't exist.\n");
         push @$roots, @$children;
      }
   }
}

print(Dumper($roots));

Tested.

You appear to have the depth of each node available to you (level). Simpler code could be used if your data was sorted by increasing depths.