1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
# frozen_string_literal: true
=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
module Redmine
module StringArrayDiff
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
end
end
class Array
include Redmine::StringArrayDiff::Diffable
end
class String
include Redmine::StringArrayDiff::Diffable
end
|
