OOP: building a tree (very lengthy)

[Anon]

I'm having problems updating adding children to the nodes of a tree I'm trying to build. Any help appreciated. The code goes like this:

class Node {
var $id;
var $children;
var $no_children;

function Node($nodeid) {
printf("Constructing object (%s)...<br>", $nodeid);
$this->id = $nodeid;
$this->no_children = 0;
}

function AddChild($child) {
printf("Adding child %s to parent %s", $child->id, $this->id);
$this->children[$this->no_children++] = $child;
reset($this->children);
printf(" Node %s now has %s children<br>", $this->id, count($this->children));
}

function FindNode($nodeid) {
if ($this->children) {
while(list($key, $val) = each($this->children)) {
if($val->id == $nodeid) {
$node = $val; break;
} else {
$node = $val->FindNode($nodeid);
if($node) break;
}
}
reset($this->children);
}
else {
printf("Node has no children<br>");
}
return $node;
}

function Show() {
printf("Node<br>----<br>Id: %s<br>Number of children: %s<br>", $this->id, $this->no_children);
if ($this->children) {
while(list($key, $val) = each($this->children)) {
$val->Show();
}
reset($this->children);
}
printf("----<br>");
}
} #class Node

$dummyroot = new Node("0");

$new_node = new Node("100");
$dummyroot->AddChild($new_node);
$new_node = new Node("200");
$dummyroot->AddChild($new_node);
$new_node = new Node("300");
$dummyroot->AddChild($new_node);
$new_node = new Node("400");
$dummyroot->AddChild($new_node);
$new_node = new Node("500");
$dummyroot->AddChild($new_node);
$new_node = new Node("600");
$dummyroot->AddChild($new_node);

$new_node = new Node("110");
$parent = $dummyroot->FindNode("100");
$parent->AddChild($new_node);
$new_node = new Node("120");
$parent = $dummyroot->FindNode("100");
$parent->AddChild($new_node);
$new_node = new Node("220");
$parent = $dummyroot->FindNode("200");
$parent->AddChild($new_node);
$new_node = new Node("330");
$parent = $dummyroot->FindNode("300");
$parent->AddChild($new_node);

$dummyroot->Show();

---

which produces this result:

Constructing object (0)...
Constructing object (100)...
Adding child 100 to parent 0 Node 0 now has 1 children
Constructing object (200)...
Adding child 200 to parent 0 Node 0 now has 2 children
Constructing object (300)...
Adding child 300 to parent 0 Node 0 now has 3 children
Constructing object (400)...
Adding child 400 to parent 0 Node 0 now has 4 children
Constructing object (500)...
Adding child 500 to parent 0 Node 0 now has 5 children
Constructing object (600)...
Adding child 600 to parent 0 Node 0 now has 6 children
ObjectConstructing object (110)...
ObjectAdding child 110 to parent 100 Node 100 now has 1 children
Constructing object (120)...
Adding child 120 to parent 100 Node 100 now has 1 children
Constructing object (220)...
Node has no children
Adding child 220 to parent 200 Node 200 now has 1 children
Constructing object (330)...
Node has no children
Node has no children
Adding child 330 to parent 300 Node 300 now has 1 children

Node

Id: 0
Number of children: 6

Node

Id: 100

Number of children: 0

Node

Id: 200

Number of children: 0

Node

Id: 300

Number of children: 0

Node

Id: 400

Number of children: 0

Node

Id: 500

Number of children: 0

Node

Id: 600

Number of children: 0

---

[simon_belak]

i would trie something like this:

class Node {
var $id;
var $children;
var $no_children;

    function Node($nodeid)
    {
            printf("Constructing object (%s)...<br>", $nodeid);
            $this->id = $nodeid;
            $this->no_children = 0;
            $this->children = array();
    }

    function AddChild(&$child)
    {
            printf("Adding child %s to parent %s", $child->id, $this->id);
            $this->children[$this->no_children++] = &$child;
            printf(" *** Node %s now has %s children***<br>", $this->id, $this->no_children);
    }

    function &FindNode($nodeid)
    {
            if (0<$this->no_children)
            {
                    foreach ($this->children as $child)
                    {
                            if ($child->id == $nodeid)
                            {
                                    return $child;
                            }
                            else
                            {
                                    $node = $child->FindNode($nodeid);
                                    if ($node!=0)
                                    {
                                            return $node;
                                    }
                            }
                    }
            }
            else
            {
                    print('Node has no children<br>');
            }
            return 0;
    }

    function Show()
    {
            printf("Node<br>----<br>Id: %s<br>Number of children: %s<br>", $this->id, $this->no_children);
            if (0<$this->no_children)
            {
                    foreach ($this->children as $child)
                    {
                            $child->Show();
                    }
            }
            printf("----<br>");
    }

    function GetChildren()
    {
            return $this->children;
    }

    function GetNumChildren()
    {
            return $this->no_children;
    }

    function GetId()
    {
            return $this->id;
    }

} #class Node

this works only in php4, if you need it to work with php3 as well replace foreach with for and make function findeNode return by value insted of by refrence.
I have added accessor funcctions (Get...) as well, becouse if you are doing it the OOP way do it like it should be done!

hth
Simon

[Anon]

Thank you very much for your helpful reply! I'm having slight problems converting your code to php3, however. The line
$this->children[$this->no_children++] = &$child;
results in a parsing error.
Also, I'm wondering what the consequences are of having FindNode return by value instead of reference. I would be very grateful if you could provide some further clues...

[simon_belak]

my mistake: php3 is very limiting when it comes to refrence. if you ommit the & in that troublesome line it should work ok.
Now about refrence:
if you return by refrence a variable to witch you assign the function return value will be a sort of an alias. So if you change that variable the variable witch you have passed by refrence will change allso.
But if you return by value the var to witch you assign the return value will become a copy of the var being passed from the function.
And since with passing by refrence you don't create extra copies of vars passing by refrencce shoul be faster and less memory demanding as well.
I hope this makes any sence.

           Simon

[Anon]

It does start to make sense to me now. I guess it means that I should use a different data structure, as I am unable to return a pointer to the original object from the Find-function. What I get is a pointer to a copy of the object, correct? Thank you very much - you've been most helpful!

[Anon]

I had a difficult time getting the following code (taken from previous post) to work:

function &FindNode($nodeid) {
if (0<$this->no_children) {
foreach ($this->children as $child) {
if ($child->id == $nodeid) {
return $child;
} else {
$node = $child->FindNode($nodeid);
if ($node!=0) {
return $node;
}
}
}
} else {
print('Node has no children<br>');
}
return 0;
}

The problem is that apparently anytime you make an assignment of a variable without using the '=&' syntax you are creating a new copy of the variable. If the FindNode() method is only to be used for retreiving data, then this is fine. If, however, you'd like to modify the nodes you find -- as I did -- then this function will not work. (at least w/ my environment and PHP 4.0.6).

One problematic assignment is fairly obvious:

$node = $child->FindNode($nodeid);
That's creating a copy. It should be
$node =& $child->FindNode($nodeid);
to create a "pointer" to the node.

The other problematic assignment in this function took me a little longer to realize:

foreach ($this->children as $child) {
This is sort of an implicit assignment (i.e.
$child = $this->children[]) but it just as surely is creating copies of each child pointer. There may be various ways of solving this problem; I just made an explicit for-loop:
for($i=0; $i<sizeof($this->children); $i++) {
$child =& $this->children[$i];
...etc.
That solved my problem.

I struggled with these issues for awhile -- hope this helps someone else struggle less.

Cheers,
Hans

P.S. I'm still assuming that this will only work in PHP4.