|
1
19
20 package org.netbeans.modules.diff.builtin.provider;
21
22 import java.util.ArrayList  ;
23 import java.util.Arrays ;
24 import java.util.Comparator ;
25 import java.util.List ;
26 import org.netbeans.api.diff.Difference;
27
28
29 public class HuntDiff {
30
31 private HuntDiff() {
32 }
33
34
40 public static Difference[] diff(String [] lines1, String [] lines2, boolean ignoreWhitespace) {
41 int m = lines1.length;
42 int n = lines2.length;
43 String [] lines1_original = lines1;
44 String [] lines2_original = lines2;
45 if (ignoreWhitespace) {
46 lines1 = new String [lines1_original.length];
47 lines2 = new String [lines2_original.length];
48 for (int i = 0 ; i < lines1_original.length; i++) {
49 lines1[i] = lines1_original[i].trim();
50 }
51 for (int i = 0 ; i < lines2_original.length; i++) {
52 lines2[i] = lines2_original[i].trim();
53 }
54 }
55 Line[] l2s = new Line[n + 1];
56 for (int i = 1; i <= n; i++) {
58 l2s[i] = new Line(i, lines2[i - 1]);
59 }
60 Arrays.sort(l2s, 1, n+1, new Comparator <Line>() {
61
62 public int compare(Line l1, Line l2) {
63 return l1.line.compareTo(l2.line);
64 }
65
66 public boolean equals(Object obj) {
67 return obj == this;
68 }
69
70 });
71
72 int[] equvalenceLines = new int[n+1];
73 boolean[] equivalence = new boolean[n+1];
74 for (int i = 1; i <= n; i++) {
75 Line l = l2s[i];
76 equvalenceLines[i] = l.lineNo;
77 equivalence[i] = (i == n) || !l.line.equals(l2s[i+1].line); }
79 equvalenceLines[0] = 0;
80 equivalence[0] = true;
81 int[] equivalenceAssoc = new int[m + 1];
82 for (int i = 1; i <= m; i++) {
83 equivalenceAssoc[i] = findAssoc(lines1[i - 1], l2s, equivalence);
84 }
85
86 l2s = null;
87 Candidate[] K = new Candidate[Math.min(m, n) + 2];
88 K[0] = new Candidate(0, 0, null);
89 K[1] = new Candidate(m + 1, n + 1, null);
90 int k = 0;
91 for (int i = 1; i <= m; i++) {
92 if (equivalenceAssoc[i] != 0) {
93 k = merge(K, k, i, equvalenceLines, equivalence, equivalenceAssoc[i]);
94 }
95 }
96 int[] J = new int[m+2];
98 Candidate c = K[k];
99 while (c != null) {
100 J[c.a] = c.b;
101 c = c.c;
102 }
103
104 List <Difference> differences = getDifferences(J, lines1_original, lines2_original);
105 cleanup(differences);
106 return differences.toArray(new Difference[0]);
107 }
108
109 private static int findAssoc(String line1, Line[] l2s, boolean[] equivalence) {
110 int idx = binarySearch(l2s, line1, 1, l2s.length - 1);
111 if (idx < 1) {
112 return 0;
113 } else {
114 int lastGoodIdx = 0;
115 for (; idx >= 1 && l2s[idx].line.equals(line1); idx--) {
116 if (equivalence[idx - 1]) {
117 lastGoodIdx = idx;
118 }
119 }
120 return lastGoodIdx;
121 }
122 }
123
124 private static int binarySearch(Line[] L, String key, int low, int high) {
125 while (low <= high) {
126 int mid = (low + high) >> 1;
127 String midVal = L[mid].line;
128 int comparison = midVal.compareTo(key);
129 if (comparison < 0) {
130 low = mid + 1;
131 } else if (comparison > 0) {
132 high = mid - 1;
133 } else {
134 return mid;
135 }
136 }
137 return -(low + 1);
138 }
139
140 private static int binarySearch(Candidate[] K, int key, int low, int high) {
141 while (low <= high) {
142 int mid = (low + high) >> 1;
143 int midVal = K[mid].b;
144 if (midVal < key) {
145 low = mid + 1;
146 } else if (midVal > key) {
147 high = mid - 1;
148 } else {
149 return mid;
150 }
151 }
152 return -(low + 1);
153 }
154
155 private static int merge(Candidate[] K, int k, int i, int[] equvalenceLines,
156 boolean[] equivalence, int p) {
157 int r = 0;
158 Candidate c = K[0];
159 do {
160 int j = equvalenceLines[p];
161 int s = binarySearch(K, j, r, k);
162 if (s >= 0) {
163 s = k + 1;
165 } else {
166 s = -s - 2;
167 if (s < r || s > k) s = k + 1;
168 }
169 if (s <= k) {
170 if (K[s+1].b > j) {
171 Candidate newc = new Candidate(i, j, K[s]);
172 K[r] = c;
173 r = s+1;
174 c = newc;
175 }
176 if (s == k) {
177 K[k+2] = K[k+1];
178 k++;
179 break;
180 }
181 }
182 if (equivalence[p] == true) {
183 break;
184 } else {
185 p++;
186 }
187 } while (true);
188 K[r] = c;
189 return k;
190 }
191
192 private static List <Difference> getDifferences(int[] J, String [] lines1, String [] lines2) {
193 List <Difference> differences = new ArrayList <Difference>();
194 int n = lines1.length;
195 int m = lines2.length;
196 int start1 = 1;
197 int start2 = 1;
198 do {
199 while (start1 <= n && J[start1] == start2) {
200 start1++;
201 start2++;
202 }
203 if (start1 > n) break;
204 if (J[start1] < start2) { int end1 = start1 + 1;
206 StringBuffer deletedText = new StringBuffer ();
207 deletedText.append(lines1[start1-1]).append('\n');
208 while (end1 <= n && J[end1] < start2) {
209 String line = lines1[end1-1];
210 deletedText.append(line).append('\n');
211 end1++;
212 }
213 differences.add(new Difference(Difference.DELETE, start1, end1 - 1, start2 - 1, 0, deletedText.toString(), null));
214 start1 = end1;
215 } else { int end2 = J[start1];
217 StringBuffer addedText = new StringBuffer ();
218 for (int i = start2; i < end2; i++) {
219 String line = lines2[i-1];
220 addedText.append(line).append('\n');
221 }
222 differences.add(new Difference(Difference.ADD, (start1 - 1), 0, start2, (end2 - 1), null, addedText.toString()));
223 start2 = end2;
224 }
225 } while (start1 <= n);
226 if (start2 <= m) { int end2 = start2 + 1;
228 StringBuilder addedText = new StringBuilder ();
229 addedText.append(lines2[start2-1]).append('\n');
230 while (end2 <= m) {
231 String line = lines2[end2-1];
232 addedText.append(line).append('\n');
233 end2++;
234 }
235 differences.add(new Difference(Difference.ADD, n, 0, start2, m, null, addedText.toString()));
236 }
237 return differences;
238 }
239
240 private static void cleanup(List <Difference> diffs) {
241 Difference last = null;
242 for (int i = 0; i < diffs.size(); i++) {
243 Difference diff = diffs.get(i);
244 if (last != null) {
245 if (diff.getType() == Difference.ADD && last.getType() == Difference.DELETE ||
246 diff.getType() == Difference.DELETE && last.getType() == Difference.ADD) {
247
248 Difference add;
249 Difference del;
250 if (Difference.ADD == diff.getType()) {
251 add = diff;
252 del = last;
253 } else {
254 add = last;
255 del = diff;
256 }
257 int d1f1l1 = add.getFirstStart() - (del.getFirstEnd() - del.getFirstStart());
258 int d2f1l1 = del.getFirstStart();
259 if (d1f1l1 == d2f1l1) {
260 Difference newDiff = new Difference(Difference.CHANGE,
261 d1f1l1, del.getFirstEnd(), add.getSecondStart(), add.getSecondEnd(),
262 del.getFirstText(), add.getSecondText());
263 diffs.set(i - 1, newDiff);
264 diffs.remove(i);
265 i--;
266 diff = newDiff;
267 }
268 }
269 }
270 last = diff;
271 }
272 }
273
274 private static class Line {
275
276 public int lineNo;
277 public String line;
278 public int hash;
279
280
281 public Line(int lineNo, String line) {
282 this.lineNo = lineNo;
283 this.line = line;
284 this.hash = line.hashCode();
285 }
286
287 }
288
289 private static class Candidate {
290
291 private int a;
292 private int b;
293 private Candidate c;
294
295 public Candidate(int a, int b, Candidate c) {
296 this.a = a;
297 this.b = b;
298 this.c = c;
299 }
300 }
301
302 }
303 |
Popular Tags |
Java API By Example, From Geeks To Geeks.