Pimp my function

[Lars Eighner]

My function GetTourDescendants works, but I do not really have a recursive
brain (and run from lisp like a vampire from a crucifix) and am a little
wary of recursion in PHP. And besides, the function is ugly as sin. So,
this question is not will this work (it does) or how to make it work (it
does), but whether there is a better way or not to do this.

A tour may have any number of children, but in most cases have no more
than dozen (the tour with the greatest number of children has about 200).
Child tours also may have children, and so forth, but the number of
"generations" is not, in practice, more than six.

The function GetTourChildren($tour) returns a list (one-dimensional,
numerical indexed array) of children of $tour or an empty list
if a tour has no children.

The purpose of GetTourDescendants($tour) is to produce a list of
descendants of $tour, in other words, the children, the children of
children, and so forth. The purpose of this list is sanity checking
of the tour structure, the main one of which is to test for uniqueness
as a tour should not be a descendant of itself, no tour should be the
child of two different tours (in the same hierarchy), tours should not be
entered twice as a child of a given tour, and so forth.

So far as I can describe it, this is how GetTourDescendants works:

Well, actually the heavy lifting is done by GetTourDescendants_inner,
and GetTourDescendants just lops off the first cell of the return
because I cannot get GetTourDescendants_inner to work without returning
the parent tour as its own descendant.

So GetTourDescendants_inner goes this way:

The end condition is a tour has no children. However, this condition
might not be reached if in some way the tour structure has become
corrupt and a tour is its own descendant, so every time a tour is
added to the descendants list the list is checked for uniqueness.

If a tour has no children, it is added to the list, and the list is
returned.

If a tour has chidren, it is added to the list and the function
recurs on each child.

You may notice that GetTourDescendants_inner initializes $list if it is
called with one argument, which never happens here, since it is first called
by the wrapper GetTourDescendants. That is because I would like
GetTourDescendants_inner to stand alone, called from the outside with one
argument and called recursively with two.

function GetTourDescendants($tour){
$list = array();
$all = GetTourDescendants_inner($tour,$list);
return array_slice($all,1);
}

function GetTourDescendants_inner(){
$numargs = func_num_args();
$tour = func_get_arg(0);
if($numargs < 2){$list = array();
}else{ $list = func_get_arg(1);}
if(!GetTourChildren($tour)){$list[] = $tour;
if(count($list) != count(array_unique($list))){
die("Bad Tours: Get Tour Descendants not unique.");}
return $list;}
$list[] = $tour;
if(count($list) != count(array_unique($list))){
die("Bad Tours: Get Tour Descendants not unique.");}
foreach(GetTourChildren($tour) as $child){
$list = GetTourDescendants_inner($child,$list);
}
return $list;
}

--
Lars Eighner <http://larseighner.com/ <http://myspace.com/larseighner>
Countdown: 574 days to go.
Owing to googlegroups not screening users to eliminate spammers and other
USENET abusers, I do not see most posts from googlegroups.

[gosha bine]

On 26.06.2007 08:40 Lars Eighner wrote:

My function GetTourDescendants works, but I do not really have a recursive
brain (and run from lisp like a vampire from a crucifix) and am a little
wary of recursion in PHP. And besides, the function is ugly as sin. So,
this question is not will this work (it does) or how to make it work (it
does), but whether there is a better way or not to do this.
[snip]

hi there

a general purpose tree-walker algorithm is as simple as
$node = array(
'data' =whatever data,
'children' =array of nodes or empty
);

function walk($node) {
// do something with $node['data']
if(isset($node['children']))
foreach($node['children'] as $child)
walk($child);
}

a more generic approach would be to pass a callback function to the
walker, so that you can use it for different things
function walk($node, $callback) {
call_user_func($callback, $node);
if(isset($node['children']))
foreach($node['children'] as $child)
walk($child);
}
--
gosha bine

extended php parser ~ http://code.google.com/p/pihipi
blok ~ http://www.tagarga.com/blok