I worked out a bit of code to build an array tree for the directory structure of a website. The tree is stored in the database on a single table. Here’s my test array, the results of query “SELECT * FROM pages”
Array
(
[0] => Array
(
[recordid] => 1
[parentid] => 0
[name] =>
[title] => Home Page
[class] => Gazelle\\Page
)
[1] => Array
(
[recordid] => 2
[parentid] => 1
[name] => js
[title] => Javascript Page
[class] => Gazelle\\JavascriptPage
)
[2] => Array
(
[recordid] => 3
[parentid] => 1
[name] => technology
[title] => Tech News
[class] =>
)
[3] => Array
(
[recordid] => 4
[parentid] => 3
[name] => windows
[title] => Windows
[class] =>
)
[4] => Array
(
[recordid] => 5
[parentid] => 3
[name] => mac
[title] => Mac
[class] =>
)
[5] => Array
(
[recordid] => 6
[parentid] => 3
[name] => linux
[title] => Linux
[class] =>
)
[6] => Array
(
[recordid] => 7
[parentid] => 6
[name] => slackware
[title] => Slackware
[class] =>
)
[7] => Array
(
[recordid] => 8
[parentid] => 6
[name] => debian
[title] => Debian
[class] =>
)
)
The resulting tree needs to look like this
Array
(
[1] => Array
(
[attributes] => Array
(
[name] =>
[title] => Home Page
[class] => Gazelle\\Page
)
[children] => Array
(
[2] => Array
(
[attributes] => Array
(
[name] => js
[title] => Javascript Page
[class] => Gazelle\\JavascriptPage
)
[children] => Array
(
)
)
[3] => Array
(
[attributes] => Array
(
[name] => technology
[title] => Tech News
[class] =>
)
[children] => Array
(
[4] => Array
(
[attributes] => Array
(
[name] => windows
[title] => Windows
[class] =>
)
[children] => Array
(
)
)
[5] => Array
(
[attributes] => Array
(
[name] => mac
[title] => Mac
[class] =>
)
[children] => Array
(
)
)
[6] => Array
(
[attributes] => Array
(
[name] => linux
[title] => Linux
[class] =>
)
[children] => Array
(
[7] => Array
(
[attributes] => Array
(
[name] => slackware
[title] => Slackware
[class] =>
)
[children] => Array
(
)
)
[8] => Array
(
[attributes] => Array
(
[name] => debian
[title] => Debian
[class] =>
)
[children] => Array
(
)
)
)
)
)
)
)
)
)
My function to do this process can build the tree taking between 36 and 44 steps (possibly a few more). The reason for the variance is I plugged in a shuffle statement on the test array so that I could be sure the function would work even if the input array order was entirely random, though the order will affect the number of loops.
protected function buildTree( $data, $key, $parent, $seek = 0) {
$tree = array();
foreach($data as $k => $v) {
if ($v[$parent] == $seek) {
$i = $v[$key];
unset($data[$k], $v[$key], $v[$parent]);
$tree[$i] = array(
'attributes' => $v,
'children' => $this->buildTree( $data, $key, $parent, $i)
);
}
}
return $tree;
}
During testing I used this invocation.
$array = $s->fetchAll( \\PDO::FETCH_ASSOC );
shuffle($array); // make sure this works no matter what the order of input.
$this->buildTree( $array, $key, $parent);
Now, I am not that good with data structures, and something tells me the people here that are smarter than I am can come up with something that can build the tree in fewer than 36 steps.
Or if someone knows of an inbuilt function that does this tell me so I can laugh at myself for wasting time (though the educational value of working this out was worth it).
