Move 'branches' of tree...?

[Anon]

Hi guys, sure one of you clever sods can make me feel dumb with this one 🙂

I need t be able to move a branch of a tree. That branch may also have branches so clearly I can't move the parent branch to one of it's child branches and I wouldn't want it to be it's own parent!

If someone could help me with a little pseudo-code or just a pointer in the right direction that'd be great. Heres the example:

id|parent|name

1|0|great grandma
2|1|grandma
3|1|grand_pa
4|3|father
5|4|son

Thanks

Nick

[[deleted]]

What exactly is you problem, the move or the making sure that you don't move it to the wrong parent?

[knickerlas]

Hi Vincent. Sorry, wasn't clear. My difficulty lies in making sure I don't move it to an invalid parent like itself, one of it's children etc.

Cheers

Nick

[jjoske]

function legalparent($id,$newParentId) {
while($newParent!=0 and $newparent!=$id)
{
$newparent=getparent($newparent);
}
if($newparrent==$id)
{
return false;
}
else
{
return true;
}

hope this helps

[knickerlas]

Looks good, I guess $newParentId is the same var throughout? (you've labeled it slightly differently in some cases)

Nick

[[deleted]]

I'd build a small recursive routine that goes all the way down the tree to fetch all the ID's of those elements. Then all you have to do is make sure the new parentid is not equal to any of those.

[jjoske]

yep, sorry about that confusion.

[knickerlas]

That's where I was originally heading. I'm a little stuck with the recursion bit though. Any chance of a little pseudo code so I can get the general idea Vincent?

Much appreciated

Nick

[[deleted]]

What you do is:

Get the id of the top-record in the branch that you want to move.

Then create a function that will fetch the ids of all the records that have the top record as a parent (the children).

That part is easy, now comes the tricky bit:
Everytime that function finds a child record, it should call itself with the id of the record it found.

That way, the function will start a new copy of itself, but now it will look for all records that have the newfly found child as a parent.
And if it finds children of that child, it will stat another copy of itself to look for it's childeren, etc etc untill there are no more children found.

For example:
id|parent|name

1|0|great grandma
2|1|grandma
3|1|grand_pa
4|3|father
5|4|son

I weant to find all the id's in the branch starting at grand_pa.
I lookup the id of grand_pa, and get 3.
I call the recursive function, and tell it to look for chilren of record 3.
That will find record 4, and when it find it ti will call itself to look for children of record 4, and it will find 5, and start another copy if itself looking for children of record 5, and it will find none.

That is the basic idea.
You have to make sure of two things:
One: the function must have a check builtin to make sure it will never try to find children of a record if that record is a child of itself.

id|parent|name

1|0|great grandma
...
6|6|village_idiot

The villagea_idiot is a child of itself, and will cause an infinate loop.

and two: you need to pass an array along from function to function in order to store all the IDs you find. You'll have to do this 'by reference'

[knickerlas]

Fantastic!

Thanks for taking time out to walk me through that one. I totally get it. I'll get on to it tonight after I've finished trying to make some cash and let you know how I get on.

Are you still planning on writing that article?

Regards

Nick

[[deleted]]

I've been quite busy writing the article, but it is far from complete and it needs some serious re-formatting.

it's at www.hvt-automation.nl/yapf
Let me know if there is anything completely unclear or missing.

[knickerlas]

Glad to. I actually wrote a couple myself but I'm afraid my PHP isn't really ggod enough for me to feel confident in submitting here.

I'll read it tonight and let you know what I think.

Nick

[[deleted]]

Feel free to email anything you thinkg might help others, and I'll put it on the YAPF! site.

[knickerlas]

actually they're already published

http://www.webmasterbase.com/article/590
http://www.webmasterbase.com/article/563

I'll have a good rummage round your site tonight. Maybe there's some common ground worth exploring?

Níck

[Anon]

Hi Vincent. Done it.
My only worry is that I'm over processing. It returns exactly what I want but if i put soem print routines in the function it appears to re-processing alot of stuff. Is that just the way recursion works?

Anyway, if you could have a quick look that'd be great.

function get_subcats($cat_id, $sub_cats=array()) {

$get_kids="SELECT cat_id FROM bookmarks_catagories ";
$get_kids.="WHERE parent_cat_id = '$cat_id'";
if(!($con=$this->_db_connect())) {
    return FALSE;
}
if(!($result=mysql_query($get_kids))) {
    return FALSE;
}
while($row=mysql_fetch_row($result)) {
    $temp[]=$row[0];
}
$sub_cats=array_merge($temp, $sub_cats);
if($temp) {
    foreach($temp as $child_cat_id) {
        $this->get_subcats($child_cat_id, &$sub_cats);
    }
}
return $sub_cats;

}

Cheers '

Nick

[[deleted]]

That looks to be just about right.

Yes recursion does seem to do a lot of processing. That's because it starts work, then spawns a copy of itself, does more work, etc, and when the copy is finished, the parent-continues with it's work, constantly jo-jo-ing up and down in parent-child levels.

In this particular case, it will run one query for every item in the branche. This is why 'real' databases like Oracle have special query options to make the database do the recursive part for you.

PS
A few constructive critisisms and thoughts for you to think about considering your function:
-is it required to open a 'new' connection for every query you want to run?
(I take it the $this object comes from some snipped code)
-you have a while-loop to gather all the results, then merge the array, then loop through the array. Doesn't that mean you effectively loop through the array twice?
-is it allowed to return 'false' in case of error, but an array in case of success?
-is there a point in declaring a default value of 'array()' for the second argument, when calling the function requires that you pass the second argument?

[Anon]

Cheers Vincent. Let me answer your points.

-is it required to open a 'new' connection for every query you want to run?

A--- Certainly not. I didn't see an alternative as it may be possible to call the method without a connection. You think pconnect() vetter?

-you have a while-loop to gather all the results, then merge the array, then loop through the array. Doesn't that mean you effectively loop through the array twice?

A--- I don't think so?

-is it allowed to return 'false' in case of error, but an array in case of success?

A--- Yes, do you see aproblem with that? I envision calling it like if(!($result=...

-is there a point in declaring a default value of 'array()' for the second argument, when calling the function requires that you pass the second argument?

A--- Yes. When you call it for the very first time it only needs an catagory_id. Else you'd have to pass it an empty array.

Ta very much 🙂

Nick

[[deleted]]

-you have a while-loop to gather all the results, then merge the array, then loop through the array. Doesn't that mean you effectively loop through the array twice?

A--- I don't think so?

V-- Well I do :-) Have a look at the edited version below

-is it allowed to return 'false' in case of error, but an array in case of success?

A--- Yes, do you see aproblem with that? I envision calling it like if(!($result=...

V-- yes, because an empty array is considered 'FALSE', so you cannot tell wether the function failed, or wether it just returned an empty array.

-is there a point in declaring a default value of 'array()' for the second argument, when calling the function requires that you pass the second argument?

A--- Yes. When you call it for the very first time it only needs an catagory_id. Else you'd have to pass it an empty array.

V-- which is exactly what you should do considering the previous question.

Have a look at this edited (and untested) version:

$sub_cats = array();
$this->get_subcats(12, $sub_cats);

function get_subcats($cat_id, &$sub_cats)
{ 
  $bNoErrorsFound = true;

  $get_kids="SELECT cat_id FROM bookmarks_catagories "; 
  $get_kids.="WHERE parent_cat_id = '$cat_id'"; 
  if(!($con=$this->_db_connect()))
  {
    $bNoErrorsFound = false;
  } 
  else
  {
    if(!($result=mysql_query($get_kids)))
    {
      echo mysql_error($con);
      $bNoErrorsFound = false;
    } 
    else
    {
      while($row=mysql_fetch_row($result))
      { 
        $sub_cats[]=$row[0]; 
        $this->get_subcats($cat_id, $sub_cats);
      };
      $sub_cats = array_unique($sub_cats);
    };
  };
  return $bNoErrorsFound;
} 

[knickerlas]

Hey Vincent. Really like that. Makes sense apart from one thing.

How do I get the array $subcats?

Seems to me Id be better using $subcats as the true/false indicator so then I'd either get false or an array?

What do think?

Nick

[Anon]

I take it all back! In the time it took me took me to switch from Win to Linux I realized the point.

As you can see passing by reference is not an area I have much experience of.

Ah... So much to learn and so little time. Ya gotta love it!

I'll check it out now.

Nick