How can I build a nested HTML list with an infinite depth from a flat array?

Question

I'm trying to produce a multi-level HTML list from a source array that is formatted like this:

/**
 * id = unique id
 * parent_id = "id" that this item is directly nested under
 * text = the output string
 */
$list = array(
    array(
        'id'        =>  1,
        'parent_id' =>  0,
        'text'      =>  'Level 1',
    ), array(
        'id'        =>  2,
        'parent_id' =>  0,
        'text'      =>  'Level 2',
    ), array(
        'id'        =>  3,
        'parent_id' =>  2,
        'text'      =>  'Level 2.1',
    ), array(
        'id'        =>  4,
        'parent_id' =>  2,
        'text'      =>  'Level 2.2',
    ), array(
        'id'        =>  5,
        'parent_id' =>  4,
        'text'      =>  'Level 2.2.1',
    ), array(
        'id'        =>  6,
        'parent_id' =>  0,
        'text'      =>  'Level 3',
    )
);

The goal is a nested <ul> with an infinite depth. The expected output of the array above is this:

• Level 1
• Level 2
  • Level 2.1
  • Level 2.2
    • Level 2.2.1
• Level 3

If only the array items had a key called child or something that contained the actual sub-array, it would be easy to recurse though these and get the desired output with a function like this:

function makeList($list)
{
    echo '<ul>';
    foreach ($list as $item)
    {
        echo '<li>'.$item['text'];
        if (isset($item['child']))
        {
            makeList($item['child']);
        }
        echo '</li>';
    }
    echo '</ul>';
}

Unfortunately that's not the case for me - the format of the source arrays can't be changed. So, long ago I wrote this very nasty function to make it happen, and it only works up to three levels (code is pasted verbatim with original comments). I know it's a long boring read, please bear with me:

function makeArray($links)
{
    // Output
    $nav = array();

    foreach ($links as $k => $v)
    {
        // If no parent_id is present, we can assume it is a top-level link
        if (empty($v['parent_id']))
        {
            $id = isset($v['id']) ? $v['id'] : $k;

            $nav[$id] = $v;

            // Remove from original array
            unset($links[$k]);
        }
    }

    // Loop through the remaining links again,
    // we can assume they all have a parent_id
    foreach ($links as $k => $v)
    {
        // Link's parent_id is in the top level array, so this is a level-2 link
        // We already looped through every item so we know they are all accounted for
        if (isset($nav[$v['parent_id']]))
        {
            $id = isset($v['id']) ? $v['id'] : $k;

            // Add it to the top level links as a child
            $nav[$v['parent_id']]['child'][$id] = $v;

            // Set a marker so we know which ones to loop through to add the third level
            $nav2[$id] = $v;

            // Remove it from the array
            unset($links[$k]);
        }
    }

    // Last iteration for the third level
    // All other links have been removed from the original array at this point
    foreach ($links as $k => $v)
    {
        $id = isset($v['id']) ? $v['id'] : $k;

        // Link's parent_id is in the second level array, so this is a level-3 link
        // Orphans will be ignored
        if (isset($nav2[$v['parent_id']]))
        {
            // This part is crazy, just go with it
            $nav3 = $nav2[$v['parent_id']]['parent_id'];
            $nav[$nav3]['child'][$v['parent_id']]['child'][] = $v;
        }

    }

    return $nav;
}

This makes an array like:

array(
    'text' => 'Level 1'
    'child' => array(
        array(
            'text' => 'Level 1.2'
            'child' => array(
                array(
                    'text' => 'Level 1.2.1'
                    'child' => array(
                        // etc.
                   ),
                array(
                    'text' => 'Level 1.2.2'
                    'child' => array(
                        // etc.
                   ),
                )
             )
        )
    )
);

Usage:

$nav = makeArray($links);
makeList($nav);

---

I've spent many spare hours trying to work this out, and the original code which I have given here is still the best solution I've been able to produce.

How can I make this happen without that awful function (which is limited to a depth of 3), and have an infinite number of levels? Is there a more elegant solution to this?

Answer 1

Print:

function printListRecursive(&$list,$parent=0){
    $foundSome = false;
    for( $i=0,$c=count($list);$i<$c;$i++ ){
        if( $list[$i]['parent_id']==$parent ){
            if( $foundSome==false ){
                echo '<ul>';
                $foundSome = true;
            }
            echo '<li>'.$list[$i]['text'].'</li>';
            printListRecursive($list,$list[$i]['id']);
        }
    }
    if( $foundSome ){
        echo '</ul>';
    }
}

printListRecursive($list);

Create multidimensional array:

function makeListRecursive(&$list,$parent=0){
    $result = array();
    for( $i=0,$c=count($list);$i<$c;$i++ ){
        if( $list[$i]['parent_id']==$parent ){
            $list[$i]['childs'] = makeListRecursive($list,$list[$i]['id']);
            $result[] = $list[$i];
        }
    }
    return $result;
}

$result = array();
$result = makeListRecursive($list);
echo '<pre>';
var_dump($result);
echo '</pre>';