[RESOLVED] recursive function

cgraz

I have a db table that returns an array with two keys: id and below_page. This is for a navigation menu where id is the page id and below_page is that page's parent. if there is no parent, below_page is empty.

What I'm trying to do is somehow recursively loop through my array and build a menu array in the form

$menu = array( 
'id1' => 'id1',
'id2' => array(
     'id3' => 'id3'
    'id 4' => 'id4'
    ),
'id5' => 'id5');

and so forth.

Basically all the keys and values equal the page id, and if the page has children, the value is an array containing the children.

I've tried for hours now creating recursive array searches, loops, and I'm completely stuck. Any help would be appreciated.

Weedpacket

Um; I think I see what you're getting at: could you provide the corresponding database records that would produce that example array? (And use different strings for the keys and values, please; I'll just be confusing myself otherwise🙂)

bradgrafelman

$menu_array = array();
while($result = mysql_fetch_assoc($query)) { // see comment #1

if($result['below_page'] == null) { // see comment #2
    $menu_array[$result['id']] = $result['id'];
} else {
    $menu_array[$result['below_page']][$result['id']] = $result['id'];
}

}

Comment#1: It sounds like you can already form the query, so my code snippet is basically starting after the query is formed & executed. Replace $query with the resource returned from the MySQL query.

Comment #2: Using a loose comparison, 0 would be equal to null, so if the below_page can be 0, you might need a strict comparison here... I just wasn't sure how PHP dealt with empty fields in a MySQL result set, so I used a loose comparison here.

NOTE: Code is untested, so this may not be what you want. In fact, knowing me, it probably isn't :p

cgraz

Thanks for the reply.

Database ix_users
id
below_page
sort_weight

The array I am hoping to achieve would look something like this:

<?php

$menu = array (
   'index' => 'index'
   'company' => 
            array (
               'overview' => 'overview',
               'management' => 'management',
               'careers' => 'careers'
            ),
   'solutions' => 
            array (
               'information-technology' => 
                        array (
                           'business-processes' => 'business-processes',
                           'network-strategy' => 'network-strategy',
                           'vpns' => 'vpns',
                           'network-security' => 'network-security'
			)
		'site-development' =>
			array (
			   'internet-strategies' => 'internet-strategies',
			   'web-sites' => 'web-sites',
			   'intranets' => 'intranets',
			   'content-management' =>
                                    array (
                                       'benefits' => 'benefits',
				       'features' => 'features',
				       'pricing' => 
                                                array (
                                                   'packages' => 'packages',
                                                   'specials' => 'specials'
						)
			   'seo' => 'seo'
			)
		)
)

Basically, it just assigns the id as the key and value. If there happens to be a child, then the value becomes an array. Each child is just an array of it's parent with the key value pair just being the id.

Hopefully this makes some more sense. I'm trying to get this to work with a single query (if possible); I'm looking to avoid running query after query in a loop. I initially had this done with a self join but had some problems and now I'm back at square 1.

cgraz

Thanks for the reply brad. The only problem with your suggestion is that I need some sort of recursion to build my array, otherwise, I'll only be building two levels deep.

I appreciate the help though. I'm going to continue on with this and see if I get anywhere...

bradgrafelman

Yeah, I realized that after you posted your example.

I guess I just don't understand how the "below_page" thing works. Does every menu item have some unique identifier? If so, you could probably use the "ArraySearchRecrusive" function found on the man page for [man]array_search/man to find the path of the "parent" key of each id, and then you'd add the row inside that key's value.

cgraz

okay, here's where I'm at with this:

I decided to try the following method:

Execute the query
Load the top level items into an array $items (these are the pages where below_page is empty)
Load children into arrays in the format

$children['parent']['page_id'] = page_id

This way, each page that is a parent (regardless if that page is a child of another) is set in this format.

Run BuildNav function; recursive.

Loops through parents and checks for children in the children array. If children are found, assigns, merges them to the tree array (which should contain the running total..all navigation). then starts over except now it's checking recursively if the children have children.

In logic it loops through each array of children as they are added and tacks their children on. At the end of the function, it returns the tree.

What I'm having trouble with (I believe) is merging everything into the tree array. I think my function needs some minor changes to work. I think in logic this makes sense, and should work.

I'm going to continue on, and if anyone has any suggestions i would REALLY appreciate it 😉

$res = db_fetch_array( "SELECT id, below_page FROM ix_page WHERE include != 'no' ORDER BY sort_weight DESC");

for( $i=0; $i<count($res); $i++ )
{
	if( empty( $res[$i]['below_page'] ) )
	{
		// Top Level Item
		$items{$res[$i]['id']} = $res[$i]['id'];
	}
	else
	{
		// Children
		$children{$res[$i]['below_page']}[$res[$i]['id']] = $res[$i]['id'];
	}
}

function BuildNav2( $items = array(), $children = array() ) 
{
	$array = !is_array($items) ? array($items) : $items;

// Loop through current array
foreach( $items as $key => $value )
{
	// If this page has children
	if( isset( $children{$key} ) )
	{
		// Add children to array
		$items[$key] = $children{$key};

		// Merge everything into the tree array
		$tree = array_merge_recursive2( $tree, BuildNav2( $items[$key], $children ) );
	}
}

return $tree;
}

// Print the results
print_r( BuildNav2( $items, $children ) );

cgraz

Okay, I got this to work using eval( ). (Question to follow)

What I did is put this into a class, and keep track of the array by setting the values rather than trying to merge the arrays together on each recursive call.

Then what I do is keep track of the current location, so I form a string that looks like this:

$str = '$this->tree' . $location . '[\'' . $key . '\']' . ' = $children{$key};';

Where $location is a string that looks like this:

['solutions']['site-development'] etc

Then I eval $str, and it basically sets the array value of $this->tree. At the end of the function, I can access $this->tree - my entire navigation tree.

My question is this: what are the security implications of doing this? I realize I am using eval(), however, I am only eval()'ing the page ID's. Granted, the user of my CMS has access to specify the page id, and this could be a vulnerability as they could stick some PHP code in there.

However, what if I added form validation that prohibited them from inputting certain characters as the page id. I'll need some help coming up with these, but they may include

;

'
\
/
(
)

Basically, only allow text and - or _, not even spaces will be allowed.

By doing this, can I rest assured that I'm not going to be exploited, or is there something I'm missing?

Also, is this a fairly efficient way of managing my navigation? It seems better than nested queries, and the recursive call should be pretty fast. I doubt many sites will have more than 100 pages, and even that is a stretch!

bradgrafelman

If the only thing you're eval'ing that contains user-contaminated data is the ID.. why not use something like [man]ctype_alnum/man to make sure they entered alphanumeric characters only?

cgraz

I could add in additional verification, but my main concern is ensuring the db holding the page_id only contains alphanumeric characters and - or _.

I assume since that will be the only think I'm eval()'ing, it shouldn't be a security risk?

bradgrafelman

Yeah... if the page ID is the only variable that depends on user-given information (and if register_globals is off.. but I'm sure you've covered that :p) then I would say sanitize that and you're fine.

Going on those parameters, you could do a simple preg_match:

if(preg_match('/[^a-z0-9_-]/i', $page_id)) {
    die('Error: Invalid characters detected!');
}

etc.

cgraz

sounds good. Thanks for all your help. This was officially a nightmare!