|
|
class Diff
|
|
|
|
|
|
VERSION = 0.3
|
|
|
|
|
|
def Diff.lcs(a, b)
|
|
|
astart = 0
|
|
|
bstart = 0
|
|
|
afinish = a.length-1
|
|
|
bfinish = b.length-1
|
|
|
mvector = []
|
|
|
|
|
|
# First we prune off any common elements at the beginning
|
|
|
while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
|
|
|
mvector[astart] = bstart
|
|
|
astart += 1
|
|
|
bstart += 1
|
|
|
end
|
|
|
|
|
|
# now the end
|
|
|
while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
|
|
|
mvector[afinish] = bfinish
|
|
|
afinish -= 1
|
|
|
bfinish -= 1
|
|
|
end
|
|
|
|
|
|
bmatches = b.reverse_hash(bstart..bfinish)
|
|
|
thresh = []
|
|
|
links = []
|
|
|
|
|
|
(astart..afinish).each { |aindex|
|
|
|
aelem = a[aindex]
|
|
|
next unless bmatches.has_key? aelem
|
|
|
k = nil
|
|
|
bmatches[aelem].reverse.each { |bindex|
|
|
|
if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
|
|
|
thresh[k] = bindex
|
|
|
else
|
|
|
k = thresh.replacenextlarger(bindex, k)
|
|
|
end
|
|
|
links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
|
|
|
}
|
|
|
}
|
|
|
|
|
|
if !thresh.empty?
|
|
|
link = links[thresh.length-1]
|
|
|
while link
|
|
|
mvector[link[1]] = link[2]
|
|
|
link = link[0]
|
|
|
end
|
|
|
end
|
|
|
|
|
|
return mvector
|
|
|
end
|
|
|
|
|
|
def makediff(a, b)
|
|
|
mvector = Diff.lcs(a, b)
|
|
|
ai = bi = 0
|
|
|
while ai < mvector.length
|
|
|
bline = mvector[ai]
|
|
|
if bline
|
|
|
while bi < bline
|
|
|
discardb(bi, b[bi])
|
|
|
bi += 1
|
|
|
end
|
|
|
match(ai, bi)
|
|
|
bi += 1
|
|
|
else
|
|
|
discarda(ai, a[ai])
|
|
|
end
|
|
|
ai += 1
|
|
|
end
|
|
|
while ai < a.length
|
|
|
discarda(ai, a[ai])
|
|
|
ai += 1
|
|
|
end
|
|
|
while bi < b.length
|
|
|
discardb(bi, b[bi])
|
|
|
bi += 1
|
|
|
end
|
|
|
match(ai, bi)
|
|
|
1
|
|
|
end
|
|
|
|
|
|
def compactdiffs
|
|
|
diffs = []
|
|
|
@diffs.each { |df|
|
|
|
i = 0
|
|
|
curdiff = []
|
|
|
while i < df.length
|
|
|
whot = df[i][0]
|
|
|
s = @isstring ? df[i][2].chr : [df[i][2]]
|
|
|
p = df[i][1]
|
|
|
last = df[i][1]
|
|
|
i += 1
|
|
|
while df[i] && df[i][0] == whot && df[i][1] == last+1
|
|
|
s << df[i][2]
|
|
|
last = df[i][1]
|
|
|
i += 1
|
|
|
end
|
|
|
curdiff.push [whot, p, s]
|
|
|
end
|
|
|
diffs.push curdiff
|
|
|
}
|
|
|
return diffs
|
|
|
end
|
|
|
|
|
|
attr_reader :diffs, :difftype
|
|
|
|
|
|
def initialize(diffs_or_a, b = nil, isstring = nil)
|
|
|
if b.nil?
|
|
|
@diffs = diffs_or_a
|
|
|
@isstring = isstring
|
|
|
else
|
|
|
@diffs = []
|
|
|
@curdiffs = []
|
|
|
makediff(diffs_or_a, b)
|
|
|
@difftype = diffs_or_a.class
|
|
|
end
|
|
|
end
|
|
|
|
|
|
def match(ai, bi)
|
|
|
@diffs.push @curdiffs unless @curdiffs.empty?
|
|
|
@curdiffs = []
|
|
|
end
|
|
|
|
|
|
def discarda(i, elem)
|
|
|
@curdiffs.push ['-', i, elem]
|
|
|
end
|
|
|
|
|
|
def discardb(i, elem)
|
|
|
@curdiffs.push ['+', i, elem]
|
|
|
end
|
|
|
|
|
|
def compact
|
|
|
return Diff.new(compactdiffs)
|
|
|
end
|
|
|
|
|
|
def compact!
|
|
|
@diffs = compactdiffs
|
|
|
end
|
|
|
|
|
|
def inspect
|
|
|
@diffs.inspect
|
|
|
end
|
|
|
|
|
|
end
|
|
|
|
|
|
module Diffable
|
|
|
def diff(b)
|
|
|
Diff.new(self, b)
|
|
|
end
|
|
|
|
|
|
# Create a hash that maps elements of the array to arrays of indices
|
|
|
# where the elements are found.
|
|
|
|
|
|
def reverse_hash(range = (0...self.length))
|
|
|
revmap = {}
|
|
|
range.each { |i|
|
|
|
elem = self[i]
|
|
|
if revmap.has_key? elem
|
|
|
revmap[elem].push i
|
|
|
else
|
|
|
revmap[elem] = [i]
|
|
|
end
|
|
|
}
|
|
|
return revmap
|
|
|
end
|
|
|
|
|
|
def replacenextlarger(value, high = nil)
|
|
|
high ||= self.length
|
|
|
if self.empty? || value > self[-1]
|
|
|
push value
|
|
|
return high
|
|
|
end
|
|
|
# binary search for replacement point
|
|
|
low = 0
|
|
|
while low < high
|
|
|
index = (high+low)/2
|
|
|
found = self[index]
|
|
|
return nil if value == found
|
|
|
if value > found
|
|
|
low = index + 1
|
|
|
else
|
|
|
high = index
|
|
|
end
|
|
|
end
|
|
|
|
|
|
self[low] = value
|
|
|
# $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
|
|
|
# $stderr.puts self.inspect
|
|
|
#gets
|
|
|
#p length - low
|
|
|
return low
|
|
|
end
|
|
|
|
|
|
def patch(diff)
|
|
|
newary = nil
|
|
|
if diff.difftype == String
|
|
|
newary = diff.difftype.new('')
|
|
|
else
|
|
|
newary = diff.difftype.new
|
|
|
end
|
|
|
ai = 0
|
|
|
bi = 0
|
|
|
diff.diffs.each { |d|
|
|
|
d.each { |mod|
|
|
|
case mod[0]
|
|
|
when '-'
|
|
|
while ai < mod[1]
|
|
|
newary << self[ai]
|
|
|
ai += 1
|
|
|
bi += 1
|
|
|
end
|
|
|
ai += 1
|
|
|
when '+'
|
|
|
while bi < mod[1]
|
|
|
newary << self[ai]
|
|
|
ai += 1
|
|
|
bi += 1
|
|
|
end
|
|
|
newary << mod[2]
|
|
|
bi += 1
|
|
|
else
|
|
|
raise "Unknown diff action"
|
|
|
end
|
|
|
}
|
|
|
}
|
|
|
while ai < self.length
|
|
|
newary << self[ai]
|
|
|
ai += 1
|
|
|
bi += 1
|
|
|
end
|
|
|
return newary
|
|
|
end
|
|
|
end
|
|
|
|
|
|
class Array
|
|
|
include Diffable
|
|
|
end
|
|
|
|
|
|
class String
|
|
|
include Diffable
|
|
|
end
|
|
|
|
|
|
=begin
|
|
|
= Diff
|
|
|
(({diff.rb})) - computes the differences between two arrays or
|
|
|
strings. Copyright (C) 2001 Lars Christensen
|
|
|
|
|
|
== Synopsis
|
|
|
|
|
|
diff = Diff.new(a, b)
|
|
|
b = a.patch(diff)
|
|
|
|
|
|
== Class Diff
|
|
|
=== Class Methods
|
|
|
--- Diff.new(a, b)
|
|
|
--- a.diff(b)
|
|
|
Creates a Diff object which represent the differences between
|
|
|
((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
|
|
|
of any objects, strings, or object of any class that include
|
|
|
module ((|Diffable|))
|
|
|
|
|
|
== Module Diffable
|
|
|
The module ((|Diffable|)) is intended to be included in any class for
|
|
|
which differences are to be computed. Diffable is included into String
|
|
|
and Array when (({diff.rb})) is (({require}))'d.
|
|
|
|
|
|
Classes including Diffable should implement (({[]})) to get element at
|
|
|
integer indices, (({<<})) to append elements to the object and
|
|
|
(({ClassName#new})) should accept 0 arguments to create a new empty
|
|
|
object.
|
|
|
|
|
|
=== Instance Methods
|
|
|
--- Diffable#patch(diff)
|
|
|
Applies the differences from ((|diff|)) to the object ((|obj|))
|
|
|
and return the result. ((|obj|)) is not changed. ((|obj|)) and
|
|
|
can be either an array or a string, but must match the object
|
|
|
from which the ((|diff|)) was created.
|
|
|
=end
|
|
|
|
