Sorting tree array infinite and generating a nested HTML structure

funcion · Feb 18, 2019

I want to create this question with the intention that we can collect in one place, one or several examples of an infinite array tree, and generate a nested structure of HTML <ul> <li>, with examples of codes using good practices for junior programmers, who want to learn to work with this type of arrays.

Scope:

Sort the arrangement and generate the HTML with different types of examples.
Use different examples of codes with the same result, to understand the work with this type of arrangements, which can become very complex.

I have prepared for this example a multi-level arrangement:

The code that orders this arrangement I have obtained from this answer: https://stackoverflow.com/questions/4284616/php-array-tree-sorting/#answer-4284985

A simple view is a code that is not so easy to digest, I would like more experienced programmers to give us more examples of code to obtain the same result, with different practices and examples.

$data = array(
    array("id"=> 1,  "parent_id" => "", "name"=> "Home" ),
    array("id"=> 2,  "parent_id" => "", "name"=> "News"),
    array("id"=> 3,  "parent_id" => 2, "name"=> "World"),
    array("id"=> 4,  "parent_id" => 2, "name"=> "Internationals"),
    array("id"=> 5,  "parent_id" => 4, "name"=> "America"),
    array("id"=> 6,  "parent_id" => 5, "name"=> "United Stated"),
    array("id"=> 7,  "parent_id" => 6, "name"=> "Florida"),
    array("id"=> 8,  "parent_id" => 7, "name"=> "Miami"),
    array("id"=> 9,  "parent_id" => "", "name"=> "Sports"),
    array("id"=> 10,  "parent_id" => "", "name"=> "Global")
);

$sort = array();
$all = array();
$dangling = array();

// Initialize arrays
foreach ($data as $value) {
    $value['children'] = array();
    $id = $value['id'];

// If this is a top-level node, add it to the sort immediately
if ($value['parent_id'] == '') {
    $all[$id] = $value;
    $sort[] =& $all[$id];

// If this isn't a top-level node, we have to process it later
} else {
    $dangling[$id] = $value; 
}
}

// Process all 'dangling' nodes
while (count($dangling) > 0) {
    foreach($dangling as $value) {
        $id = $value['id'];
        $pid = $value['parent_id'];

    // If the parent has already been added to the sort, it's
    // safe to add this node too
    if (isset($all[$pid])) {
        $all[$id] = $value;
        $all[$pid]['children'][] =& $all[$id]; 
        unset($dangling[$value['id']]);
    }
}
}

echo "<pre>"; print_r($sort);

This would be the result of the array ordered:

I want to generate from this array an HTML structure like the following one, using good practices and with different examples.

<ul>
    <li><a href="#">Home</a></li>
    <li><a href="#">News</a>
        <ul>
            <li><a href="#">World</a></li>
            <li><a href="#">Internationals</a>
                <ul>
                    <li><a href="#">America</a>
                        <ul>
                            <li><a href="#">United Stated</a>
                                <ul>
                                    <li><a href="#">Florida</a>
                                        <ul>
                                            <li><a href="#">Miami</a></li>
                                        </ul>
                                    </li>
                                </ul>
                            </li>
                        </ul>
                    </li>
                </ul>
            </li>
        </ul>
    </li>
    <li><a href="#">Sports</a></li>
    <li><a href="#">Global</a></li>
</ul>

NogDog · Feb 19, 2019

Unless there's a reason for that $data array having the id and parent_id fields, it seems like it would be easier -- both coding-wise and for readability/maintenance -- to define the initial data array as an n-dimensional array, instead of messing with parent IDs. You could even use JSON for the config. Then a little recursive function can traverse that array and build the HTML markup:

<?php

function buildList(Array $data)
{
  $result = "<ul>\n";
    foreach($data as $name => $content)
    {
      $result .= "<li>$name";
      if(count($content))
      {
        $result .= buildList($content);
      }
      $result .= "</li>\n";
    }
  $result .= "</ul>\n";
  return $result;
}

$jsonData = <<<EOD
{
  "Home": {},
  "News": {
    "World": {},
    "Internationals": {
      "America": {
        "United States": {
          "Florida": {
            "Miami": {}
          }
        }
      }
    }
  },
  "Sports": {},
  "Global": {}
}
EOD;

$data = json_decode($jsonData, 1);
echo buildList($data);

Output:

<ul>
<li>Home</li>
<li>News<ul>
<li>World</li>
<li>Internationals<ul>
<li>America<ul>
<li>United States<ul>
<li>Florida<ul>
<li>Miami</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>Sports</li>
<li>Global</li>
</ul>

To-do: pretty indenting, if desired.

Weedpacket · Feb 19, 2019

And if you have a "id/parent-id" array (perhaps drawn from a database) and you're wanting a hierarchical array (and don't want to {do the conversion to / have} a JSON object in the database),

First use more useful values for the array keys:

$data = array_column($data, null, 'id');

For once I actually have a use for variable references. That's rare.

Instead of copying the value of each entry to its parent's children, I make an alias to the child instead. Later, if the child has children of its own, I won't have to search for where I put it because I may still refer to it through its original location. It also means I don't have to do an initial topological sort; it doesn't matter if children appear in the list before or after their parents.

foreach($data as &$entry)
{
    if(($parent = $entry['parent_id']) !== "")
    {
        $data[$parent]['children'][] = &$entry; // <--Wow
    }
}
unset($entry); // In case I want to use "$entry" again

All of those children are still elements of the original $data array, and they're all still aliased to various child elements all over the place (often multiple times). But only those that are supposed to be at the root will have a parent_id of "". So to clear out all those loose branches lying around:

$data = array_filter($data, function($a)
{
	return $a['parent_id'] === "";
});

Since every element has a single parent, every element will appear in the final $data, all of the aliases but one for any given element will be unset by the filtering, that "but one" being the one accessible by traversing from the root as desired.

The tree-building and root-pruning steps might be done together, by putting each root as it is found in a temporary array, then replacing the original array with the temporary one. But that strikes me as a little messier.

Note: Circular references can be formed if the id/parent_id relationship is not a partial order; they will be pruned out of the result (as they can't be reached from a root) but will remain floating around in memory until the GC engine kicks off a mark-sweep phase.
Note: With a bit of fiddling (i.e. a nested loop), this could also be used in situations where an entry may have more than one parent; all such entries will appear as often as they have parents, and all of them will have a full set of descendants. Duplicates will remain aliased to each other. Loops will be preserved (which could make for pain when serialising).

Weedpacket · Feb 20, 2019

NogDog
And depending on what the resulting HTML list is for (specifically, something that already requires JavaScript) then maybe serve the JSON to the browser and have script build the HTML and whatever event handlers it needs.