module

Similar::Algorithms::Patience

Patience diff algorithm.

  • time: O(N log N + M log M + (N+M)D)
  • space: O(N+M)

Tends to give more human-readable outputs. See Bram Cohen's blog post describing it.

This is based on the patience implementation of pijul by Pierre-Étienne Meunier.

Class methods

diff(old, old_range : Range(Int32, Int32), new, new_range : Range(Int32, Int32), d : DiffHook) : Nil

Patience diff algorithm.

Diff old, between indices old_range and new between indices new_range.

Source
diff_deadline(old, old_range : Range(Int32, Int32), new, new_range : Range(Int32, Int32), d : DiffHook, deadline : Similar::DeadlineSupport::Instant | Nil = nil) : Nil

Patience diff algorithm with deadline.

Diff old, between indices old_range and new between indices new_range.

This diff is done with an optional deadline that defines the maximal execution time permitted before it bails and falls back to an approximation.

Source