CODEWITHSUNDEEP
phprecursionpass-by-reference
sevenWonders
sevenWonders

Reputation: 185

Recursion and passing by reference

I have a tree of categories of the following structure:

[6] => Array
    (
        [id] => 6
        [name] => computers
        [productCount] => 0
        [children] => Array
            (
                [91] => Array
                    (
                        [id] => 91
                        [name] => notebook
                        [productCount] => 5
                        [children] => Array
                            (
                            )
                    )

                [86] => Array
                    (
                        [id] => 86
                        [name] => desktop
                        [productCount] => 0
                        [children] => Array
                            (
                            )
                    )
            )
    )

Beside a subcategory, each category may contain products (like a folder may contain subfolders and just files).

I'm trying to write a recursive function which I want to take this array as reference and strip both leaf categories with [productCount] = 0 and all parent categories that contain such empty nodes. In other words, after processing I want to have only those categories that hold products on any sublevels.

I've wrote some code, now debugging it and it doesn't strip empty nodes. May be I'm not using references properly. Please, help me fix it, if possible.

    function pruneTree( & $node) {
    if ( ! $node['children'] && ! $node['productCount']) {
        unset($node);
    }
    if ( ! empty($node['children'])) {
        foreach ($node['children'] as $key => $child) {
            pruneTree($node['children'][$key]);
        }
    }
    return;
}

Upvotes: 9

Views: 8760

Answers (5)

poring91
poring91

Reputation: 523

I'm searching for this case too and somehow, I stumbled upon this thread just now. And found out that using unset is a mistake. F! PHP. It's different to how I use in C/C++

Here's my solution without using function unset at all and I've tried it and success.

I know Gumbo's solution is right on and this is old thread, but I just want to share some idea that is different, not yet shared here and easier to read.

My idea is :

  1. Declare array of new branches / leaves node to store new nodes.
  2. Do Postorder Tree Traversal.
  3. At the node's action, insert condition to node that you need to keep, not you want to remove, because unset could mislead you. Store it to the declared array.
  4. Replace old list with new list into the function's param.
    function pruneTree(& $tree) {

        $new_tree = [];  // Declare to rebuild the nodes

        foreach($tree as $node) {  // Traverse the branch

            if(!empty($node["children"])) { // Visit the children branch first in postorder
                pruneTree($node["children"]);
            }

            /* Node's action */
            if(!empty($node["children"]) || $node["productCount"] > 0) {
                $new_tree [] = $node;
            }
            /* End of node's action */

        }

        $tree = $new_tree ; // Replace the tree with their new filtered children
    }

Upvotes: 0

lsd
lsd

Reputation: 670

I would do that. Notice the "&" in the foreach.

function pruneTree(&$node)
{
    foreach ($node as $index => &$value) {
        if (empty($value)) {
            unset($node[$index]);
        } elseif (is_array($value)) {
            pruneTree($value);
        }
    }
}

Upvotes: 2

Aiphee
Aiphee

Reputation: 9156

I dont know if this is the case, but when i needed to change values recursively in array, i needed to pass & to the foreach value as well.

private function convertXMLPart(&$array) {
        foreach ($array as $rowKey => &$row) {
            if (gettype($row) != 'string') {
                $row = (array)$row;
                if (!empty($row['@attributes'])) {
                    foreach ($row['@attributes'] as $key => $value) {
                        $row[$key] = $value;
                    }
                    unset($row['@attributes']);
                    $array[$rowKey] = $row;
                }
                $this->convertXMLPart($row);
            }
        }
    }

Upvotes: 1

RabidFire
RabidFire

Reputation: 6330

You could also change the parameter in the function to take an array of nodes instead of a single node. This changes the recursion slightly, and prevents the need to pass along a key:

function pruneTree(&$nodes) {
    foreach ($nodes as $key => $node) {
        if (!$node['children'] && !$node['productCount']) {
            unset($nodes[$key]);
        } elseif (!empty($node['children'])) {
            pruneTree($nodes[$key]['children']);
            // This line checks if all the children have been pruned away:
            if (empty($nodes[$key]['children'])) {
                unset($nodes[$key]);
            }
        }
    }
}

Also, added a check that ensures that if all child nodes are pruned, the parent (now, leaf) node also gets pruned.

Hope this helps!

Test data:

$data = array(
    6 => array(
        'id' => 6,
        'name' => 'computers',
        'productCount' => 0,
        'children' => array(
            91 => array(
                'id' => 91,
                'name' => 'notebook',
                'productCount' => 5,
                'children' => array()
            ),
            86 => array(
                'id' => 86,
                'name' => 'desktop',
                'productCount' => 0,
                'children' => array()
            )
        )
    )
);

The Call:

pruneTree($data);
echo '<pre>';
print_r($data);
echo '</pre>';

Upvotes: 6

Gumbo
Gumbo

Reputation: 655219

unset deletes only the reference but not the referenced variable:

If a variable that is PASSED BY REFERENCE is unset() inside of a function, only the local variable is destroyed. The variable in the calling environment will retain the same value as before unset() was called.

So you need to pass the parent array and the key to delete that variable:

function pruneTree(&$parent, $key) {
    $node = &$parent[$key];
    if (!$node['children'] && !$node['productCount']) {
        unset($parent[$key]);
    }
    if (!empty($node['children'])) {
        foreach ($node['children'] as $key => &$child) {
            pruneTree($node['children'], $key);
        }
    }
}

Upvotes: 6

Related Questions