2

My question is similar to Searching for an array key branch inside a larger array tree - PHP, but for different limitations (like processing on the fly, etc) and why not for knowledge sake I would like to implement it using just PHP recursion.

Consider this data:

array(
    'root_trrreeee1' => array(
        'path1' => array(
            'description' => 'etc',
            'child_of_path_1' => array(
                array('name' => '1'),
                array('name' => '1')
            )
        ),
        'path1' => array(
            'description' => 'etc',
            'child_of_path_1' => array(
                array('name' => '1'),
                array('name' => '1')
            )
        ),
    ),
    'name' => '1',
    1 => array('name' => '1'),
    'another_leaf' => '1'
)

If I search for array('name' => '1') it should return the path I need to traverse to get to that value root_trrreeee1.path1.child_of_path_1.o, preferably returned as array:

array(
    0 => root_trrreeee1
    1 => path1
    2 => child_of_path_1
    3 => 0
)

This is the recursive function I've tried to implement but its not working:

function multidimensional_preserv_key_search($haystack, $needle, $path = array(), &$true_path = array())
{
    if (empty($needle) || empty($haystack)) {
        return false;
    }

    foreach ($haystack as $key => $value) {

        foreach ($needle as $skey => $svalue) {

            if (is_array($value)) {
                $path = multidimensional_preserv_key_search($value, $needle, array($key => $path), $true_path);
            }

            if (($value === $svalue) && ($key === $skey)) {
                $true_path = $path;
                return $true_path;
            }
        }

    }

    if (is_array($true_path)) { return array_reverse(flatten_keys($true_path)); }
    return $path;
}


function flatten_keys($array)
{
    $result = array();

    foreach($array as $key => $value) {
        if(is_array($value)) {
            $result[] = $key;
            $result = array_merge($result, self::flatten_keys($value));
        } else {
            $result[] = $key;
        }
    }

    return $result;
}

it returns just an empty array. Thanks in advance.

Similar questions I've found:

Community
  • 1
  • 1
eagleal
  • 1,368
  • 9
  • 15
  • have you got any solutions. i am stuck on the same point – dhpratik Aug 27 '14 at 10:56
  • 1
    I implemented a custom Backtracking Algorithm: http://en.wikipedia.org/wiki/Backtracking (code on the page) – eagleal Aug 28 '14 at 15:22
  • For those having the same problem, its called **Backtracking** (as in algorithm). There is a working pseudo-code on Wikipedia: http://en.wikipedia.org/wiki/Backtracking – eagleal Aug 28 '14 at 15:25

1 Answers1

0

This recursive function searches for the first occurrence of a value in a multidimensional array and returns the path to it as an array of keys.

function array_value_path($array, $needle, &$path)
{
    foreach($array as $key => $value) {
        if ($value == $needle || is_array($value) && array_value_path($value, $needle, $path)) {
            array_unshift($path, $key);
            return true;
        }
    }
    return false;
}

fiddle

array_value_path($a, ['name' => 1], $path);

Array
(
    [0] => root_trrreeee1
    [1] => path1
    [2] => child_of_path_1
    [3] => 0
)

array_value_path($a, 1, $path);

Array
(
    [0] => root_trrreeee1
    [1] => path1
    [2] => child_of_path_1
    [3] => 0
    [4] => name
)
id'7238
  • 2,428
  • 1
  • 3
  • 11