Implements the Myers diff algorithm.

Myers, Eugene W. "An O (ND) difference algorithm and its variations." Algorithmica 1.1 (1986): 251-266.

  • template T
  • internal
public __construct(callable $isEqual)

Create differ over the given equality relation.

  • param callable $isEqual Equality relation
public diff(array $old, array $new) : array

Calculate diff (edit script) from $old to $new.

  • param \T[] $old Original array
  • param \T[] $new New array
  • return \DiffElem[] Diff (edit script)
public diffWithReplacements(array $old, array $new) : array

Calculate diff, including "replace" operations.

If a sequence of remove operations is followed by the same number of add operations, these will be coalesced into replace operations.

  • param \T[] $old Original array
  • param \T[] $new New array
  • return \DiffElem[] Diff (edit script), including replace operations
private $isEqual = NULL
  • var callable
private calculateTrace(array $old, array $new) : array
  • param \T[] $old
  • param \T[] $new
  • return array{: array<int,array<int,int>>, : int, : int}
private coalesceReplacements(array $diff) : array

Coalesce equal-length sequences of remove+add into a replace operation.

  • param \DiffElem[] $diff
  • return \DiffElem[]
private extractDiff(array $trace, int $x, int $y, array $old, array $new) : array
  • param array<int,array<int,int>> $trace
  • param \T[] $old
  • param \T[] $new
  • return \DiffElem[]
© 2024 Bruce Wells
Search Namespaces \ Classes