On Mon, May 17, 2010 at 9:13 AM, Richard Quadling
<rquadling@xxxxxxxxxxxxxx>wrote:
> OOI, can you take a look at my first response. Is this the sort of
> thing you were talking about?
>
Essentially, yes. For the temporary array I would map nid => element instead
of INDEX => nid. Your $Relationships array is basically the same as $Data.
The goal is to make the lookup of parentID fast. This would be automatic if
the keys of $Data were the nid values instead of a raw index from 0..N-1. If
the relationship INDEX = nid - 1 for all elements in $Data, the temporary
array also isn't needed.
Here's how I would code it:
function makeTreeAndReturnRoots(&$arr)
{
// not necessary if $arr is guaranteed to contain at least one root
$map[0]['children'] = array();
// map each nid to its node
foreach ($arr as $index => &$node) {
$map[$node['nid']] = $node;
}
// add each node to its parent's children array
foreach ($map as $nid => &$node) {
$map[$parentID]['children'][] = $node;
}
// return the array of root nodes
return $map[0]['children'];
}
Note: I haven't tested the above so my reference usage may be off, but it
illustrates the basic algorithm. Each node requires a single ArrayPut
operation to create $map and a single ArrayGet to lookup the parent node in
$map in addition to the two attribute accesses for nid and children (also
ArrayGet operations). Since all of the keys are unique in their respective
hashtables, these operations should all be O(1) making the entire algorithm
O(2n) which simplifies to O(n).
David
