diff options
author | Austin Ziegler <austin@zieglers.ca> | 2021-12-20 11:20:25 -0500 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-12-20 11:20:25 -0500 |
commit | 01fce789b26d9adc65d29af9b8a194e1b3ef7a60 (patch) | |
tree | 7d3848c2ad1cb118e7741e97e905393eb17a3345 /lib/diff/lcs/internals.rb | |
parent | 0c1529965772baf94aee9c94109df9ffecbc9407 (diff) | |
parent | 7b9fa86d33b1aa42e629f152c5acb43176a420d3 (diff) | |
download | diff-lcs-01fce789b26d9adc65d29af9b8a194e1b3ef7a60.tar.gz |
Merge pull request #72 from tiendo1011/ax-unecessary-call
Ax unecessary call
Diffstat (limited to 'lib/diff/lcs/internals.rb')
-rw-r--r-- | lib/diff/lcs/internals.rb | 13 |
1 files changed, 6 insertions, 7 deletions
diff --git a/lib/diff/lcs/internals.rb b/lib/diff/lcs/internals.rb index 4977288..74f8909 100644 --- a/lib/diff/lcs/internals.rb +++ b/lib/diff/lcs/internals.rb @@ -44,13 +44,12 @@ class << Diff::LCS::Internals b_finish = b.size - 1 vector = [] - # Prune off any common elements at the beginning... + # Collect any common elements at the beginning... while (a_start <= a_finish) and (b_start <= b_finish) and (a[a_start] == b[b_start]) vector[a_start] = b_start a_start += 1 b_start += 1 end - b_start = a_start # Now the end... while (a_start <= a_finish) and (b_start <= b_finish) and (a[a_finish] == b[b_finish]) @@ -60,6 +59,7 @@ class << Diff::LCS::Internals end # Now, compute the equivalence classes of positions of elements. + # An explanation for how this works: https://codeforces.com/topic/92191 b_matches = position_hash(b, b_start..b_finish) thresh = [] @@ -71,11 +71,10 @@ class << Diff::LCS::Internals bm = b_matches[ai] k = nil bm.reverse_each do |j| - if k and (thresh[k] > j) and (thresh[k - 1] < j) - thresh[k] = j - else - k = replace_next_larger(thresh, j, k) - end + # Previously, we would update `thresh[k] = j` if `k and (thresh[k] > j) and (thresh[k - 1] < j)` + # Otherwise, we would do this. The update appears not to be necessary, so we are trying to + # simplify to: + k = replace_next_larger(thresh, j) links[k] = [k.positive? ? links[k - 1] : nil, i, j] unless k.nil? end end |