Page 1 of 1

Recursive Functions - ugh

Posted: Tue Jul 29, 2008 12:59 pm
by Chalks
I have a love/hate relationship with recursive functions. I love it when they work, but I hate working out the logic of them. Unfortunately, this one has me stumped and I need some help.

I have a form that allows you to input a new page into my database. The fields are:
name, type, parent, deleted, order

"deleted" and "order" are used to show if a page has been deleted and its order, respectively. Allowed types are "regular", "unique", and "nodelete" (nodelete is only for the index page). If the page type is unique, it has no parent, and doesn't show up in any menus. If the page type is regular, it _must_ have a parent. You can use any page (including unique pages) as a parent. If the parent is a unique page or the index page, each page with that parent will show up on the parent's main menu as menu headings (i.e. Home, FAQ, Members). If the parent is a regular page, it will show up under the menu that the regular page is on. That's the theory anyways. I'm having trouble getting this to work properly.

My mysql query to pull all the pages just takes everything out sorted by order (excluding deleted pages). "Order" is a user input number, so it doesn't necessarily mean anything, and I can't rely on it for true order. Here's the rough pseudo code I've come up with to sort the pages:

Code: Select all

function getChild($pages, $originalPages, $originalParents)
{
// $originalPages and $originalParents are the same length, and correspond 1 to 1 for each page's parent.
  foreach($pages AS $p)
  {
    for($i=0; $i < $originalParents.length; $i++)
        $sorted = append($originalPages[i]);  //append to the $sorted array.  Don't remember the actual code to append to arrays.
 
    $finalSort = append(" -" . $p);  // children of child pages should appear as " - - -child 3"
 
    if(!empty($sorted))
      $finalSort = append(getChilds($sorted, $Opgs, $Oprs));
  }
  if(empty($sorted));
    return null;
  else
    return $finalSort;
}
I know that this won't work the way I want. It's sort of close though. Here's an example of what I'd like to have happen:

Code: Select all

$pages = array("index", "parent1", "parent2", "child1", "child2", "child3", "child4", "child5", "child6");
$originalPages = array("index", "parent1", "parent2", "child1", "child2", "child3", "child4", "child5", "child6");
$originalParents = array("", "index", "index", "parent2", "parent1", "parent2", "child2", "parent1", "parent1");
 
//send through getChild($pages, $originalPages, $originalParent)
 
$desiredArray = array("index", "parent1", " -child2", " - -child4", " -child5", " -child6", "parent2", " -child1", " -child3");


I've been wracking my head for the past two hours (and drawing diagrams, and writing and rewriting code) and still can't come up with anything functional. I'm starting to wonder if a recursive function is the best way to go about this. The reason I started with recursive is because each page could have potentially hundreds of child pages and sub-child pages. It's not likely, but it is possible. Maybe I can structure my query better to pull the pages out slightly more organized? Any ideas on how to fix this function or do this a better way?

Thanks!

Re: Recursive Functions - ugh

Posted: Tue Jul 29, 2008 3:58 pm
by Eran
Looking at your example data, I don't see anything that represents which children belong to which parent. Could you show some real data which we could work with?

Re: Recursive Functions - ugh

Posted: Tue Jul 29, 2008 4:35 pm
by Chalks
pytrin wrote:Looking at your example data, I don't see anything that represents which children belong to which parent. Could you show some real data which we could work with?
I can't give you "real" data mainly because it's all user generated, and since this isn't live yet, the user hasn't generated anything. I didn't make it really clear though. The array $originalPages is a list of _all_ the regular pages. The array $originalParents is a list of _all_ the parents. So, if $originalParents[x] is "index" than the parent of $originalPages[x] is "index". So, looking at the example data that I posted above, the parent of $originalData[5] is "parent2".

If you mean that the parents don't keep track of what children they have, you're right. I only have a way in place to know what the parent is, but I have no way of knowing what the child is (without searching the parents array for the parent name).

I hope that makes sense.

Re: Recursive Functions - ugh

Posted: Tue Jul 29, 2008 5:02 pm
by Eran
I didn't mean 'real' real data, only 'real' psuedo data ;)
What I meant was, usually database results are returned as multi-dimensional arrays, which the data you showed is not. Suppose we have the following data returned:

Code: Select all

 
$pages = array(
    0 => array(
        'title' => 'some title',
        'parent' => 5,
        'id' => 10
    ),
    1 => array(
        'title' => 'another title',
        'parent' => 10,
        'id' => 30
    ),
    2 => array(
        'title' => 'nothing new',
        'parent' => null,
        'id' => 5
    )
);
 
This looks like a database results array. How does your data looks like when returned from the database?

Re: Recursive Functions - ugh

Posted: Tue Jul 29, 2008 5:14 pm
by VladSun
pytrin wrote:This looks like a database results array. How does your data looks like when returned from the database?

Also, what about doing it by using more complex SQL query and a *little* of PHP code?

Re: Recursive Functions - ugh

Posted: Tue Jul 29, 2008 5:39 pm
by Chalks
pytrin wrote:This looks like a database results array. How does your data looks like when returned from the database?
Ah, I see what you mean. I think this is part of my problem, I'm very new to database queries and I think my (very) simplistic approach is not going to work in this case. What I have been doing for this project is pulling a one dimension array that contained the page names, and a one dimension array that contained all the parents (of those pages). I could pull the data the way you suggested, but in effect that's what I'm doing already (just with 2 queries instead of 1). So, yes. The examples I showed really are representative of what I'm pulling from the database. I did have it so that the parents were actually varchars, but I'll change it so that the parents are just ints that point to the parent id number since that seems to make more sense.
VladSun wrote:Also, what about doing it by using more complex SQL query and a *little* of PHP code?
If I could do it that way, I'd love to. I just don't know enough about queries to structure it in such a way that it sorts the way I need it to.

Edit: I don't know if this will help clarify things any, but here's a mockup of what the frontend looks like: Create a Page

Re: Recursive Functions - ugh

Posted: Wed Jul 30, 2008 5:56 pm
by Chalks
EDIT: This is why I love recursive functions. 8 lines of code doing all that? Yes please! :D
Ok, cool. I've gotten this done a bit better now. I redid my queries and pulled stuff out in a much more organized way. My recursive function looks like this now:

Code: Select all

function getChilds($pg, $opgs)
{
  $final[] = $p;
  for($i=0; $i<count($opgs); $i++)
    if($pg == $opgs[$i]['parent'])
      $final[] = getChilds($opgs[$i]['name'], $opgs);
   return $final;
}
This requires me to input the main pages one at a time (easy). Here's what I'm getting back (from print_r):
Array ( [0] => A [1] => Array ( [0] => B ) [2] => Array ( [0] => C ) [3] => Array ( [0] => D ) [4] => Array ( [0] => E [1] => Array ( [0] => F ) ) )

I would like to take that (potentially x-dimensional) array and break it down like so:

Code: Select all

A
 -B
 -C
 -D
 -E
 - -F
Multidimensional arrays are almost as confusing for me as recursive functions are. Any advice for going about this? I'm sure it's simple, but I can't find any easy ways to do it.