Re: Tree sort in C

Maurice Makaay wrote:

Hi,

A quick sketch of an idea that should work:

Yes, that would work. The problem though, is that there's still accumulation of data going on, before the actual sorting can take place. Remember that the main reason for writing the C-extension was to get the memory usage down.

Actually, this does not work. It uses string sorting to sort the nodes in the $keys array. This means the nodes at a given level are now out of order compared to the original order of the input array Try this for making a node list: for($x=1;$x<=40;$x++){

    $parent = rand(0,$x-1);
    $nodes[$x] = array(
        "id" => $x,
        "parent_id" => $parent,
        "title" => "item $x"
     );

} You will see that the order of the nodes within a level is string sorted. That is not desired. The order of the children should not change from the order they appeared in the input array. In this case, numeric, but with our function, the order is preserved. So, you could sort the array by ANY thing you wanted before calling the tree sort function and the nodes at any given level will be in that order. And as Maurice said, the memory overhead is still there. -- Brian Moon Senior Developer ------------------------------ http://dealnews.com/ It's good to be cheap =)