thelolcat thelolcat - 3 months ago 7
PHP Question

How can I detect a cycle when iterating array?

$arr = array(
'a' => 1,
'b' => 15,
'c' => 0,
);

$arr['c'] = &$arr;

print_r($arr); // <-- CYCLE


Do you know how can I detect if I have array values that somehow point to the existing element, or cause a infinite loop?

Answer

Use memory, Luke. When your iterator comes across the array as an elementof another one, just store reference/id of it to smth like set or list (or another suitable container, eg. array). So you memorize what array you have already processed, and then ignore it when meet next time or stop the loop.

<?php
function get_id(&$array) {
  return crc32(serialize($array)); 
}

# This will not work as expected. I leave it here just for future versions.
function get_id_alt(&$array) {
  $obj = (object) $array;
  return spl_object_hash($obj);
}

function iterate(array $input, &$reached=array(), $id_func='get_id') {
  // this is an unseen array, memorize it
  array_push($reached, $id_func($input));

  foreach($input as $key=>$item) {
    if (is_array($item)) {        // This is an array
      if (in_array($id_func($item), $reached)) {
        // We found an array that have been processed before. What will you do?
      } else {
        // Recurse!
        iterate($item, $reached);
      }
    } else {
      // It is not traversable value, do what you want here
    }
  }
}

PS: I'm using spl_object_hash as a ID-function, you may use another one, if prefered (but i don't know others that can identify the same objects, as this one does).

UPD: Using spl_object_hash doesn't give right results as of PHP 5.3.10: it treats any array as the same object regardless of its content. But using smth like %hash_fn%(serialize($array)) works well (beware of performance degradation!).