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