recursive array_diff()?

Question 1

I'm looking for some tool to give me a recursive diff of two arrays. What I envision is a web page with two color-coded tree-structures. On each tree, green are parts of the array which match in both arrays, and red is for parts of each that don't match the other. Something like the output of dBug

I have some code that gives me a nested array to populate a report. I'm developing a new method that should be faster, but I need to test the values and also the structure, to make sure it gives output identical to the old method.

Is there something out there that I can use? Or do I need to write this? Or is there another way to accomplish my goals?

Question 2

There is one such function implemented in the comments of array_diff.

function arrayRecursiveDiff($aArray1, $aArray2) {
  $aReturn = array();

  foreach ($aArray1 as $mKey => $mValue) {
    if (array_key_exists($mKey, $aArray2)) {
      if (is_array($mValue)) {
        $aRecursiveDiff = arrayRecursiveDiff($mValue, $aArray2[$mKey]);
        if (count($aRecursiveDiff)) { $aReturn[$mKey] = $aRecursiveDiff; }
      } else {
        if ($mValue != $aArray2[$mKey]) {
          $aReturn[$mKey] = $mValue;
        }
      }
    } else {
      $aReturn[$mKey] = $mValue;
    }
  }
  return $aReturn;
}

The implementation only handles two arrays at a time, but I do not think that really posses a problem. You could run the diff sequentially if you need the diff of 3 or more arrays at a time. Also this method uses key checks and does a loose verification.

Question 3

This will do what you want, except it does not put the first element (1005) in the array:

function create_array($number, $data)
{
    $result = array();
    foreach ($data as $row)
    {
        if ($row['enroller_id'] == $number)
        {
            $result[$row['id']] = create_array($row['id'], $data);
        }
    }
    return $result;
}

print_r(create_array(1005, $data));

Output:

Array
(
    [1000] => Array
        (
            [1101] => Array ()
            [1111] => Array ()
        )
)

Question 4

It's always fun to try solving "impossible" problems!

Here's a function that will detect recursive arrays if the recursion happens at the top level:

function is_recursive(array &$array) {
    static $uniqueObject;
    if (!$uniqueObject) {
        $uniqueObject = new stdClass;
    }

    foreach ($array as &$item) {
        if (!is_array($item)) {
            continue;
        }

        $item[] = $uniqueObject;
        $isRecursive = end($array) === $uniqueObject;
        array_pop($item);
        if ($isRecursive) {
            return true;
        }
    }

    return false;
}

See it in action.

Detecting recursion at any level would obviously be more tricky, but I think we can agree that it seems doable.

Update

And here is the recursive (pun not intended but enjoyable nonetheless) solution that detects recursion at any level:

function is_recursive(array &$array, array &$alreadySeen = array()) {
    static $uniqueObject;
    if (!$uniqueObject) {
        $uniqueObject = new stdClass;
    }

    $alreadySeen[] = &$array;

    foreach ($array as &$item) {
        if (!is_array($item)) {
            continue;
        }

        $item[] = $uniqueObject;
        $recursionDetected = false;
        foreach ($alreadySeen as $candidate) {
            if (end($candidate) === $uniqueObject) {
                $recursionDetected = true;
                break;
            }
        }

        array_pop($item);

        if ($recursionDetected || is_recursive($item, $alreadySeen)) {
            return true;
        }
    }

    return false;
}

See it in action.

Of course this can also be written to work with iteration instead of recursion by keeping a stack manually, which would help in cases where a very large recursion level is a problem.

Question 5

The difference between a recursive and non-recursive mutex has to do with ownership. In the case of a recursive mutex, the kernel has to keep track of the thread who actually obtained the mutex the first time around so that it can detect the difference between recursion vs. a different thread that should block instead. As another answer pointed out, there is a question of the additional overhead of this both in terms of memory to store this context and also the cycles required for maintaining it.

However, there are other considerations at play here too.

Because the recursive mutex has a sense of ownership, the thread that grabs the mutex must be the same thread that releases the mutex. In the case of non-recursive mutexes, there is no sense of ownership and any thread can usually release the mutex no matter which thread originally took the mutex. In many cases, this type of "mutex" is really more of a semaphore action, where you are not necessarily using the mutex as an exclusion device but use it as synchronization or signaling device between two or more threads.

Another property that comes with a sense of ownership in a mutex is the ability to support priority inheritance. Because the kernel can track the thread owning the mutex and also the identity of all the blocker(s), in a priority threaded system it becomes possible to escalate the priority of the thread that currently owns the mutex to the priority of the highest priority thread that is currently blocking on the mutex. This inheritance prevents the problem of priority inversion that can occur in such cases. (Note that not all systems support priority inheritance on such mutexes, but it is another feature that becomes possible via the notion of ownership).

If you refer to classic VxWorks RTOS kernel, they define three mechanisms:

mutex - supports recursion, and optionally priority inheritance. This mechanism is commonly used to protect critical sections of data in a coherent manner.
binary semaphore - no recursion, no inheritance, simple exclusion, taker and giver does not have to be same thread, broadcast release available. This mechanism can be used to protect critical sections, but is also particularly useful for coherent signalling or synchronization between threads.
counting semaphore - no recursion or inheritance, acts as a coherent resource counter from any desired initial count, threads only block where net count against the resource is zero.

Again, this varies somewhat by platform - especially what they call these things, but this should be representative of the concepts and various mechanisms at play.

Question 6

Adding to your existing recursive sql to get path:

WITH RECURSIVE path AS(
 select 
   t1.v1 as start,
   t1.v2 as end,  
   CAST(t1.v1 as VARCHAR(30)) as path 
   0 as depth
 from topo t1 
   left outer join topo as t2 on t1.v1=t2.v2 
 where t2.v2 IS null

 UNION ALL
 select 
   path.start ,
   t1.v2 as end,
   path.path || '>' || t1.v1,       
   path.d + 1 
 from path 
   inner join topo as t1 on t1.v1=path.end
)
SELECT * FROM path

Just adding in a couple of more fields to track what's happening as you traverse your hierarchy. Start will be static from the first query. It will be 1 for every record since that is your starting point. End is whatever node you are currently working. path will concatenate the end node as each new one is found. depth will tell you how far you traversed.

recursive array_diff()?

Answers

Update

php,arrays,recursion,diff