there are %d monkeys in the tree

29 October 2006 // php. stuff.

Simple functions to create php tree structures (nested arrays) from "flat" storage formats.

Adjacency list to tree

Adjacency lists are widely used to store trees in SQL tables. With ALs, inserts and updates are cheap, but retrieving the whole tree is tricky. Some people use recursion and nested queries for this (which doesn't scale well) or build JOIN statements dynamically (which is messy). The "pure php" solution is, on the contrary, quite trivial: we simply select all rows and "sieve" them through tree builder function.

function adj_tree(&$tree, $item) {
    $i = $item['id'];
    $p = $item['parent_id'];
    $tree[$i] = isset($tree[$i]) ? $item + $tree[$i] : $item;
    $tree[$p]['_children'][] = &$tree[$i];
}

$tree = array();
$rs = my_query("SELECT * FROM categories");
while($row = my_fetch($rs))
    adj_tree($tree, $row);

At the end, $tree[0] contains the root of the hierarchy. Moreover, $tree[N] will be a subtree for the node with id = N, so you can easily select subtrees.

Indented lists

The second function reconstructs the tree from the data "printed" as an indented list like this one (spaces replaced with dots for clarity):

Hardware
...Scanners
....Monitors
......CRT monitors
.......LCD monitors
...Input devices
......Keyboards
......Mice

The function is as follows:

function indent_tree($text, $indent = ' ') {
    $root  = array();
    $stack = array(&$root);
    $depth = -1;
    $temp  = array();
    $re = '/^(' . preg_quote($indent) . ')+/';
    $len = strlen($indent);

    foreach(explode("\n", trim($text)) as $line) {
        $v = preg_replace($re, '', $line);
        $k = (strlen($line) - strlen($v)) / $len;
        while($depth-- >= $k)
            array_pop($stack);
        while(++$depth < $k) {
            array_unshift($temp, array());
            $stack[count($stack) - 1]['_children'][] = &$temp[0];
            $stack[] = &$temp[0];
        }
        $stack[count($stack) - 1]['value'] = trim($v);
    }
    return $root;
}

The code doesn't require the list to be precisely indented: indents are rounded down, you only need to pass the "average" indent string (in above case, it would be three spaces).