How do I manipulate this php array to create more dimensions?

I have an ordered array as follows:

$array = array
(	 
	[0] => array
		(
			[id] => 1
			[parent_id] => 0
		)
	[1] => array
		(
			[id] => 2
			[parent_id] => 0
		)
	[2] => array
		(
			[id] => 3
			[parent_id] => 2
		)
	[3] => array
		(
			[id] => 4
			[parent_id] => 2
		)
	[4] => array
		(
			[id] => 5
			[parent_id] => 4
		)
	[5] => array
		(
			[id] => 6
			[parent_id] => 0
		) 
);

Open in new window


How would I loop through this array to reformat it, creating a new 'children' key with an associated array of the children as identified by the 'parent_id' key? The assumption is that the parent/child taxonomy can be infinitely deep, hence a parent could have children, with children, with children etc...

The output should be as follows:

$array = array
(
		 
	[0] => array
		(
			[id] => 1
			[parent_id] => 0
			[children] => 0
		)
	
	[1] => array
		(
			
			[id] => 2
			[parent_id] => 0
			[children] => array
			
				(
								
					[0] => array
						(
					
							[id] => 3
							[parent_id] => 2
							[children] => 0
							
						)
								
					[1] => array
						(
					
							[id] => 4
							[parent_id] => 2
							[children] => array
			
								(
												
									[0] => array
										(
									
											[id] => 5
											[parent_id] => 4
											[children] => 0
											
										)
										
								)
							
						)
						
				)
								
		)

	[2] => array
		(
			[id] => 6
			[parent_id] => 0
			[children] => 0
		)
	 
);

Open in new window

LVL 1
93jordanajAsked:
Who is Participating?
 
Ray PaseurConnect With a Mentor Commented:
See if this makes sense.  It seems OK given the test data.  Not 100% sure about the sanity checks, but I had the feeling that there was some built-in dependency so I noted them in the comments.  Please let me know if you have questions, ~Ray
http://iconoun.com/demo/temp_93jordanaj.php

<?php // demo/temp_93jordanaj.php
error_reporting(E_ALL);
echo '<pre>';

/**
 * SEE http://www.experts-exchange.com/Programming/Languages/Scripting/PHP/Q_28421151.html
 *
 * SANITY CHECKS MAY BE NEEDED...
 *   DO ALL 'parent_id' VALUES EXIST IN 'id' ELEMENTS?
 *   ARE ALL 'id' ELEMENTS UNIQUE?
 *   ARE ALL 'id' VALUES IN ASCENDING ORDER?
 */

// CREATE THE INPUT DATA
$dat = array
( 0 => array( 'id' => 1, 'parent_id' => 0)
, 1 => array( 'id' => 2, 'parent_id' => 0)
, 2 => array( 'id' => 3, 'parent_id' => 2)
, 3 => array( 'id' => 4, 'parent_id' => 2)
, 4 => array( 'id' => 5, 'parent_id' => 4)
, 5 => array( 'id' => 6, 'parent_id' => 0)
)
;
// DOES IT LOOK RIGHT? (YES)
// print_r($inp);

// ASSIGN EMPTY CHILDREN TO EACH OF THE SUB-ARRAYS
foreach ($dat as $key => $sub)
{
    $sub['children'] = 0;
    $dat[$key] = $sub;
}

// COLLAPSE THE ARRAYS INTO PARENT-CHILD RELATIONSHIPS
while ( $xyz = getpid($dat) )
{
    putpid($dat, $xyz);
}

// RENUMBER THE ARRAYS
$dat = array_values($dat);

// SHOW THE WORK PRODUCT
print_r($dat);


// FUNCTION TO EXTRACT FIRST INSTANCE OF LARGEST PARENT-ID
function getPID(&$arr)
{
    $maxpid = 0;

    // LOCATE THE MAX PARENT ID
    foreach ($arr as $key => $sub)
    {
        if ($sub['parent_id'] > $maxpid) $maxpid = $sub['parent_id'];
    }

    // IF THE MAX IS ZERO, WE ARE ALL DONE
    if ($maxpid == 0) return FALSE;

    // REMOVE AND RETURN THE FIRST MATCHING ELEMENT
    foreach ($arr as $key => $sub)
    {
        if ($sub['parent_id'] == $maxpid)
        {
            unset($arr[$key]);
            return $sub;
        }
    }
}

// FUNCTION TO APPEND CHILD TO PARENT
function putPID(&$arr, $child)
{
    foreach ($arr as $key => $sub)
    {
        if ($sub['id'] == $child['parent_id'])
        {
            // APPEND THIS CHILD TO THE PARENT
            if (empty($sub['children']))
            {
                $sub['children'] = array($child);
            }
            else
            {
                $sub['children'][] = $child;
            }
            $arr[$key] = $sub;
            return;
        }
    }
}

Open in new window

0
 
Ray PaseurCommented:
Is this an academic assignment?  What is the context for this question?  It seems very theoretical, and while we all deal with linked lists in college, there are not many applications after engineering school.  Are there any other data elements to consider?  What would the output be used for?

If you can fill in a little more of the context we may be able to find a standard design pattern for something like this.
0
 
93jordanajAuthor Commented:
Thanks for your comment. No, not an academic assignment, it's being used on a real website, hopefully to populate a navigation menu (ul / li). I was trying to simplify the question so apologies if this appears theoretical.

The menu items are being provided in a flat array, i.e as in the first example which has been simplified for this post. This starting point cannot be changed as this is how the data is provided through the api. The menu is currently 3 levels deep, although the user has the option to add more levels if he/she desires.

My intention was to reformat the array into the multidimensional array for easier management when outputting, each branch being a branch in the menu.

I am however exploring other options so there may be better ways to handle this, but this was just the first method I was exploring.

Any suggestions would be appreciated.

As a side note, I could achieve this if I knew the maximum number of possible levels and hard code the for each loops. However, given that the number of levels could be anything, is there a way to loop through for each loops for each instance?

Many thanks.
Alex
0
Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

 
Ray PaseurCommented:
FWIW, PHP JSON processing stops at 500 levels of nesting.  The main reason for this limitation is to prevent run-time failures when there is a nesting loop (not to mention memory leaks).

I'll see if I can cobble something together for you.  If I can come up with a good solution, I'll post a code snippet here.
0
 
93jordanajAuthor Commented:
Ray, thank you so much for this, you've put in a lot of effort and I really appreciate it. I'm going to test this out properly this evening when I get home and will let you know how it goes.

Many thanks,
Alex
0
 
Ray PaseurCommented:
Alex:  OK, please let me know what you find.  My test case using the script above can be seen here (it's a great question):
http://iconoun.com/demo/temp_93jordanaj.php
0
 
hieloCommented:
My suggestion to you is to keep the flat array as it.  Since in theoretically it can be infinitely  deep, then you will need to do recursion to follow the branches until you reach the leaves.

From the description of your problem, my guess is that what you actually need is a "tree" of deeply nested (I am guessing) UL-LI.  From the flat array you can accomplish this task.  Take a look at the following page:

http://stackoverflow.com/questions/14740429/flat-php-array-to-hierarchy-tree (posted by "Code Source").

Regards,
Hielo
0
 
Ray PaseurCommented:
@hielo: The same code set seems to work on the test data posted by "Code Source."  Example here:
http://iconoun.com/demo/temp_93jordanaj_3.php

I believe the author has no choice but to keep the flat array -- that is what comes from the API.

<?php // demo/temp_93jordanaj_3.php
error_reporting(E_ALL);
echo '<pre>';

/**
 * SEE http://www.experts-exchange.com/Programming/Languages/Scripting/PHP/Q_28421151.html
 *
 * SANITY CHECKS MAY BE NEEDED...
 *   DO ALL 'parent_id' VALUES EXIST IN 'id' ELEMENTS?
 *   ARE ALL 'id' ELEMENTS UNIQUE?
 *   ARE ALL 'id' VALUES IN ASCENDING ORDER?
 *   ARE ALL 'id' AND 'parent_id' PAIRS MUTUALLY EXCLUSIVE
 */

// CREATE THE INPUT DATA
$dat = array(
    array('id' =>  1, 'parent_id' =>  0, 'name' => 'Page 1'),
    array('id' =>  2, 'parent_id' =>  1, 'name' => 'Page 1.1'),
    array('id' =>  3, 'parent_id' =>  2, 'name' => 'Page 1.1.1'),
    array('id' =>  4, 'parent_id' =>  3, 'name' => 'Page 1.1.1.1'),
    array('id' =>  5, 'parent_id' =>  3, 'name' => 'Page 1.1.1.2'),
    array('id' =>  6, 'parent_id' =>  1, 'name' => 'Page 1.2'),
    array('id' =>  7, 'parent_id' =>  6, 'name' => 'Page 1.2.1'),
    array('id' =>  8, 'parent_id' =>  0, 'name' => 'Page 2'),
    array('id' =>  9, 'parent_id' =>  0, 'name' => 'Page 3'),
    array('id' => 10, 'parent_id' =>  9, 'name' => 'Page 3.1'),
    array('id' => 11, 'parent_id' =>  9, 'name' => 'Page 3.2'),
    array('id' => 12, 'parent_id' => 11, 'name' => 'Page 3.2.1'),
    )
;
// DOES IT LOOK RIGHT? (YES)
// var_dump($dat);

// ASSIGN EMPTY CHILDREN TO EACH OF THE SUB-ARRAYS
foreach ($dat as $key => $sub)
{
    $sub['children'] = 0;
    $dat[$key] = $sub;
}

// COLLAPSE THE ARRAYS INTO PARENT-CHILD RELATIONSHIPS
while ( $xyz = getpid($dat) )
{
    putpid($dat, $xyz);
}

// RENUMBER THE ARRAYS (MAY NOT BE NEEDED)
$dat = array_values($dat);

// SHOW THE WORK PRODUCT
print_r($dat);


// FUNCTION TO EXTRACT FIRST INSTANCE OF LARGEST PARENT-ID
function getPID(&$arr)
{
    $maxpid = 0;

    // LOCATE THE MAX PARENT ID
    foreach ($arr as $key => $sub)
    {
        if ($sub['parent_id'] > $maxpid) $maxpid = $sub['parent_id'];
    }

    // IF THE MAX IS ZERO, WE ARE ALL DONE
    if ($maxpid == 0) return FALSE;

    // REMOVE AND RETURN THE FIRST MATCHING ELEMENT
    foreach ($arr as $key => $sub)
    {
        if ($sub['parent_id'] == $maxpid)
        {
            unset($arr[$key]);
            return $sub;
        }
    }
}

// FUNCTION TO APPEND CHILD TO PARENT
function putPID(&$arr, $child)
{
    foreach ($arr as $key => $sub)
    {
        if ($sub['id'] == $child['parent_id'])
        {
            // APPEND THIS CHILD TO THE PARENT
            if (empty($sub['children']))
            {
                $sub['children'] = array($child);
            }
            else
            {
                $sub['children'][] = $child;
            }
            $arr[$key] = $sub;
            return;
        }
    }
}

Open in new window

0
 
hieloCommented:
>>I believe the author has no choice but to keep the flat array -- that is what comes from the API.
Exactly.  But what I am saying is that it seems to me that the author is trying to find an easy way to construct deeply nested UL/LI menus.  If that is the case, then there is no need/point to creating "children" sub-arrays.

Yes, I can see that the code you posted does what the author originally asked for, but on his second post the author wrote:

I am however exploring other options so there may be better ways to handle this, but this was just the first method I was exploring.

Your code addresses the "Underlined" portion.  I am addressing the "Bold" portion of the quote.  I really don't see the point in creating those sub-arrays if all he/she wants is to created deeply nested menus.  He/She is unnecessarily consuming memory (by constructing "children" sub arrays) for a data structure that will ultimately require recursion to traverse anyway.

Regards,
Hielo
0
 
Ray PaseurCommented:
Agreed that it would be interesting to see the "real" data to see if the abstracted portion included in this question has removed anything that affects the desired outcome!
0
 
93jordanajAuthor Commented:
Ray, thanks again for your help. I've been testing this and it seems to do exactly what I need it for so thank you very much. There may be some instances where the initial array is a multidimensional array, for which I've not tested yet, but I believe I'll be able to use this as a basis for any future changes and it certainly dos what I need for the current implementation.

@Hielo thanks for your comments. I am exploring several options and appreciate your feedback. Ray's help has allowed me to implement this part of the project, but I will take on board what you have said for the optimisation stage and any future projects.
0
 
Ray PaseurCommented:
Thanks for the points and for your kind words.  I've tested this with the id values in random order and it still seems to produce reasonable output.  Best of luck with your project, ~Ray
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.