HelpNeeder HelpNeeder - 23 days ago 15
PHP Question

How to find pages without parent page?

I have a parent/child structure where the it can happen that parent can be deleted, and it's children are still going to be in the database. If that happen, the lowest parent should be set parent of 0.

I'm stuck with this problem because I'm not sure how to structure my (possibly recursive) loop.

I need to return an array of page ID's which parents do not exist; example:

array(5, 9, 8)
;

This is my data set, and the structure can be connected through the parent id; we can see that page ID 8 and 9 have parent of 7 which does not exist:

evar_export($orphans($pages));
$data = array (
0 => array (
'id' => 1,
'url' => 'Home-Page',
'parent' => 0
),
1 => array (
'id' => 2,
'url' => 'page1',
'parent' => 1
),
4 => array (
'id' => 5,
'url' => 'page4',
'parent' => 4
),
5 => array (
'id' => 6,
'url' => 'page5',
'parent' => 5
),
6 => array (
'id' => 8,
'url' => 'no-parent-1',
'parent' => 7
),
7 => array (
'id' => 9,
'url' => 'no-parent-2',
'parent' => 7
)
);


I've tried recursion, but I don't know how to catch the end of the sub-tree:

$orphans = function($array, $temp = array(), $index = 0, $parent = 0, $owner = 0) use(&$orphans) {
foreach ($array as $p) {
if($index == 0) {
$owner = $p['id'];
}

if ($index == 0 || $p['id'] == $parent) {
$temp[] = $p['id'];

$result = $orphans($array, $temp, $index + 1, $p['parent'], $owner);

if (isset($result)) {
return $result;
}
}
else {
return $temp;
}
}
};

Answer

I named your data array "pages" for this example:

$orphans = array();


foreach($pages as $p)
{   
    if($p['parent'] == 0)
        continue; //End this iteration and move on.

    $id = $p['id'];
    $parent = $p['parent'];
    $parentExists = false;
    foreach($pages as $p2)
    {
        if( $p2['id'] == $parent )
        {
            $parentExists = true;
            break; //Found, so stop looking.
        }
    }

    if(!$parentExists)
    {
        $orphans[] = $id;
    }
}

If you var_dump the $orphans array after this runs, you would get:

array(2) {
  [0]=>
  int(8)
  [1]=>
  int(9)
}

Which appears to be the desired result. Unfortunately nesting another foreach within the foreach is required unless you modify your data structure so the IDs are the keys (which I would advise to reduce resource usage to process this). Using the continue / break control structures at least limits usage.

Clarification on Nested Foreach

An ideal data structure would use key value pairs over sequential items, especially when processing dynamic data, because the keys are unknown. Taking your data for example, getting the 4th item's URL is easy:

$id = $pages[4]['id'];

But there is no relational / logical association between the 4th item and the associated data. Its sequential based on the what ever built the data. If, instead, you assign the id as the key, then we could easily find the parent id of the page with id 4:

$parent = $pages[4]['parent'];

So when doing a simple parse of your data to find non-existing parents, you would just have to do this:

foreach($pages as $p)
{   
    if($p['parent'] == 0)
        continue; //End this iteration and move on.

    $id = $p['id'];
    if(! isset($pages[$p['parent']])
    {
        $orphans[] = $id;
    }
}

Because then we would know for sure that the key is the id and then logically process the data in that fashion. And considering something like a page id is a primary key (non-duplicate), this should be entirely possible.

But without having a logical association between the key and value in the array, we have to look at the entire data set to find matches for each iteration, causing an exponential explosion of resource usage to complete the task.

Comments