Skip to content

Instantly share code, notes, and snippets.

@yoshuawuyts
Last active March 9, 2018 15:03
Show Gist options
  • Save yoshuawuyts/86b30f07ad30104edf4671b332883908 to your computer and use it in GitHub Desktop.
Save yoshuawuyts/86b30f07ad30104edf4671b332883908 to your computer and use it in GitHub Desktop.
Slice = Struct.new(:a_low, :a_high, :b_low, :b_high) do
def a_range
a_low ... a_high
end
def b_range
b_low ... b_high
end
def not_empty?
a_low < a_high and b_low < b_high
end
end
Match = Struct.new(:a_line, :b_line) do
attr_accessor :prev, :next
end
class Patience
def self.diff(a, b, fallback: MyersLinear)
slice = Slice.new(0, a.size, 0, b.size)
new(fallback, a, b).diff(slice)
end
def initialize(fallback, a, b)
@fallback = fallback
@a, @b = a, b
end
def diff(slice)
match = patience_sort(unique_matching_lines(slice))
return fallback_diff(slice) unless match
lines = []
a_line, b_line = slice.a_low, slice.b_low
loop do
a_next, b_next = match ?
[match.a_line, match.b_line] :
[slice.a_high, slice.b_high]
subslice = Slice.new(a_line, a_next, b_line, b_next)
head, tail = [], []
match_head(subslice) { |edit| head = head + [edit] }
match_tail(subslice) { |edit| tail = [edit] + tail }
lines += head + diff(subslice) + tail
return lines unless match
end
end
end
def unique_matching_lines(slice)
counts = Hash.new { |h, text| h[text] = [0, 0, nil, nil] }
slice.a_range.each do |n|
text = @a[n].text
counts[text][0] += 1
counts[text][2] ||= n
end
slice.b_range.each do |n|
text = @b[n].text
counts[text][1] += 1
counts[text][3] ||= n
end
counts.select! { |text, count| count.take(2) == [1, 1] }
counts.map do |text, (_, _, a_line, b_line)|
Match.new(a_line, b_line)
end
end
def patience_sort(matches)
stacks = []
matches.each do |match|
i = binary_search(stacks, match)
match.prev = stacks[i] if i >= 0
stacks[i + 1] = match
end
match = stacks.last
return nil unless match
while match.prev
match.prev.next = match
match = match.prev
end
match
end
def binary_search(stacks, match)
low, high = -1, stacks.size
while low + 1 < high
mid = (low + high) / 2
if stacks[mid].b_line < match.b_line
low = mid
else
high = mid
end
end
low
end
def fallback_diff(slice)
@fallback.diff(@a[slice.a_range], @b[slice.b_range])
end
def match_head(slice)
while slice.not_empty? and @a[slice.a_low].text == @b[slice.b_low].text
yield Diff::Edit.new(:eql, @a[slice.a_low], @b[slice.b_low])
slice.a_low += 1
slice.b_low += 1
end
end
def match_tail(slice)
while slice.not_empty? and @a[slice.a_high - 1].text == @b[slice.b_high - 1].text
slice.a_high -= 1
slice.b_high -= 1
yield Diff::Edit.new(:eql, @a[slice.a_high], @b[slice.b_high])
end
end
module Diff
Edit = Struct.new(:type, :old_line, :new_line) do
def old_number
old_line ? old_line.number.to_s : ""
end
def new_number
new_line ? new_line.number.to_s : ""
end
def text
(old_line || new_line).text
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment