Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:29380
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain dealnews.com designates 129.41.69.185 as permitted sender)
Message-ID: <464207FC.2040403@dealnews.com>
Date: Wed, 09 May 2007 12:42:20 -0500
User-Agent: Thunderbird 2.0.0.0 (Macintosh/20070326)
MIME-Version: 1.0
To:  maurice@phorum.org
CC: Michael Walter <michael.walter@gmail.com>,  internals@lists.php.net
References: <4641D92C.4050208@dealnews.com>	 <10845a340705090743v6aba7896y45b9f7d60a4e77ba@mail.gmail.com>	 <4641E3DD.8040807@phorum.org> <877e9a170705090913i320359cag81b0a3bf203e2c86@mail.gmail.com> <464202D9.8080509@phorum.org>
In-Reply-To: <464202D9.8080509@phorum.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] Tree sort in C
From: brianm@dealnews.com (Brian Moon)

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 =)