note 44793 deleted from language.types.array by tomsommer
| From: | tomsommer@php.net | Date: | Mon, 16 Aug 2004 19:34:09 +0000 |
| Subject: | note 44793 deleted from language.types.array by tomsommer | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-74775@lists.php.net to get a copy of this message | ||
Note Submitter: brooklynphil hotmail com
----
here is a barebones generic tree class for php
i was writing a parser for nexus/newick phylogeny trees, thinking it would be extremely easy in php,
but i hit a wall twice because php lacks true pointers (sniff) and my tree school depends greatly on
them (all my attempts took the c+cpp approach, unsucessfully).
so i decided to take a step back and, finding none online, write a generic tree wrapper.
this can most definitely be made a little better, but the essentials are there and should be good
starting place to costumize it for your needs
P.S. writing a red-black implementation, or gen_optimal_AVL(), is left as an exercise to the reader
:D (same for traversals and delete)
P.P.S. if you have a better, less complex php approach than mine, please post it :) (same if you
have corrections for possible bugs with all those "&"'s i have to use...) for
example, using eval and '[x][y]...[z]' might be more efficient in scan()...
<?php
/*
by Phil R
http://www.quakeplayers.org/~phil
*/
<?php
/*
by Phil R
http://www.quakeplayers.org/~phil
*/
class phil_node
{
var $self,$prnt,$data,$chld;
function phil_node($parent = null, $data = null)
{
$this->prnt = $parent;
$this->self = md5(uniqid(mt_rand(), true));
$this->data = $data;
}
function &get_parent(&$tree)
{
return $tree->getnode($this->prnt);
}
}
class phil_tree
{
var $root;
function phil_tree()
{
$this->root =& new phil_node();
}
function &push($what, &$node)
{
return $node->chld[] =& new phil_node($node->self,$what);
}
function &scan(&$start,&$find)
{
if ($start->self == $find) return $start;
if ($start->chld) foreach($start->chld as $i => $dummy)
{
$ret =& $this->scan($start->chld[$i], $find);
if ($ret !== false) return $ret;
}
return false;
}
function &getnode(&$nodeid)
{
if (is_null($nodeid)) return $this->root;
return $this->scan($this->root, $nodeid);
}
}
?>
<pre>test
<?php
$tree =& new phil_tree();
$q =& $tree->push("doctor smith", $tree->root);
$q =& $tree->push("smith's son (jonny)", $q);
$q =& $tree->push("smith's grandson, or jonny's son", $q);
$q =& $q->get_parent($tree); // lets jump back once...
$q =& $tree->push("jonny's daughter", $q);
$q =& $tree->root->chld[0]; // direct reference
$tree->push("another child for smith",$q);
$q =& $tree->root->chld[0]->chld[0]->chld[1]; // direct reference
$tree->push("jonny's daughter's child",$q);
$q =& $tree->root->chld[1]; // but this kind of reference can be dangerous
$tree->push("THIS IS WRONG, dr smith has no brothers or sisters",$q);
// so be sure you know your tree structure
// (if you had; $q =& $tree->push("doctor smith's brother", $tree->root);
// then the "THIS IS WRONG" push would be ok...)
print_r($tree);
?>