PHP Array Diff

php-diff.php

<?php

// Array Diff

class DiffElem
{
    const TYPE_KEEP = 0;
    const TYPE_REMOVE = 1;
    const TYPE_ADD = 2;

    /** @var int One of the TYPE_* constants */
    public $type;
    /** @var mixed Is null for add operations */
    public $old;
    /** @var mixed Is null for remove operations */
    public $new;

    public function __construct(int $type, $old, $new)
    {
        $this->type = $type;
        $this->old = $old;
        $this->new = $new;
    }
}

function diff(array $old, array $new)
{
    list($trace, $x, $y) = calculateTrace($old, $new);
    return extractDiff($trace, $x, $y, $old, $new);
}

function isEqual($a, $b)
{
    return $a === $b;
}

function calculateTrace(array $a, array $b)
{
    $n = \count($a);
    $m = \count($b);
    $max = $n + $m;
    $v = [1 => 0];
    $trace = [];
    for ($d = 0; $d <= $max; $d++) {
        $trace[] = $v;
        for ($k = -$d; $k <= $d; $k += 2) {
            if ($k === -$d || ($k !== $d && $v[$k - 1] < $v[$k + 1])) {
                $x = $v[$k + 1];
            } else {
                $x = $v[$k - 1] + 1;
            }

            $y = $x - $k;
            while ($x < $n && $y < $m && isEqual($a[$x], $b[$y])) {
                $x++;
                $y++;
            }

            $v[$k] = $x;
            if ($x >= $n && $y >= $m) {
                return [$trace, $x, $y];
            }
        }
    }
    throw new \Exception('Should not happen');
}

function extractDiff(array $trace, int $x, int $y, array $a, array $b)
{
    $result = [];
    for ($d = \count($trace) - 1; $d >= 0; $d--) {
        $v = $trace[$d];
        $k = $x - $y;

        if ($k === -$d || ($k !== $d && $v[$k - 1] < $v[$k + 1])) {
            $prevK = $k + 1;
        } else {
            $prevK = $k - 1;
        }

        $prevX = $v[$prevK];
        $prevY = $prevX - $prevK;

        while ($x > $prevX && $y > $prevY) {
            $result[] = new DiffElem(DiffElem::TYPE_KEEP, $a[$x - 1], $b[$y - 1]);
            $x--;
            $y--;
        }

        if ($d === 0) {
            break;
        }

        while ($x > $prevX) {
            $result[] = new DiffElem(DiffElem::TYPE_REMOVE, $a[$x - 1], null);
            $x--;
        }

        while ($y > $prevY) {
            $result[] = new DiffElem(DiffElem::TYPE_ADD, null, $b[$y - 1]);
            $y--;
        }
    }
    return array_reverse($result);
}

$a = ["Mr. Jones", "Mr. Banda", "Mrs. Smith"];
$b = ["Mr. Jones", "Mr. Banda", "Mrs. Lee"];
var_dump(diff($a, $b));
/*
array(4) {
  [0]=>
  object(DiffElem)#4 (3) {
    ["type"]=>
    int(0)
    ["old"]=>
    string(9) "Mr. Jones"
    ["new"]=>
    string(9) "Mr. Jones"
  }
  [1]=>
  object(DiffElem)#3 (3) {
    ["type"]=>
    int(0)
    ["old"]=>
    string(9) "Mr. Banda"
    ["new"]=>
    string(9) "Mr. Banda"
  }
  [2]=>
  object(DiffElem)#2 (3) {
    ["type"]=>
    int(1)
    ["old"]=>
    string(10) "Mrs. Smith"
    ["new"]=>
    NULL
  }
  [3]=>
  object(DiffElem)#1 (3) {
    ["type"]=>
    int(2)
    ["old"]=>
    NULL
    ["new"]=>
    string(8) "Mrs. Lee"
  }
}
*/