- Timestamp:
- 2016-05-17T18:07:55+02:00 (9 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/tools/Diff.java
r10223 r10246 103 103 sibling file. */ 104 104 private int equivMax = 1; 105 106 /** When set to true, the comparison uses a heuristic to speed it up.107 With this heuristic, for files with a constant small density108 of changes, the algorithm is linear in the file size. */109 public boolean heuristic;110 111 /** When set to true, the algorithm returns a guarranteed minimal112 set of changes. This makes things slower, sometimes much slower. */113 public boolean noDiscards;114 105 115 106 private int[] xvec, yvec; /* Vectors being compared. */ … … 246 237 } 247 238 } 248 249 /* Heuristic: check occasionally for a diagonal that has made250 lots of progress compared with the edit distance.251 If we have any such, find the one that has made the most252 progress and return it as if it had succeeded.253 254 With this heuristic, for files with a constant small density255 of changes, the algorithm is linear in the file size. */256 257 if (c > 200 && bigSnake && heuristic) {258 int best = 0;259 int bestpos = -1;260 261 for (d = fmax; d >= fmin; d -= 2) {262 int dd = d - fmid;263 int x = fd[fdiagoff + d];264 int y = x - d;265 int v = (x - xoff) * 2 - dd;266 if (v > 12 * (c + (dd < 0 ? -dd : dd))) {267 if (v > best268 && xoff + SNAKE_LIMIT <= x && x < xlim269 && yoff + SNAKE_LIMIT <= y && y < ylim) {270 /* We have a good enough best diagonal.271 now insist that it end with a significant snake. */272 int k;273 274 for (k = 1; xvec[x - k] == yvec[y - k]; k++) {275 if (k == SNAKE_LIMIT) {276 best = v;277 bestpos = d;278 break;279 }280 }281 }282 }283 }284 if (best > 0) {285 cost = 2 * c - 1;286 return bestpos;287 }288 289 best = 0;290 for (d = bmax; d >= bmin; d -= 2) {291 int dd = d - bmid;292 int x = bd[bdiagoff + d];293 int y = x - d;294 int v = (xlim - x) * 2 + dd;295 if (v > 12 * (c + (dd < 0 ? -dd : dd))) {296 if (v > best297 && xoff < x && x <= xlim - SNAKE_LIMIT298 && yoff < y && y <= ylim - SNAKE_LIMIT) {299 /* We have a good enough best diagonal.300 now insist that it end with a significant snake. */301 int k;302 303 for (k = 0; xvec[x + k] == yvec[y + k]; k++) {304 if (k == SNAKE_LIMIT) {305 best = v;306 bestpos = d;307 break;308 }309 }310 }311 }312 }313 if (best > 0) {314 cost = 2 * c - 1;315 return bestpos;316 }317 }318 239 } 319 240 } … … 805 726 int j = 0; 806 727 for (int i = 0; i < end; ++i) { 807 if ( noDiscards ||discards[i] == 0) {728 if (discards[i] == 0) { 808 729 undiscarded[j] = equivs[i]; 809 730 realindexes[j++] = i;
Note:
See TracChangeset
for help on using the changeset viewer.