PHP Bytesize : Recursive Hunting

What’s the best part about recursion? The answer is : recursion. As you can tell I’m quite the comedian! So recently I’ve been working quite heavily with Drupal 7’s ‘field’ api and an issue I came across was getting a list of all instances of the field in the super set given by the rather broard field_info_instances() function.

This function provides a multi dimeensional array keyed by the entity type. Given we have N instances in any number of entity types, we can’t just simply look in one of these subsets, we need to recursively hunt the entire set of instances to find anything keyed with our field name.

To do this we can easily throw together a handy search function

Let’s get the basis of our function built :

/**
 * Recursively hunt a multi dimensional array for all occurances of a key ->
 * value at any level
 *
 * @param array  $haystack  The haystack to search
 * @param string $needle The needle to find in the haystack
 *
 * @return array
**/
function _recursiveHunt(array $haystack, $needle) {
    $results = array();
    foreach ( ? as $key => $value) {
        if ($key === $needle) {
            $results[] = $value;
        }
    }
    return $results;
}

Obviously this won’t execute, infact it will through a massive wobbly about the for loop declaration – however we know that we will need an array to hold all occurances of our array, we know we’re going to have to loop over the haystack some how, and we know that if the key matches the needle we want to push the value for that needle on to our results stack.

Using a for loop on an array directly will essentially iterate over the top level values of that array one by one. Iteration is to iterate over the values in something. If we want to iterate over multiple levels we need to use a more complex iterator that knows implicitly how to iterate over what we give it. Luckily the SPL has us covered.

There are a tonne of iterators availiable, and you can find a list of them at php.net, what we are interested in is the RecursiveArrayIterator. This is, as the name implies, an iterator class that, targeting arrays that implements a recursive iterator interface. We can provide our $haystack to the constructor as a parameter, and this will instantiate an iterator based on our $haystack.

Great stuff. However this is only half of the story, if we were to use this directly in a loop, the for loop would still only iterate at the top level, we need to create a recursive iterator (that implements tree traversal) with our array iterator. SPL has us covered again with a RecursiveIteratorIterator class, which takes in as part of it’s constructor an iterator object that implements the recursive iterator interface. The instance of the RecusriveIteratorIterator class we create is the argument for our loop, it will perform tree traversal, on the array iterator we have instantiated with our array.

Feel free to read that again and eat a pringle sandwich.

Crunch crunch crunch, yum yum yum.

A way of thinking about this is to consider the other iterators availiable to us. Say I wanted to recursively search a file system? I could use the SPL RecursiveDirectoryIterator with a string representing the top directory to being the search from, and pass this instantiated object to the constructor for the RecursiveIteratorIterator class, as this object implements the required interface.

So my final code will look like this :

<?php
/**
* Recursively hunt an array for all occurrences of key/val
 *
 * @param array  $array  The haystack to search
 * @param string $needle The needle to find in the haystack
 *
 * @return array
**/
function _recursiveHunt(array $array, $needle) {
  $results = array();
  // Create a recursive iterator for our array
  $iterator = new RecursiveArrayIterator($array);
  // Create a recursive iterator for our iterator
  $recursive = new RecursiveIteratorIterator($iterator, RecursiveIteratorIterator::SELF_FIRST);
  foreach ($recursive as $key => $value) {
    if ($key === $needle) {
      $results[] = $value;
    }
  }
  return $results;
}

$haystack = array(
  'sandwich' => array(
    'bread' => 'white',
    'spread' => 'butter',
    'filling' => 'peanut butter'
  ),
  'bagel' => array(
    'bread' => 'seeded',
    'filling' => 'salmon',
    'toasted' => FALSE
  )
);

print_r(_recursiveHunt($haystack, 'filling'));

Now recurse!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s