PHP - help with recursion

feenster99 · 16 Feb 2006 at 21:36

Hi folks,
I think this is an easy one, but its the first time I have attempted recursion.

I have a MySQL table that stores items for a menu. It has the following fields:
- id
- depth
- left_id
- right_id
- title

So I have entered the data (manually at the moment, but will be automated eventually), and they look like this when selected into an array:

Code:

Array
(
    [0] => Array
        (
            [id] => 1
            [depth] => 0
            [left_id] => 0
            [right_id] => 2
            [title] => Home
        )

    [1] => Array
        (
            [id] => 2
            [depth] => 0
            [left_id] => 1
            [right_id] => 4
            [title] => News
        )

    [2] => Array
        (
            [id] => 4
            [depth] => 1
            [left_id] => 2
            [right_id] => 5
            [title] => Archive
        )

    [3] => Array
        (
            [id] => 5
            [depth] => 2
            [left_id] => 4
            [right_id] => 3
            [title] => Really old stuff
        )

    [4] => Array
        (
            [id] => 3
            [depth] => 0
            [left_id] => 5
            [right_id] => 0
            [title] => Contact us
        )
)

This should produce a menu structure of:

Code:

- Home
- News
-- Archive
--- Really old stuff
- Contact us

Can anyone create a simple recursive function to generate that structure from the above array?

Cheers,
Matt

daz · 16 Feb 2006 at 21:56

Why not use an iterative function?

feenster99 · 16 Feb 2006 at 21:58

Because there is no specified limit to the depth the menu could go. It could be 2 levels deep or it could be 20

Matt

jamesrw · 16 Feb 2006 at 22:22

I'm not sure the whole left_id, right_id thing is the correct way to go about it? Why not try having a parent / child thing going on?

Dj_Jestar · 16 Feb 2006 at 22:24

Code:

<?php

function ArrayDepthList ($array, $indent = 0, $spacer = '-') 
{
    $output = '';
    $spacerOut = '';
    
    for ($i = 0; $i < $indent; $i++) {
        $spacerOut .= $spacer;
    }
    
    foreach ($array as $arr) {
        if (is_array($arr)) {
            $output .= ArrayDepthList($arr, $indent + 1, $spacer);
        } else {
            $output .= $spacerOut . $arr . "\n";
        }
    }
    
    return $output;
}

echo ArrayDepthList(array(1,1,1,array(2,2,2,2,array(3,3,3,3),2,2,2),1,1,1));

?>

Will give you something to work with.

feenster99 · 16 Feb 2006 at 22:36

jamesrw said:
I'm not sure the whole left_id, right_id thing is the correct way to go about it? Why not try having a parent / child thing going on?

Yeah, im not sure it offers anything either to be honest - was something new I was trying. However, I don't see that having a parent_id offers me a great advantage though to be honest. The problem is that when iterating through the array, it doesn't know whether an ID has children or not. It goes something like this:

- look at item
- add to array
- move to next item
- does item have a parent?
- if yes - Damn, go back a step and add it to the children list!
- if no - Move onto the next

I wonder if I would be better doing the sorting from the end of the array and working upwards? That way, I would know if an item had a parent, so could pass its ID onto the next iteration of the loop to be attached to its parent.

Blimey this hurts my head :S

DJ_Jestar - thanks for the code. The problem is, your array is already sorted into a parent/children relationship - thats the stage I am trying to get to.

Cheers,
Matt

sloth · 16 Feb 2006 at 22:37

Why not just extract it from the DB in the correct order? Ie, ORDER BY left_id ASC. Then when you're looping through your result set, use depth to determine how to pad it. I certainly can't see the need for right_id in addition to left_id.

A simple structure for this menu...

- Home
- News
-- Archive
--- Really old stuff
- Contact us

... would be:

Code:

Name		Order	Depth
Home		1	0
News		2	0
Archive		3	1
Really old...	4	2
Contact Us	5	0

The query to get the stuff out in order:

Code:

SELECT Name, Order, Depth
FROM TableName
ORDER BY [Order]

And the PHP to output it all:

Code:

$PadString = "»";
$Output = "";

for ($i == 0; $i < Len($Results); $i++)
{
	for ($x == 0; $x < $Results[$i]["Depth"]; $x++)
	{
		$Output .= $PadString;
	}
	$Output .= $Results[$i]["Name"]."<br />\n";
}

Probably simpler to maintain than trying to keep left_id and right_id in sync. As jamesrw suggested, parent + child stuff would be the *better* way to do it, but would mean recursive coding, which can be a lot of extra effort.

Note the code is off the top of my head, so most will contain errors.

feenster99 · 16 Feb 2006 at 22:51

What sort of table structure would you suggest for a parent/child menu then? I think this left_id and depth stuff is heading in the wrong direction.

Any suggestions?

Matt

Gman · 16 Feb 2006 at 23:27

in the past i've had a table structure of

menu_name | Parent

For menu items at the top level you set it to a parent of 0
then for any sub menu items you give it the id of its parent.

But I think I used this for a 2 level menu system but I dont see why it can't handle multiple parent levels

Dj_Jestar · 16 Feb 2006 at 23:35

In that case, daz hit the nail on the head.. Iterative loop..

Code:

<?php

$array = Array
(
    Array
        (
            'id' => 1,
            'depth' => 0,
            'left_id' => 0,
            'right_id' => 2,
            'title' => 'Home',
        ),

    Array
        (
            'id' => 2,
            'depth' => 0,
            'left_id' => 1,
            'right_id' => 4,
            'title' => 'News',
        ),

    Array
        (
            'id' => 4,
            'depth' => 1,
            'left_id' => 2,
            'right_id' => 5,
            'title' => 'Archive',
        ),

    Array
        (
            'id' => 5,
            'depth' => 2,
            'left_id' => 4,
            'right_id' => 3,
            'title' => 'Really old stuff',
        ),

    Array
        (
            'id' => 3,
            'depth' => 0,
            'left_id' => 5,
            'right_id' => 0,
            'title' => 'Contact us',
        )
);

foreach ($array as $arr) {

    $spacer = '-';
    $spaceOut = $spacer;
 
    for ($i = 0; $i < $arr['depth']; $i++) {
        $spaceOut .= $spacer;
    }
    
    echo $spaceOut . $arr['title'] . "\n";

}
    
?>

outputs:

Code:

>E:\PHP\php.exe -q test2.php
-Home
-News
--Archive
---Really old stuff
-Contact us
>Exit code: 0    Time: 0.325

feenster99 · 16 Feb 2006 at 23:42

Thanks again - that is great, but I need them in an array which is what is causing me such trouble. E.g., I need this as my output, which I don't think is doable with your code:

Code:

array(
	[0] = array(	"id"	=> "1",
			"title" => "Home",
			"depth" => "0",
			"parent"=> "0");

	[1] = array(	"id"	=> "2",
			"title" => "News",
			"depth" => "0",
			"parent"=> "0",
			"children" =>
				[2] = array(	"id"	=> "3",
						"title" => "Archive",
						"depth" => "1",
						"parent"=> "2");
		);

)