Diff::shortestMiddleSnake

protected function shortestMiddleSnake(array $a, $lowerA, $upperA, array $b, $lowerB, $upperB)
{
	$result = array();

	$downK = $lowerA - $lowerB; // the k-line to start the forward search
	$upK = $upperA - $upperB; // the k-line to start the reverse search

	$delta = ($upperA - $lowerA) - ($upperB - $lowerB);
	$oddDelta = ($delta & 1) != 0;

	$maxD = (($upperA - $lowerA + $upperB - $lowerB) / 2) + 1;

	// init vectors
	$this->downVector[$downK + 1] = $lowerA;
	$this->upVector[$upK - 1] = $upperA;

	for ($d = 0; $d <= $maxD; $d++)
	{

		// Extend the forward path.
		for ($k = $downK - $d; $k <= $downK + $d; $k += 2)
		{
			// find the only or better starting point
			$x = 0;
			$y = 0;
			if ($k == $downK - $d)
			{
				$x = $this->downVector[$k + 1]; // down
			}
			else
			{
				$x = $this->downVector[$k - 1] + 1; // a step to the right
				if (($k < $downK + $d) && ($this->downVector[$k + 1] >= $x))
				{
					$x = $this->downVector[$k + 1];
				} // down
			}
			$y = $x - $k;

			// find the end of the furthest reaching forward D-path in diagonal k.
			while (($x < $upperA) && ($y < $upperB) && ($a[$x] == $b[$y]))
			{
				$x++;
				$y++;
			}
			$this->downVector[$k] = $x;

			// overlap ?
			if ($oddDelta && ($upK - $d < $k) && ($k < $upK + $d))
			{
				if ($this->upVector[$k] <= $this->downVector[$k])
				{
					$result['x'] = $this->downVector[$k];
					$result['y'] = $this->downVector[$k] - $k;
					return $result;
				}
			}
		}

		// Extend the reverse path.
		for ($k = $upK - $d; $k <= $upK + $d; $k += 2)
		{

			// find the only or better starting point
			$x = 0;
			$y = 0;
			if ($k == $upK + $d)
			{
				$x = $this->upVector[$k - 1]; // up
			}
			else
			{
				$x = $this->upVector[$k + 1] - 1; // left
				if (($k > $upK - $d) && ($this->upVector[$k - 1] < $x))
				{
					$x = $this->upVector[$k - 1];
				} // up
			}
			$y = $x - $k;

			while (($x > $lowerA) && ($y > $lowerB) && ($a[$x - 1] == $b[$y - 1]))
			{
				// diagonal
				$x--;
				$y--;
			}
			$this->upVector[$k] = $x;

			// overlap ?
			if (!$oddDelta && ($downK - $d <= $k) && ($k <= $downK + $d))
			{
				if ($this->upVector[$k] <= $this->downVector[$k])
				{
					$result['x'] = $this->downVector[$k];
					$result['y'] = $this->downVector[$k] - $k;
					return $result;
				}
			}
		}
	}
}