Hi,
A quick sketch of an idea that should work:
<?php
// test data
$nodes=array(
array('id'=>1, 'parent_id'=>0),
array('id'=>2, 'parent_id'=>1),
array('id'=>3, 'parent_id'=>1),
array('id'=>4, 'parent_id'=>2)
);
// create column data
$keys=$indents=$index=array();
$i=0;
foreach($nodes as $node)
{
$id=$node['id'];
$pid=$node['parent_id'];
$index[$id]=$i;
$keys[]=$pid ? $keys[$index[$pid]].'_'.$id : $id;
$indents[]=$pid ? $indents[$index[$pid]]+1 : 0;
++$i;
}
// sort
array_multisort($keys, $indents, $nodes);
// display
$i=0;
foreach($nodes as $node)
echo str_repeat(' ', $indents[$i++]), $node['id'], "\n";
?>
Regards,
Michael
On 5/9/07, Maurice Makaay <[EMAIL PROTECTED]> wrote:
Hello,
> Take a look at
> http://www.php.net/manual/en/function.array-multisort.php#68689
> / http://rquadling.php1h.com/array_multisort_column.php
Could you please explain how you think that multisort array would help
in doing a tree sort? AFAIK, tree sorting is not a simple sort algorithm
where you can tell which node comes before the other based on an $a vs.
$b comparison. After playing with it for quite a bit of time, I'm quite
convinced that you actually have to walk the tree to find indention
levels and node positions.
Imagine a tree like this:
node id parent id
1 0 (root node)
2 1
3 1
4 2
The tree sort with indention would look like this:
1
2
4
3
This is about as simple as it can get. So the ordered tree nodes for
this example would be array(1,2,4,3). Now try to find an array sorting
algorithm to get to this result. You'll find that node 4 is quite a
nasty one to get your head around.
Maybe we missed something obvious here, but there's most probably a
reason why a lot of applications implement tree sorting as a recursive
function call and not as an array sort of some kind.
From your followup post:
> That doesn't look right. Surely ID is already sorted so the array
won't change?
> And sorting by "parent" and then "id" would make no difference either.
I see you already found out the big issue with tree sorting ;-) You
cannot apply simple linear sorting to find out in what order the nodes
in a tree appear.
I hope my example cleared up some of the confusion.
With kind regards,
Maurice Makaay
Phorum.org
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
