12 # First we prune off any common elements at the beginning
13 while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
14 mvector[astart] = bstart
20 while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
21 mvector[afinish] = bfinish
26 bmatches = b.reverse_hash(bstart..bfinish)
30 (astart..afinish).each { |aindex|
32 next unless bmatches.has_key? aelem
34 bmatches[aelem].reverse.each { |bindex|
35 if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
38 k = thresh.replacenextlarger(bindex, k)
40 links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
45 link = links[thresh.length-1]
47 mvector[link[1]] = link[2]
56 mvector = Diff.lcs(a, b)
58 while ai < mvector.length
91 s = @isstring ? df[i][2].chr : [df[i][2]]
95 while df[i] && df[i][0] == whot && df[i][1] == last+1
100 curdiff.push [whot, p, s]
107 attr_reader :diffs, :difftype
109 def initialize(diffs_or_a, b = nil, isstring = nil)
116 makediff(diffs_or_a, b)
117 @difftype = diffs_or_a.class
122 @diffs.push @curdiffs unless @curdiffs.empty?
126 def discarda(i, elem)
127 @curdiffs.push ['-', i, elem]
130 def discardb(i, elem)
131 @curdiffs.push ['+', i, elem]
135 return Diff.new(compactdiffs)
139 @diffs = compactdiffs
153 # Create a hash that maps elements of the array to arrays of indices
154 # where the elements are found.
156 def reverse_hash(range = (0...self.length))
160 if revmap.has_key? elem
169 def replacenextlarger(value, high = nil)
171 if self.empty? || value > self[-1]
175 # binary search for replacement point
180 return nil if value == found
189 # $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
190 # $stderr.puts self.inspect
198 if diff.difftype == String
199 newary = diff.difftype.new('')
201 newary = diff.difftype.new
205 diff.diffs.each { |d|
224 raise "Unknown diff action"
228 while ai < self.length
247 (({diff.rb})) - computes the differences between two arrays or
248 strings. Copyright (C) 2001 Lars Christensen
252 diff = Diff.new(a, b)
259 Creates a Diff object which represent the differences between
260 ((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
261 of any objects, strings, or object of any class that include
262 module ((|Diffable|))
265 The module ((|Diffable|)) is intended to be included in any class for
266 which differences are to be computed. Diffable is included into String
267 and Array when (({diff.rb})) is (({require}))'d.
269 Classes including Diffable should implement (({[]})) to get element at
270 integer indices, (({<<})) to append elements to the object and
271 (({ClassName#new})) should accept 0 arguments to create a new empty
275 --- Diffable#patch(diff)
276 Applies the differences from ((|diff|)) to the object ((|obj|))
277 and return the result. ((|obj|)) is not changed. ((|obj|)) and
278 can be either an array or a string, but must match the object
279 from which the ((|diff|)) was created.