1 module RedmineDiff
2 class Diff
3
4 VERSION = 0.3
5
6 def Diff.lcs(a, b)
7 astart = 0
8 bstart = 0
9 afinish = a.length-1
10 bfinish = b.length-1
11 mvector = []
12
13 # First we prune off any common elements at the beginning
14 while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
15 mvector[astart] = bstart
16 astart += 1
17 bstart += 1
18 end
19
20 # now the end
21 while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
22 mvector[afinish] = bfinish
23 afinish -= 1
24 bfinish -= 1
25 end
26
27 bmatches = b.reverse_hash(bstart..bfinish)
28 thresh = []
29 links = []
30
31 (astart..afinish).each { |aindex|
32 aelem = a[aindex]
33 next unless bmatches.has_key? aelem
34 k = nil
35 bmatches[aelem].reverse.each { |bindex|
36 if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
37 thresh[k] = bindex
38 else
39 k = thresh.replacenextlarger(bindex, k)
40 end
41 links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
42 }
43 }
44
45 if !thresh.empty?
46 link = links[thresh.length-1]
47 while link
48 mvector[link[1]] = link[2]
49 link = link[0]
50 end
51 end
52
53 return mvector
54 end
55
56 def makediff(a, b)
57 mvector = Diff.lcs(a, b)
58 ai = bi = 0
59 while ai < mvector.length
60 bline = mvector[ai]
61 if bline
62 while bi < bline
63 discardb(bi, b[bi])
64 bi += 1
65 end
66 match(ai, bi)
67 bi += 1
68 else
69 discarda(ai, a[ai])
70 end
71 ai += 1
72 end
73 while ai < a.length
74 discarda(ai, a[ai])
75 ai += 1
76 end
77 while bi < b.length
78 discardb(bi, b[bi])
79 bi += 1
80 end
81 match(ai, bi)
82 1
83 end
84
85 def compactdiffs
86 diffs = []
87 @diffs.each { |df|
88 i = 0
89 curdiff = []
90 while i < df.length
91 whot = df[i][0]
92 s = @isstring ? df[i][2].chr : [df[i][2]]
93 p = df[i][1]
94 last = df[i][1]
95 i += 1
96 while df[i] && df[i][0] == whot && df[i][1] == last+1
97 s << df[i][2]
98 last = df[i][1]
99 i += 1
100 end
101 curdiff.push [whot, p, s]
102 end
103 diffs.push curdiff
104 }
105 return diffs
106 end
107
108 attr_reader :diffs, :difftype
109
110 def initialize(diffs_or_a, b = nil, isstring = nil)
111 if b.nil?
112 @diffs = diffs_or_a
113 @isstring = isstring
114 else
115 @diffs = []
116 @curdiffs = []
117 makediff(diffs_or_a, b)
118 @difftype = diffs_or_a.class
119 end
120 end
121
122 def match(ai, bi)
123 @diffs.push @curdiffs unless @curdiffs.empty?
124 @curdiffs = []
125 end
126
127 def discarda(i, elem)
128 @curdiffs.push ['-', i, elem]
129 end
130
131 def discardb(i, elem)
132 @curdiffs.push ['+', i, elem]
133 end
134
135 def compact
136 return Diff.new(compactdiffs)
137 end
138
139 def compact!
140 @diffs = compactdiffs
141 end
142
143 def inspect
144 @diffs.inspect
145 end
146
147 end
148 end
149
150 module Diffable
151 def diff(b)
152 RedmineDiff::Diff.new(self, b)
153 end
154
155 # Create a hash that maps elements of the array to arrays of indices
156 # where the elements are found.
157
158 def reverse_hash(range = (0...self.length))
159 revmap = {}
160 range.each { |i|
161 elem = self[i]
162 if revmap.has_key? elem
163 revmap[elem].push i
164 else
165 revmap[elem] = [i]
166 end
167 }
168 return revmap
169 end
170
171 def replacenextlarger(value, high = nil)
172 high ||= self.length
173 if self.empty? || value > self[-1]
174 push value
175 return high
176 end
177 # binary search for replacement point
178 low = 0
179 while low < high
180 index = (high+low)/2
181 found = self[index]
182 return nil if value == found
183 if value > found
184 low = index + 1
185 else
186 high = index
187 end
188 end
189
190 self[low] = value
191 # $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
192 # $stderr.puts self.inspect
193 #gets
194 #p length - low
195 return low
196 end
197
198 def patch(diff)
199 newary = nil
200 if diff.difftype == String
201 newary = diff.difftype.new('')
202 else
203 newary = diff.difftype.new
204 end
205 ai = 0
206 bi = 0
207 diff.diffs.each { |d|
208 d.each { |mod|
209 case mod[0]
210 when '-'
211 while ai < mod[1]
212 newary << self[ai]
213 ai += 1
214 bi += 1
215 end
216 ai += 1
217 when '+'
218 while bi < mod[1]
219 newary << self[ai]
220 ai += 1
221 bi += 1
222 end
223 newary << mod[2]
224 bi += 1
225 else
226 raise "Unknown diff action"
227 end
228 }
229 }
230 while ai < self.length
231 newary << self[ai]
232 ai += 1
233 bi += 1
234 end
235 return newary
236 end
237 end
238
239 class Array
240 include Diffable
241 end
242
243 class String
244 include Diffable
245 end
246
247 =begin
248 = Diff
249 (({diff.rb})) - computes the differences between two arrays or
250 strings. Copyright (C) 2001 Lars Christensen
251
252 == Synopsis
253
254 diff = Diff.new(a, b)
255 b = a.patch(diff)
256
257 == Class Diff
258 === Class Methods
259 --- Diff.new(a, b)
260 --- a.diff(b)
261 Creates a Diff object which represent the differences between
262 ((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
263 of any objects, strings, or object of any class that include
264 module ((|Diffable|))
265
266 == Module Diffable
267 The module ((|Diffable|)) is intended to be included in any class for
268 which differences are to be computed. Diffable is included into String
269 and Array when (({diff.rb})) is (({require}))'d.
270
271 Classes including Diffable should implement (({[]})) to get element at
272 integer indices, (({<<})) to append elements to the object and
273 (({ClassName#new})) should accept 0 arguments to create a new empty
274 object.
275
276 === Instance Methods
277 --- Diffable#patch(diff)
278 Applies the differences from ((|diff|)) to the object ((|obj|))
279 and return the result. ((|obj|)) is not changed. ((|obj|)) and
280 can be either an array or a string, but must match the object
281 from which the ((|diff|)) was created.
282 =end