Forum Moderators: coopster
Can anyone help me with a little pseudo-code to recurse through a multi-dimentional array that looks something like this:
array(0 => array('id' => 1, parent => '0', title => 'Green'), 1 => array('id' => 2, 'parent' => 1, 'title' => 'Eggs'), 3 => array('id' => 3, 'parent' => 1, title => 'And'), array('id' => 4, 'parent' => '3', 'title' => 'Ham'))
I just need help with the psedo code, I'm finding it hard to grasp the concept here ane would really appreciate a helping hand to get me going ;)
I'd envisioned (for testing) a list like:
<ul>
<li>Green</li>
<ul>
<li>Eggs</li>
<li>And
<ul>
<li>Ham</li>
</ul>
</li>
</ul>
</ul>
With me?
Many thanks if anyone can see what I mean and help out! ;)
Nick
A few questions first:
Shawn
I'm using PHP. Maybe it would help to explain why I need it:
Let's assume that the whole array comes from one call to MySQL. And what I need to achieve is exactly what I posted above. A nested list in a 'tree-like' structure.
It really seems simple, but then nothing is ever what it seems ;)
Nick
This is the approach I woulkd take, I would not try and implement my own tree unless the available ones had bad performance.
[pre]
function recursor( $array ) {
print "<ul>\n";
foreach( $array as $key => $value ) {
if ( is_array( $value) )
recursor( $value );
else
print "<li>$value</li>\n";
}
print "</ul>\n";
}
[/pre]
(sorry - I don't do pseudocode :))
Will that do?
I assume that your list structure is what you meant, so your array should be:
<snip, my mistake>
Here is some pseudo-code
function main()
{
array $current_list = FindTopElements();
TraverseList($current_list);
}
function FindTopElements()
{
return (select from the database all elements which have parentID = ID);
}
function TraverseList($my_list)
{
print <ul>;
foreach $list_element in my_list
{
print <li>$list_element
array $children = select from the database where parentID = $list_element.ID;
if $children is not empty
{
TraverseList($children)
}
print </li>
print</ul>
}
If you really only want to query the database once then I'd suggest getting it into a tree data structure first. You can't just traverse the list with a for loop and recurse if you find a child, because it is unordered (although your example was not), so the children of a node may not be after the node in your array.
Shawn
<added> Seems I was beaten to the post (must learn to eat quicker).... I think graham's suggestion will only work if the original array was ordered so that all the children of an element appear directly after that element in the array. </added>
[edited by: ShawnR at 12:10 pm (utc) on May 2, 2003]
I'll try the functions in a moment but first, let me ask another question: Is it possible I'm asking the wrong question?
This is for a 'site map' pull-down to determine where a new 'section' of the site should go in the tree. Does that make a difference?
Aspdaddy, sometimes i'm non-to-bright ;)
Good point but I'll tryout the functions above first.
Nick
My take on that is that it is a reasonable question and a reasonable solution, given the way your data is structured in the database. The number of levels in a site map is not likely to run into the 100's or even 10's so using recursion shouldn't be a problem.
However If you had to broaden the question to include advice on the design of the database which holds the structure, then you'd probably get a whole lot more suggestions.
Shawn
I would have noticed in your function but I can't read the damn text untill I paste it ;)
Nick
id ¦ parent ¦ title ¦ desc
Not bothered about overhead at all. It'll only be used on the admin module anyway. And only I use that to add new categories (sections of site).
Nick
Sorry...
Nick
[pre]
$lists =
array(
'cat1' => array(
'cat1.1' => array(
'cat1.1.1',
'cat1.1.2',
),
'cat1.2' => array(
'cat1.2.1',
'cat1.2.2',
'cat1.2.3'
)
),
'cat2' => array(
'cat2.1',
'cat2.2'
)
);
[/pre]
Basically if a category has children then it is an array, otherwise it is a simple value.
Heres a slightly modified version of the function above that deals with this..
[pre]
function recursor( $array ) {
print "\n<ul>\n";
foreach( $array as $key => $value ) {
if ( is_array($value) ) {
print "<li>$key</li>\n";
recursor( $value );
}
else
print "<li>$value</li>\n";
}
print "</ul>\n";
}
[/pre]
Hope thats more useful.
It's simple enough once it's written down but the whole concept was just making my head hurt this morning ;)
Doesn't look to be a resource drain?
Thanks graham, tinkering with it now to get it to do what I need...
Nick
If I'm understanding this correct you want an order list of all your categories having each new sub category indented under it's parent.
At first I figured that one nice big SQL query could solve the problem (I hate to many SQL server round trips they are _VERY_ expensive) but it doesn't look like that's the case.
The simpliest solution is the recursion solution. Start it off with a "select * from tblcat WHERE parent=0 ORDER BY title" (if the root cats have a parent of 0 ofcourse. If not change to suit)
This would get more and more expensive the more levels you have. Because of this and the fact that categories do not change that much I would cache everything to a file so that the next time around you could just do a readfile() which is cheep.
The issue you have now is to know when you need to regenerate the list. This could be done in a global table. Have something like a "last updated" date field. When you use the category manager have it update this field. When you go to display the categories check to see if you cache file is older than that timestamp. If so it needs to be regenerated if not then do readfile().
A slightly better solution in my opinion is to use a timestamp file. I do this since then the categories could still come up incase of an absent database. Rather then updating a global database field have your category manager Touch() a file on your system. Then when you go to show your categories if the timestamp file is newer regenerate. In cases where you cannot connect to the database then just send the cached file. The added advantage to the timestamp solution is that if the categories haven't changed you don't need any SQL server round trip. On a busy site that can make a huge performance difference.
daisho.
So, tell me what's wrong with just fetching the whole set of records (will not likely be more than 100-300 and most likely less than 50) and using Grahams recursor function?
>>readfile() which is cheep.
Now that I LIKE, I would never have thought of it and it's a damn good point. I can use something like that in a number of places in this app. Thanks!
Nick
So, tell me what's wrong with just fetching the whole set of records (will not likely be more than 100-300 and most likely less than 50) and using Grahams recursor function?
That recurtion function will work fine if you can get the array as you have it in msg1. I don't know how you would do this in 1 SQL statememnt since the table recurses on itself and you don't know how many times it happens. That's where omultiple SQLs come in. Might as well do it in the recursive function rather than code to build the array then display the array.
As for the caching I think that's what keeps my site alive and fast. Depending on how you are doing things you may want to look into ob_start, ob_get_contents functions. These function really help in retrofitting a caching system onto a system that's already build.
I've gone a little crazy with it and have 1000's of timestamp files based on ID's in the database then another 3gigs+ of cached content. Though it's all automatic and I could delete it all at anytime with no ill effects other than database queries but my site can still run even if the database is gone which is really what I was aiming for.
Just as a suggestion I created a "cache.php" program at get's included at the first line of a script. Other than that the script does not know it's being cached.
The PEAR classes also have a caching class that is very similar to my implementation. I just came accross it a couple weeks ago but you may want to look into that. It my save you some typing.
daisho.
It does all of that I beileve and is my preferecd template engine...
Nick
Look up CONNECT BY PRIOR (here's some of the basics [lbdwww.epfl.ch])
Unfortunately I don't think MySQL has this feature. :(
But thats why Oracle costs the big bucks.
I have not had experiance with smarty but I did some work with fast template. If you setup a loop in that it would do a regex for every iteration. Really killed performance. Not sure if smarty has that problem though.
daisho.
In this example I just want to put an <optgroup> in for parents but just can't be doen can it...
print("<form method=\"post\" action=\"\">\n");
print("<select name=\"blah\">\n");print(recursor($TheArray));
print("</select\n>");
print("</form>");function recursor( $array ) {
foreach( $array as $key => $value ) {
if ( is_array($value) ) {
recursor( $value );
} else {
switch($key) {
case "id":
print("<option value=\"$value\" >");
break;
case "title":
print("$value</option>\n");
break;
}
}
}
}
Is this what you mean Daisho?
Nick
With the recurtion example you gave why not just add a counter parameter to the function then do:
$buf=str_repeat(" ",$count);
Every recurtion increments this. That way you will get the indentation.
daisho.
I think the code/sql hybrid has to be the best way. Good luck nick.
Working on it now. I already have classes to handle all basic functions like getting one record, getting a records children etc so it shouldn't be rocket science with a bit of luck ;)
Nick
Well, I can get the first set of children but wherever I call the function (within itself) I can't get any deeper?
I appear to be suffering from lack of intelligence again. Assume that the things not explained, do actually work and do exactly what you'd expect them to. (get_children() returns an array of id,title.parent,desc etc...).
Anyone help me spot the gotcha?
function recursor($array) {global $f;
if(is_array($array)) {
foreach($array as $key => $val) {
print($val['title']."<br>\n");
if ($kids=$f->get_children($val['id'])) {
foreach($kids as $kidkey => $kidval) {
print("->".$kidval['title']."<br>\n");
}
}
}
}
}
I just cant see where to call itself?
Many thanks...
Nick
not knowing your class I may do something like:
<?
//Start the ball rolling...
recurse(0,0);
function recurse ($id,$count) {
$result=mysql_query( "SELECT * FROM tblcat WHERE parent=$id ORDER BY title");
while( $row=mysql_query($result,MYSQL_ASSOC) ) {
$padding=str_repeat(" ", $count);
print($padding."->".$row['title']."<br>\n");
recurse($row['id'],$count+1);
}
mysql_free_result($result);
}
?>
If you are going down the path of multiple calls to the DB as per daisho's msg #27, then I still recommend what I had in msg #6. i.e. Bracket the recursive call with an if statement.
The alternative is just get the whole database into a table and do 2 passes through it:
This is pretty similar to how simple compilers work, so if you are interested you can search for something like 'LR parser'.
Shawn
Thanks guys!
Nick
I just read this excellent article on preorder traversal [searchdatabase.techtarget.com] by database guru Joe Celko (author of SQL for Smarties [amazon.com] and several other database books).
Heres a snippet illustrating queries that do what you were looking for..
1. An employee and all their Supervisors, no matter how deep the tree.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = :myemployee;
2. The employee and all subordinates. There is a nice symmetry here.
SELECT P1.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;
How cool is that? No complicated recursion - no flat files - just good code.
Of course the disadvantage is that inserting hurts - but that suits you fine, you'll only be inserting categories occassionally but you'll be querying them a lot!
