...

View Full Version : recursion help



b_hole
06-07-2007, 08:19 AM
I have data stored in the following method:
id, father_id, level, order & data.

What I'm trying to do is to display the data in a nested list, like this:

<ul>
<li>aa</li>
<li>ab
<ul>
<li>aba</li>
<li>abb</li>
</ul>
</li>
<li>ac
<ul>
<li>aca</li>
<li>acb</li>
<li>acc</li>
</ul>
</li>
<li>ad</li>
</ul>
But no matter what, I can't think of a way to accomplish this. I think the best way I can order the data inside the SELECT is like this:

order by `type` asc, `level` asc, `order` asc
And then maybe move the recordset into an array?

* I don't want to involve JS here, just server-side in PHP (using MySQL as my DB).

Any guiding will be appreciated :)

ralph l mayo
06-07-2007, 09:42 AM
It's not possible to use the order clause to get data from that table structure in the correct order in a general (abritrarily deep way). You don't say what the 'type' column is, but if it's something like a 'branch id' it can help you achieve the desired layout for a maximum of the depth shown (root nodes +1 deep). Ordering by level or parent_id only gets you so far, structurally, and you'll find this falls apart if you add a child to 'aba' for instance, because it can't reconcile its position with its siblings with the available structural data.

So assuming type is some kind of branch id and that the table therefore looks like this: ('aa%' is branch 1, 'ab%' is 2, etc)



+----+-----------+-------+------+----------+------+
| id | father_id | level | data | ordering | type |
+----+-----------+-------+------+----------+------+
| 1 | NULL | 0 | aa | 1 | 1 |
| 2 | NULL | 0 | ab | 2 | 2 |
| 3 | NULL | 0 | ac | 3 | 3 |
| 4 | NULL | 0 | ad | 4 | 4 |
| 5 | 1 | 1 | aba | 1 | 2 |
| 6 | 1 | 1 | abb | 2 | 2 |
| 7 | 3 | 1 | aca | 1 | 3 |
| 8 | 3 | 1 | acb | 2 | 3 |
| 9 | 3 | 1 | acc | 3 | 3 |
+----+-----------+-------+------+----------+------+


You can output your lists like this:


$sth = $dbh->query('SELECT level, data FROM t ORDER BY type, father_id, ordering');
$last_level = null;
echo '<ul>';
while ($row = $sth->fetch_assoc())
{
if (!is_null($last_level))
{
if ($row['level'] > $last_level) # Up a level, open a new list
echo '<ul>';
else if ($row['level'] < $last_level) # Down a level or two, close the last list item and as many parents as applicable
echo '</li>' . str_repeat('</ul></li>', $last_level - $row['level']);
else
echo '</li>'; # No level changes, just close the last list item
}

echo '<li>' . $row['data'];
$last_level = $row['level'];
}
echo '</li>' . str_repeat('</ul></li>', $last_level); # Close the last list item and any pending stacked levels


If you need your structure to get any deeper you're going to have to bite some kind of bullet, either refactoring to a non-recursive structural notation like MPTT, or actually doing recursive queries on a table structured similarly to this one to get things in the proper order. The former is a pain with race conditions and the latter doesn't scale.

b_hole
06-07-2007, 10:02 AM
My bad, the `type` field shouldn't be there. Therefore, the table should look like this:

+----+-----------+-------+------+----------+
| id | father_id | level | data | ordering |
+----+-----------+-------+------+----------+
| 1 | 0 | 0 | aa | 1 |
| 2 | 0 | 0 | ab | 2 |
| 3 | 0 | 0 | ac | 3 |
| 4 | 0 | 0 | ad | 4 |
| 5 | 2 | 1 | aba | 1 |
| 6 | 2 | 1 | abb | 2 |
| 7 | 3 | 1 | aca | 1 |
| 8 | 3 | 1 | acb | 2 |
| 9 | 3 | 1 | acc | 3 |
+----+-----------+-------+------+----------+

Sorry about the misleading. BTW, I can't change the structure of this table.
And yes, I also need to be able to go deeper. What I was thinking was to first select all the data, and then copy it to an array, and then do a recursive function on the array, without making so many SELECT statements.
What do you think?

dumpfi
06-10-2007, 01:35 PM
<?php
function createTree()
{
$res = mysql_query('SELECT id, father_id, data FROM t ORDER BY id ASC');
$tree = array();
while($row = mysql_fetch_assoc($res))
{
$row['children'] = array();
$tree[$row['id']] =& $row;
if($row['father_id'] != 0)
{
$tree[$row['father_id']]['children'][] =& $row;
}
unset($row);
}
return $tree;
}
function _printTree($node)
{
echo '<li>',$node['data'];
if(!empty($node['children']))
{
echo '<ul>';
foreach($node['children'] as $child)
{
_printTree($child);
}
echo '</ul>';
}
echo '</li>';
}
function printTree($tree)
{
echo '<ul>';
_printTree($tree);
echo '</ul>';
}
function printMultiTree($trees)
{
echo '<ul>';
foreach($trees as $tree)
{
if($tree['father_id'] == 0)
{
_printTree($tree);
}
}
echo '</ul>';
}
printMultiTree(createTree());

?>dumpfi

b_hole
06-21-2007, 09:57 AM
Thanks for the help dumpfi.
I'm trying to implement it in a different way. Here's what I'm doing:

function echo_2($rst, $f_id, $start, $level) {
$s=count($rst);
for ($i=$start; $i<$s; $i++) {
$disparray=$rst[$i];
if ($disparray['father_id']==$f_id) {
if ($level<$disparray['level']) echo "<ol>";
echo "<li>".$disparray['data'];
echo_2($rst, $disparray['id'], $start+1, $disparray['level']);
echo "</li>";
}
}
echo "</ol>"; // here's me problem
}
As you can see, I have no idea where to put the closing OL. What do you think?

Thank again for your help :)

b_hole
07-24-2007, 01:38 PM
dumpfi, I've been using your code for a while now, but it has a big problem: the data isn't ordered correctly, using the `ordering` column. Your function order the data using `id` column, and the data isn't ordered the right order.
Changing ORDER BY id ASC into ORDER BY ordering ASC isn't the solution: it displays only the part of the data. Why?

Thanks again.

b_hole
06-15-2008, 11:34 AM
Hi,

I'm bumping this up, as I have a problem with this function: as you can see, it orders the data according to the ID field. The problem occurs after editing the table: if I want to change the table to look like this:


<ul>
<li>aa</li>
<li>ab
<ul>
<li>aba</li>
<li>abb</li>
</ul>
</li>
<li>acc
<ul>
<li>ac
<ul>
<li>aca</li>
<li>acb</li>
</ul>
</li>
</ul>
</li>
<li>ad</li>
</ul>
It wouldn't display all of the data, because it orders the table by ID. As I said, this problem can happen only if the data is re-ordered (editing father_id).

Can someone please help me with this this? I can't figure out how to fix this...

Thanks a lot :)

dumpfi
07-25-2008, 10:40 AM
Try this:
<?php
function createTree()
{
$res = mysql_query('SELECT `id`, `father_id`, `data` FROM `t` ORDER BY `ordering` ASC');
$tree = array();
$childFixup = array();
while($row = mysql_fetch_assoc($res))
{
$row['children'] = array();
$tree[$row['id']] =& $row;
if($row['father_id'] != 0)
{
$childFixup[] =& $row;
}
unset($row);
}
for($i = 0, $c = count($fatherFixup); $i < $c; ++$i)
{
$tree[$childFixup[$i]['father_id']]['children'][] =& $childFixup[$i];
}
return $tree;
}
function _printTree($node)
{
echo '<li>',$node['data'];
if(!empty($node['children']))
{
echo '<ul>';
foreach($node['children'] as $child)
{
_printTree($child);
}
echo '</ul>';
}
echo '</li>';
}
function printTree($tree)
{
echo '<ul>';
_printTree($tree);
echo '</ul>';
}
function printMultiTree($trees)
{
echo '<ul>';
foreach($trees as $tree)
{
if($tree['father_id'] == 0)
{
_printTree($tree);
}
}
echo '</ul>';
}
printMultiTree(createTree());
?>dumpfi



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum