PHP - Find nested array1 in nested array2

Question

I need to look through Array1, finding any matching sequences from Array2, and update corresponding sub-arrays in Array1.

I previously had help on a similar question; Find array in array, in sequence

The previous solutions worked fantastically - but this time I'm dealing with more complicated data, and I need to update the Haystack array (rather than simply return the matches).

Array 1 : Haystack

Array ( 
    [0] => Array ( [v1] => aa   [v2] => ) 
    [1] => Array ( [v1] => bb   [v2] => ) 
    [2] => Array ( [v1] => cccc [v2] => ) 
    [3] => Array ( [v1] => bb   [v2] => ) 
    [4] => Array ( [v1] => aa   [v2] => ) 
    [5] => Array ( [v1] => bb   [v2] => ) 
    [6] => Array ( [v1] => cccc [v2] => ) 
    [7] => Array ( [v1] => bb   [v2] => ) 
) 

Array 2 : Needles

Array ( 
    [0] => Array ( [aa] => nnnn [bb] => nnn [cccc] =>n )
    [1] => Array ( [aa] => ddd  [bb] => dd )
)

Thus I should find "aa bb cccc" (needle[0]) in the haystack, and update the array to become;

Array ( 
    [0] => Array ( [v1] => aa   [v2] => nnnn ) 
    [1] => Array ( [v1] => bb   [v2] => nnn ) 
    [2] => Array ( [v1] => cccc [v2] => n ) 
    [3] => Array ( [v1] => bb   [v2] => ) 
    [4] => Array ( [v1] => aa   [v2] => ) 
    [5] => Array ( [v1] => bb   [v2] => ) 
    [6] => Array ( [v1] => cccc [v2] => ) 
    [7] => Array ( [v1] => bb   [v2] => ) 
) 

The 2 versions of code I have are;

Code version 1:

// cache array sizes
$haystack_len = count($haystack);
$needle_len = count($needle);

// shortlist the possible starting keys
$possible_keys = array_keys($haystack, $needle[0], true);

$results = array();

foreach ($possible_keys as $index) {
    // start searching
    $i = $index; $j = 0;
    while ($i < $haystack_len && $j < $needle_len) {
        if ($haystack[$i] !== $needle[$j]) {
            continue 2; // no match
        }
        ++$i; ++$j;
    }
    // match
    $results[] = range($index, $index + $needle_len - 1);
}

print_r($results);

and Code version 2:

function find_array_in_array($needle, $haystack) {
    $keys = array_keys($haystack, $needle[0]);
    $out = array();
    foreach ($keys as $key) {
        $add = true;
        $result = array();
        foreach ($needle as $i => $value) {
            if (!(isset($haystack[$key + $i]) && $haystack[$key + $i] == $value)) {
                $add = false;
                break;
            }
            $result[] = $key + $i;
        }
        if ($add == true) { 
            $out[] = $result;
        }
    }
    return $out;
}

But these are designed to work with flat arrays;

$haystack = array('a', 'b', 'a', 'b', 'c', 'c', 'a', 'b', 'd', 'c', 'a', 'b', 'a', 'b', 'c');
$needle = array('a', 'b', 'c');

Instead, I need them to work with the arrays as per the top (nested, and the needles are looking for matches to the needle[key] to the haystack[array][v1]

Though I've fiddled and faffed with the earlier code, I cannot beat it into the right shape :( I keep going through foreach loops to access things, and tried using for() etc.

foreach ($needlebox as $needles){
    foreach ($needles as $needlekey=>$needlevalue){
        foreach ($haystack as $haystackkey=>$haystackvalues){

            // insert above methods

        }
    }
}

but I hit the following issues; 1) Array2 (Needles) is huge, with the same needles appearing multiple times? 2) I only get a single match (even if Array 1 contains multiple matches to Array 2 Needle-n - it only finds a) the first or b) the last) 3) It matches regardless of order/sequence (I think I broke the code somehow, and it will match "cccc bb aa", when that order in Needles does not exist (it's instead "aa bb cccc").

I've now spent 2 days faffing with this wondering what I've done wrong.

I've attempted to use both solutions (the foreach and the for methods) ... but I cannot get either of them to work.

Answer 1

If I understand correctly what you are trying to achieve, you could do it like this (see comments in code):

/* Process one needle (look into haystack 
   and modify it accordingly) */
function processNeedle(&$haystack, $needle) {
    $needleKeys   = array_keys($needle);
    $needleValues = array_values($needle);
    $needleLen    = count($needle);
    $haystackLen  = count($haystack);

    /* Find indexes where a match begins */
    $matches = array();
    for ($i = 0; $i < ($haystackLen - $needleLen + 1); $i++) {
        $match = true;
        for ($j = 0; $j < $needleLen; $j++) {
            if ($haystack[$i + $j]["v1"] != $needleKeys[$j]) {
                $match = false;
                break;
            }
        }
        if ($match) {
            $matches[] = $i;
            $i += $needleLen - 1;
        }
    }

    /* Do the actual replacement for all matches */
    forEach ($matches as $startIdx) {
        for ($j = 0; $j < $needleLen; $j++) {
            $haystack[$startIdx + $j]["v2"] = $needleValues[$j];
        }
    }
}

See, also, this short demo.