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>';

Answer 2

Tested and working :)

$list = array(...);
$nested = array();

foreach ($list as $item)
{
    if ($item['parent_id'] == 0)
    {
        // Woot, easy - top level
        $nested[$item['id']] = $item;
    }
    else
    {
        // Not top level, find it's place
        process($item, $nested);
    }
}

// Recursive function
function process($item, &$arr)
{
    if (is_array($arr))
    {
        foreach ($arr as $key => $parent_item)
        {
            // Match?
            if (isset($parent_item['id']) && $parent_item['id'] == $item['parent_id'])
            {
                $arr[$key]['children'][$item['id']] = $item;
            }
            else
            {
                // Keep looking, recursively
                process($item, $arr[$key]);
            }
        }
    }
}

Answer 3

Some methods I recently wrote, maybe some will help, sorry I'm short on time and cannot rewite them to match your needs.

This code is actually a part of Kohana Framework Model, method ->as_array() is used to flat an Database_Result object.

function array_tree($all_nodes){
    $tree = array();
    foreach($all_nodes as $node){
        $tree[$node->id]['fields'] = $node->as_array();
        $tree[$node->id]['children'] = array();

        if($node->parent_id){
             $tree[$node->parent_id]['children'][$node->id] =& $tree[$node->id];
        }
    }


    $return_tree = array();
    foreach($tree as $node){
        if($node['fields']['depth'] == 0){
            $return_tree[$node['fields']['id']] = $node;
        }
    }

    return $return_tree;
}

array_tree() is used to make a tree out of a flat array. The key feature is the =& part ;)

function html_tree($tree_array = null){
        if( ! $tree_array){
           $tree_array = $this -> array_tree();
        }

        $html_tree = '<ul>'."\n";
        foreach($tree_array as $node){
            $html_tree .= $this->html_tree_crawl($node);
        }
        $html_tree .= '</ul>'."\n";


        return $html_tree;
    }

function html_tree_crawl($node){
        $children = null;

        if(count($node['children']) > 0){
            $children = '<ul>'."\n";
            foreach($node['children'] as $chnode){
                $children .= $this->html_tree_crawl($chnode);
            }
            $children .= '</ul>'."\n";
        }

        return $this->html_tree_node($node, $children);
    }

html_tree_node() is a simple method to display current node and children in HTML. Example below:

<li id="node-<?= $node['id'] ?>">
    <a href="#"><?= $node['title'] ?></a>
    <?= (isset($children) && $children != null) ? $children : '' ?>
</li>