WP_Text_Diff_Renderer_Table::interleave_changed_lines( array $orig, array $final )

	public function interleave_changed_lines( $orig, $final ) {

		// Contains all pairwise string comparisons. Keys are such that this need only be a one dimensional array.
		$matches = array();
		foreach ( array_keys($orig) as $o ) {
			foreach ( array_keys($final) as $f ) {
				$matches["$o,$f"] = $this->compute_string_distance( $orig[$o], $final[$f] );
			}
		}
		asort($matches); // Order by string distance.

		$orig_matches  = array();
		$final_matches = array();

		foreach ( $matches as $keys => $difference ) {
			list($o, $f) = explode(',', $keys);
			$o = (int) $o;
			$f = (int) $f;

			// Already have better matches for these guys
			if ( isset($orig_matches[$o]) && isset($final_matches[$f]) )
				continue;

			// First match for these guys. Must be best match
			if ( !isset($orig_matches[$o]) && !isset($final_matches[$f]) ) {
				$orig_matches[$o] = $f;
				$final_matches[$f] = $o;
				continue;
			}

			// Best match of this final is already taken?  Must mean this final is a new row.
			if ( isset($orig_matches[$o]) )
				$final_matches[$f] = 'x';

			// Best match of this orig is already taken?  Must mean this orig is a deleted row.
			elseif ( isset($final_matches[$f]) )
				$orig_matches[$o] = 'x';
		}

		// We read the text in this order
		ksort($orig_matches);
		ksort($final_matches);

		// Stores rows and blanks for each column.
		$orig_rows = $orig_rows_copy = array_keys($orig_matches);
		$final_rows = array_keys($final_matches);

		// Interleaves rows with blanks to keep matches aligned.
		// We may end up with some extraneous blank rows, but we'll just ignore them later.
		foreach ( $orig_rows_copy as $orig_row ) {
			$final_pos = array_search($orig_matches[$orig_row], $final_rows, true);
			$orig_pos = (int) array_search($orig_row, $orig_rows, true);

			if ( false === $final_pos ) { // This orig is paired with a blank final.
				array_splice( $final_rows, $orig_pos, 0, -1 );
			} elseif ( $final_pos < $orig_pos ) { // This orig's match is up a ways. Pad final with blank rows.
				$diff_pos = $final_pos - $orig_pos;
				while ( $diff_pos < 0 )
					array_splice( $final_rows, $orig_pos, 0, $diff_pos++ );
			} elseif ( $final_pos > $orig_pos ) { // This orig's match is down a ways. Pad orig with blank rows.
				$diff_pos = $orig_pos - $final_pos;
				while ( $diff_pos < 0 )
					array_splice( $orig_rows, $orig_pos, 0, $diff_pos++ );
			}
		}

		// Pad the ends with blank rows if the columns aren't the same length
		$diff_count = count($orig_rows) - count($final_rows);
		if ( $diff_count < 0 ) {
			while ( $diff_count < 0 )
				array_push($orig_rows, $diff_count++);
		} elseif ( $diff_count > 0 ) {
			$diff_count = -1 * $diff_count;
			while ( $diff_count < 0 )
				array_push($final_rows, $diff_count++);
		}

		return array($orig_matches, $final_matches, $orig_rows, $final_rows);
	}