Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 8 of 8

Thread: recursion help

  1. #1
    Regular Coder
    Join Date
    Aug 2006
    Posts
    135
    Thanks
    0
    Thanked 0 Times in 0 Posts

    recursion help

    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:
    Code:
    <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:
    Code:
    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

  • #2
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    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)

    Code:
    +----+-----------+-------+------+----------+------+
    | 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:

    PHP Code:
    $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.

  • #3
    Regular Coder
    Join Date
    Aug 2006
    Posts
    135
    Thanks
    0
    Thanked 0 Times in 0 Posts
    My bad, the `type` field shouldn't be there. Therefore, the table should look like this:
    Code:
    +----+-----------+-------+------+----------+
    | 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?
    Last edited by b_hole; 06-07-2007 at 10:05 AM.

  • #4
    Regular Coder
    Join Date
    Jun 2004
    Posts
    565
    Thanks
    0
    Thanked 18 Times in 18 Posts
    PHP Code:
    <?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
    Last edited by dumpfi; 06-10-2007 at 01:39 PM.
    "Failure is not an option. It comes bundled with the software."
    ....../)/)..(\__/).(\(\................../)_/)......
    .....(-.-).(='.'=).(-.-)................(o.O)...../<)
    ....(.).(.)("}_("}(.)(.)...............(.)_(.))Ż/.
    ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
    Little did the bunnies suspect that one of them was a psychotic mass murderer with a 6 ft. axe.

  • #5
    Regular Coder
    Join Date
    Aug 2006
    Posts
    135
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for the help dumpfi.
    I'm trying to implement it in a different way. Here's what I'm doing:
    PHP Code:
    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

  • #6
    Regular Coder
    Join Date
    Aug 2006
    Posts
    135
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #7
    Regular Coder
    Join Date
    Aug 2006
    Posts
    135
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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:

    Code:
    <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

  • #8
    Regular Coder
    Join Date
    Jun 2004
    Posts
    565
    Thanks
    0
    Thanked 18 Times in 18 Posts
    Try this:
    PHP Code:
    <?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
    "Failure is not an option. It comes bundled with the software."
    ....../)/)..(\__/).(\(\................../)_/)......
    .....(-.-).(='.'=).(-.-)................(o.O)...../<)
    ....(.).(.)("}_("}(.)(.)...............(.)_(.))Ż/.
    ŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻŻ
    Little did the bunnies suspect that one of them was a psychotic mass murderer with a 6 ft. axe.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •