Ah, thank you @oddz for that. I didn’t know about the term adjacency list. I will be using that from now on.
OK so here’s the code I promised showing that this can be done without recursion. I’ve actually gone one step further—or perhaps stupider—and done it without using references as well because I wanted to see if it was possible to just using array indexes. I’m happy to say it is.
One of the advantages with the recursion method if you can just put in whatever decoration (bits of strings) you want to appear between the various calls and have it appear within the structure roughly as you would expect. When you use a loop you loose that advantage because the structure of the tree isn’t visually reflected in the code it’s only reflected through the logic you use. As a partial solution to that problem I generalized the loop a bit so that you can supply various parameters that will control how the tree will appear. Unfortunately it is still quite limited: I can think of a number of things you might want to do for which you would have to modify the core loop but the same problem is true of recursion too it’s just that reworking the recursion isn’t so difficult (if you’re used to it).
<?php
function Employee($id, $name, $supId) {
return array('id' => $id, 'name' => $name, 'supId' => $supId); }
// This is the equivalent of your query function
function subsOf($supNode) {
$employees = [ // This is your table
Employee(1, 'Zim', null),
Employee(2, 'Gir', 1),
Employee(3, 'Wash', 1),
Employee(4, 'Dib', null),
Employee(5, 'Gaz', 4),
Employee(6, 'Cat', 5) ];
// `array_values()` required to ensure contiguous seq for `renderNodes()`
return array_values(array_filter($employees, function($node) use($supNode) {
return $node['supId'] === $supNode['id']; })); }
function esc($str) {
return htmlSpecialChars($str, ENT_QUOTES, 'UTF-8'); }
function intAsEngOrdinal($n) {
$ordinals = ['zeroth', 'first', 'second', 'third', 'fourth'];
return $ordinals[$n]; }
// Function to render nodes. They can be structured however you like as long as
// you can define a `$getSubsF`. Miniglossary:
// - subs :: sub nodes
// - seq :: contiguously indexed array
// - f :: function
function renderNodes(
$rootNodes, // seq of one or more root nodes
$renderRoots, // boolean whether to render the root nodes
$getSubsF, // returning a list of subs for a node
$renderNodeF, // returning str from node and depth level (int)
$postSubsStr, // str to insert after subs
$betweenSiblingsStr // str to insert between siblings
) {
$nodeSets = [$rootNodes];
$xs = [$y = 0];
$output = '';
for (;;) {
$x = $xs[$y];
if ($nodeSets[$y] === [] || !isSet($nodeSets[$y][$x])) {
if ($y === 0) { break; }
if ($y > 0 || $renderRoots) { $output .= $postSubsStr; }
$y--;
continue; }
$node = $nodeSets[$y][$x];
if ($y > 0 || $renderRoots) {
if ($x > 0) { $output .= $betweenSiblingsStr; }
$output .= $renderNodeF($node, $y); }
$nodeSets[$y + 1] = $getSubsF($node);
if (isSet($xs[$y])) { $xs[$y]++; }
else { $xs[$y] = 1; }
$y++;
$xs[$y] = 0; }
return $output; }
// Two examples of usage:
function employeeHtml($e, $lvl) {
return "\
" . str_repeat(' ', ($lvl - 1) * 2)
. "<div class='" . intAsEngOrdinal($lvl) . "'>"
. '<strong>' . esc($e['name']) . '</strong>'; }
function employeeTxt($e) { return $e['name'] . '['; }
$rootNodes = [Employee(null, '(root)', null)];
echo renderNodes($rootNodes, false, 'subsOf', 'employeeHtml', '</div>', '');
echo "\
\
";
echo renderNodes($rootNodes, false, 'subsOf', 'employeeTxt', ']', ',');
echo "\
";
Output:
<div class='first'><strong>Zim</strong>
<div class='second'><strong>Gir</strong></div>
<div class='second'><strong>Wash</strong></div></div>
<div class='first'><strong>Dib</strong>
<div class='second'><strong>Gaz</strong>
<div class='third'><strong>Cat</strong></div></div></div></div>
Zim[Gir[],Wash[]],Dib[Gaz[Cat[]]]]
I was going to write a version of this that uses references instead of array indexes but I’ve already spent way too long on this.
