On Friday 30 June 2006 07:19, Ben Liu wrote:
> Hi Larry,
> I've looked through the posts on the PHP general list going back
> about 3-6 weeks and can't find the thread you speak of. I searched by
> your name assuming that you posted into the thread and searched by
> the string "recursive" and "recursion". If you could steer me to it
> in some other way (subject of the thread or subject word) I would
> appreciate it, but only if it is not too much trouble. I can take a
> go at it now that the basic approach is carved out: query once,
> recurse the data in PHP.
Well I checked my Sent file and apparently it somehow got sent to just one
person rather than the entire list. I HATE it when that happens. Here's a
copy of it below. *sigh*
---------- Forwarded Message ----------
Subject: Re: How do I make a HTML tree for a set of nodes?
Date: Sunday 04 June 2006 12:38
From: Larry Garfield <larry@xxxxxxxxxxxxxxxx>
To: zorglub_olsen@xxxxxxxxxxx
On Sunday 04 June 2006 11:27, Niels wrote:
> This sounds fine -- recursion is obviously the way to go. Where can I see
> your function?
>
> I tried several different solutions over the last couple of hours, and I've
> settled on only using indentation (like a nested <ul></ul> list), not a
> fancy graph with antialised branches. It's the simplest possible recursion
> but I like the results, even if it's a bit harder to grasp without
> connections clearly marked.
>
>
> function tree($nodes, $start, $indent=-30) {
> $indent+=30;
> global $tree;
> foreach ($nodes as $nodeID => $node) {
> if ($node['parent']!=$start) {continue;}
> $tree.="<div
> style='margin-left:{$indent}px'>{$node['name']}</div>"; tree($nodes,
> $nodeID, $indent);
> }
> return $tree;
> }
Yep, you're on the right track here. If your tree is a directed acyclic
graph (read: every node has at most one parent, and never loops back on
itself), then it's quite easy to do with one SQL table and one SQL query.
(Or similar, if you're not using SQL, but I've done this many times in SQL.)
First, fetch a list of all nodes, in whatever sort order you want (say,
alphabetical), ignoring the nesting. You want an array of records (an SQL
result works, or an array of objects, or an array of arrays), where each
record has at minimum its own ID and its parent ID (0 meaning it's a root
node), and some sort of label.
Then, starting at parentid=0, iterate over the list and process just those
with that parent id. "Process" means, in this case, for example, to print
out a list item with the name, save the current cursor, and call the function
again recursively with the id of the active node as the new parent node.
When you return, reset the cursor. The cursor stuff is so that you can pass
the array by reference rather than by value and not waste a ton of memory.
So the pseudo-code would look something like:
function foo(&$nodes, $parentid) {
reset($nodes);
foreach ($nodes as $node) {
if ($node's parent is $parent id) {
$output .= "<li>"
. $node (or whatever portion of it you want)
. foo($nodes, $node's id)
. "</li>";
}
}
if ($output) return "<ul>$output</ul>";
}
$nodes = get_my_nodes();
$list = foo($nodes, 0);
There's probably a small bug in the above somewhere since I haven't tested
it, and it would vary a bit if you're operating on an SQL result directly,
but that's the basic idea. The advantage is that you get HTML that is
structurally representative of the relationship, as well as pre-styled for
you by default by any browser.
> Thanks,
>
> Ben
>
> On Jun 30, 2006, at 12:05 AM, Larry Garfield wrote:
> > I've written such a system before more than once. You do the
> > sorting in SQL,
> > and then traverse the data recursively in PHP to build the tree.
> > It's a
> > single SQL query. Check the archives for this list for about 3-4
> > weeks ago,
> > I think. We were just discussing it, and I showed some basic code
> > examples. :-)
> >
> > --
> > Larry Garfield AIM: LOLG42
> > larry@xxxxxxxxxxxxxxxx ICQ: 6817012
--
Larry Garfield AIM: LOLG42
larry@xxxxxxxxxxxxxxxx ICQ: 6817012
"If nature has made any one thing less susceptible than all others of
exclusive property, it is the action of the thinking power called an idea,
which an individual may exclusively possess as long as he keeps it to
himself; but the moment it is divulged, it forces itself into the possession
of every one, and the receiver cannot dispossess himself of it." -- Thomas
Jefferson
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
