Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:29377
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 64.233.184.226 as permitted sender)
DomainKey-Status: bad
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=JW4Yjf274T6yvGliakutQcnoZWkvUlZE/WdDb3ZDByblSZ7fpRyqcwdPk1fBwHb2e1ixuQtTJ8Z+mkkgU3qWBLfKr2X1skqBnpRWjXLaj7ue/Pc1wZYEKJVuk63EJPVjBUb/LJflCJ7oCXoWUryDvOm8VMfqDvZiy0YmNwYpnUw=
Message-ID: <877e9a170705090913i320359cag81b0a3bf203e2c86@mail.gmail.com>
Date: Wed, 9 May 2007 18:13:17 +0200
To: maurice@phorum.org
Cc: RQuadling@googlemail.com, "Brian Moon" <brianm@dealnews.com>, 
	internals@lists.php.net
In-Reply-To: <4641E3DD.8040807@phorum.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <4641D92C.4050208@dealnews.com>
	 <10845a340705090743v6aba7896y45b9f7d60a4e77ba@mail.gmail.com>
	 <4641E3DD.8040807@phorum.org>
Subject: Re: [PHP-DEV] Tree sort in C
From: michael.walter@gmail.com ("Michael Walter")

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 <maurice@phorum.org> 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
>
>