Get all parent nodes with RecursiveArrayIterator

https://stackoverflow.com/questions/13629214

03-12-2021
|

Question

Essentially, I want to use the

$foo = new RecursiveIteratorIterator(new RecursiveArrayIterator($haystack));

Methodology, but instead of returning a flat array for foreach()ing through, keep the structure but only return a single great-grand-child node and it's parent nodes. Is this possible in PHP?

I've been tasked with optimising some of my company's (horrific) codebase. I found a function that recurses through an array, searching for a key. I can't replace this with a simple array_search() or array_key_exists() because the custom function also returns the parent nodes of the matched (found) key, instead of just a true or false.

How can I use RecursiveArrayIterator, RecursiveIteratorIterator or failing that, other built-in functions (i.e. as little custom code as possible) to return a matching node with it's parent tree from a search array? I want to get the fastest function possible, as currently this function spends 8 seconds executing 14 thousand times, hence my requirement to use built-in functions.

My existing attempt (below) is incredibly slow.

function search_in_array($needle, $haystack) {
    $path = array();

    $it = new RecursiveArrayIterator($haystack);
    iterator_apply($it, 'traverse', array($it, $needle, &$path));

    return $path;
}

function traverse($it, $needle, &$path) {
    while($it->valid()) {
        $key = $it->key();
        $value = $it->current();

        if(strcasecmp($value['id'], $needle) === 0) {
            $path[] = $key;
            return;
        } else if($it->hasChildren()) {
            $sub = null;
            traverse($it->getChildren(), $needle, &$sub);
            if($sub) {
                $path[$key] = $sub;
            }
        }

        $it->next();
    }
}

Example output for $needle = TVALL would look like this:

Array (
    [HOMECINEMA] => Array (
        [children] => Array (
            [HC-VISION] => Array (
                [children] => Array (
                    [0] => TVALL
                )
            )
        )
    )
)

The search array looks something like this (sorry for the vast-ness). There are more than two top-level nodes, but I've truncated it for brevity:

Solution

The example below will not necessarily be more performant (in time or memory requirements) but avoids manually recursing through the structure and shows an easier (IMHO) way to build your desired output array.

function search_in_array($needle, $haystack) {
    $path = array();

    $it = new RecursiveIteratorIterator(
        new ParentIterator(new RecursiveArrayIterator($haystack)),
        RecursiveIteratorIterator::SELF_FIRST
    );

    foreach ($it as $key => $value) {
        if (array_key_exists('id', $value) && strcasecmp($value['id'], $needle) === 0) {
            $path = array($needle);
            for ($i = $it->getDepth() - 1; $i >= 0; $i--) {
                $path = array($it->getSubIterator($i)->key() => $path);
            }
            break;
        }
    }

    return $path;
}

Reference

RecursiveIteratorIterator::SELF_FIRST iteration mode - required to see non-"leaf" items
ParentIterator - easy way to filter out the "leaf" items
RecursiveIteratorIterator::getDepth()
RecursiveIteratorIterator::getSubIterator()

Bonus

You could also use the RecursiveIteratorIterator::setMaxDepth() method to limit the recursion to n levels deep, if your array also goes much deeper.

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow