196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Projectpackage jdiff; 296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Projectimport java.io.*; 496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Projectimport java.util.*; 596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project/** A class to compare vectors of objects. The result of comparison 796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project is a list of <code>change</code> objects which form an 896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project edit script. The objects compared are traditionally lines 996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of text from two files. Comparison options such as "ignore 1096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project whitespace" are implemented by modifying the <code>equals</code> 1196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and <code>hashcode</code> methods for the objects compared. 1296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 1396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The basic algorithm is described in: </br> 1496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project "An O(ND) Difference Algorithm and its Variations", Eugene Myers, 1596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Algorithmica Vol. 1 No. 2, 1986, p 251. 1696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 1796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project This class outputs different results from GNU diff 1.15 on some 1896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project inputs. Our results are actually better (smaller change list, smaller 1996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project total size of changes), but it would be nice to know why. Perhaps 2096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project there is a memory overwrite bug in GNU diff 1.15. 2196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 2296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @author Stuart D. Gathman, translated from GNU diff 1.15 2396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Copyright (C) 2000 Business Management Systems, Inc. 2496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 2596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project This program is free software; you can redistribute it and/or modify 2696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project it under the terms of the GNU General Public License as published by 2796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the Free Software Foundation; either version 1, or (at your option) 2896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project any later version. 2996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 3096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project This program is distributed in the hope that it will be useful, 3196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 3296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 3396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project GNU General Public License for more details. 3496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 3596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project You should have received a copy of the <a href=COPYING.txt> 3696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project GNU General Public License</a> 3796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project along with this program; if not, write to the Free Software 3896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 3996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 4096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 4196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 4296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Projectpublic class DiffMyers 4396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project{ 4496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 4596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Prepare to find differences between two arrays. Each element of 4696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the arrays is translated to an "equivalence number" based on 4796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the result of <code>equals</code>. The original Object arrays 4896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project are no longer needed for computing the differences. They will 4996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project be needed again later to print the results of the comparison as 5096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project an edit script, if desired. 5196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 5296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public DiffMyers(Object[] a,Object[] b) 5396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 5496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Hashtable h = new Hashtable(a.length + b.length); 5596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[0] = new file_data(a,h); 5696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[1] = new file_data(b,h); 5796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 5896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 5996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** 1 more than the maximum equivalence value used for this or its 6096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project sibling file. */ 6196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int equiv_max = 1; 6296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 6396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** When set to true, the comparison uses a heuristic to speed it up. 6496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project With this heuristic, for files with a constant small density 6596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of changes, the algorithm is linear in the file size. */ 6696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public boolean heuristic = false; 6796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 6896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** When set to true, the algorithm returns a guarranteed minimal 6996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project set of changes. This makes things slower, sometimes much slower. */ 7096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public boolean no_discards = false; 7196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 7296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int[] xvec, yvec; /* Vectors being compared. */ 7396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int[] fdiag; /* Vector, indexed by diagonal, containing 7496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the X coordinate of the point furthest 7596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project along the given diagonal in the forward 7696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project search of the edit matrix. */ 7796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int[] bdiag; /* Vector, indexed by diagonal, containing 7896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the X coordinate of the point furthest 7996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project along the given diagonal in the backward 8096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project search of the edit matrix. */ 8196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int fdiagoff, bdiagoff; 8296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private final file_data[] filevec = new file_data[2]; 8396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int cost; 8496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 8596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Find the midpoint of the shortest edit script for a specified 8696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project portion of the two files. 8796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 8896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project We scan from the beginnings of the files, and simultaneously from the ends, 8996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project doing a breadth-first search through the space of edit-sequence. 9096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project When the two searches meet, we have found the midpoint of the shortest 9196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project edit sequence. 9296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 9396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The value returned is the number of the diagonal on which the midpoint lies. 9496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The diagonal number equals the number of inserted lines minus the number 9596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of deleted lines (counting only lines before the midpoint). 9696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The edit cost is stored into COST; this is the total number of 9796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project lines inserted or deleted (counting only lines before the midpoint). 9896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 9996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project This function assumes that the first lines of the specified portions 10096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of the two files do not match, and likewise that the last lines do not 10196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project match. The caller must trim matching lines from the beginning and end 10296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of the portions it is going to specify. 10396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 10496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Note that if we return the "wrong" diagonal value, or if 10596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the value of bdiag at that diagonal is "wrong", 10696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the worst this can do is cause suboptimal diff output. 10796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project It cannot cause incorrect diff output. */ 10896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 10996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private int diag (int xoff, int xlim, int yoff, int ylim) 11096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 11196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] fd = fdiag; // Give the compiler a chance. 11296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] bd = bdiag; // Additional help for the compiler. 11396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] xv = xvec; // Still more help for the compiler. 11496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] yv = yvec; // And more and more . . . 11596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int dmin = xoff - ylim; // Minimum valid diagonal. 11696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int dmax = xlim - yoff; // Maximum valid diagonal. 11796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int fmid = xoff - yoff; // Center diagonal of top-down search. 11896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int bmid = xlim - ylim; // Center diagonal of bottom-up search. 11996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int fmin = fmid, fmax = fmid; // Limits of top-down search. 12096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int bmin = bmid, bmax = bmid; // Limits of bottom-up search. 12196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* True if southeast corner is on an odd 12296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project diagonal with respect to the northwest. */ 12396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean odd = (fmid - bmid & 1) != 0; 12496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 12596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fd[fdiagoff + fmid] = xoff; 12696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bd[bdiagoff + bmid] = xlim; 12796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 12896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int c = 1;; ++c) 12996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 13096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int d; /* Active diagonal. */ 13196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project boolean big_snake = false; 13296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 13396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Extend the top-down search by an edit step in each diagonal. */ 13496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (fmin > dmin) 13596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fd[fdiagoff + --fmin - 1] = -1; 13696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 13796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++fmin; 13896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (fmax < dmax) 13996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fd[fdiagoff + ++fmax + 1] = -1; 14096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 14196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project --fmax; 14296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (d = fmax; d >= fmin; d -= 2) 14396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 14496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int x, y, oldx, tlo = fd[fdiagoff + d - 1], thi = fd[fdiagoff + d + 1]; 14596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 14696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (tlo >= thi) 14796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project x = tlo + 1; 14896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 14996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project x = thi; 15096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project oldx = x; 15196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project y = x - d; 15296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (x < xlim && y < ylim && xv[x] == yv[y]) { 15396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++x; ++y; 15496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 15596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (x - oldx > 20) 15696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project big_snake = true; 15796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fd[fdiagoff + d] = x; 15896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (odd && bmin <= d && d <= bmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) 15996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 16096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project cost = 2 * c - 1; 16196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return d; 16296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 16396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 16496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 16596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Similar extend the bottom-up search. */ 16696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (bmin > dmin) 16796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bd[bdiagoff + --bmin - 1] = Integer.MAX_VALUE; 16896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 16996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++bmin; 17096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (bmax < dmax) 17196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bd[bdiagoff + ++bmax + 1] = Integer.MAX_VALUE; 17296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 17396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project --bmax; 17496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (d = bmax; d >= bmin; d -= 2) 17596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 17696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int x, y, oldx, tlo = bd[bdiagoff + d - 1], thi = bd[bdiagoff + d + 1]; 17796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 17896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (tlo < thi) 17996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project x = tlo; 18096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 18196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project x = thi - 1; 18296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project oldx = x; 18396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project y = x - d; 18496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) { 18596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project --x; --y; 18696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 18796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (oldx - x > 20) 18896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project big_snake = true; 18996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bd[bdiagoff + d] = x; 19096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (!odd && fmin <= d && d <= fmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) 19196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 19296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project cost = 2 * c; 19396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return d; 19496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 19596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 19696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 19796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Heuristic: check occasionally for a diagonal that has made 19896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project lots of progress compared with the edit distance. 19996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project If we have any such, find the one that has made the most 20096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project progress and return it as if it had succeeded. 20196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 20296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project With this heuristic, for files with a constant small density 20396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of changes, the algorithm is linear in the file size. */ 20496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 20596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (c > 200 && big_snake && heuristic) 20696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 20796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int best = 0; 20896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int bestpos = -1; 20996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 21096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (d = fmax; d >= fmin; d -= 2) 21196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 21296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int dd = d - fmid; 21396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if ((fd[fdiagoff + d] - xoff)*2 - dd > 12 * (c + (dd > 0 ? dd : -dd))) 21496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 21596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (fd[fdiagoff + d] * 2 - dd > best 21696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && fd[fdiagoff + d] - xoff > 20 21796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && fd[fdiagoff + d] - d - yoff > 20) 21896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 21996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int k; 22096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int x = fd[fdiagoff + d]; 22196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 22296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* We have a good enough best diagonal; 22396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project now insist that it end with a significant snake. */ 22496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (k = 1; k <= 20; k++) 22596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (xvec[x - k] != yvec[x - d - k]) 22696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 22796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 22896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (k == 21) 22996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 23096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project best = fd[fdiagoff + d] * 2 - dd; 23196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bestpos = d; 23296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 23396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 23496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 23596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 23696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (best > 0) 23796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 23896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project cost = 2 * c - 1; 23996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return bestpos; 24096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 24196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 24296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project best = 0; 24396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (d = bmax; d >= bmin; d -= 2) 24496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 24596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int dd = d - bmid; 24696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if ((xlim - bd[bdiagoff + d])*2 + dd > 12 * (c + (dd > 0 ? dd : -dd))) 24796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 24896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if ((xlim - bd[bdiagoff + d]) * 2 + dd > best 24996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && xlim - bd[bdiagoff + d] > 20 25096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && ylim - (bd[bdiagoff + d] - d) > 20) 25196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 25296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* We have a good enough best diagonal; 25396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project now insist that it end with a significant snake. */ 25496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int k; 25596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int x = bd[bdiagoff + d]; 25696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 25796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (k = 0; k < 20; k++) 25896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (xvec[x + k] != yvec[x - d + k]) 25996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 26096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (k == 20) 26196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 26296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project best = (xlim - bd[bdiagoff + d]) * 2 + dd; 26396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bestpos = d; 26496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 26596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 26696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 26796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 26896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (best > 0) 26996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 27096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project cost = 2 * c - 1; 27196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return bestpos; 27296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 27396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 27496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 27596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 27696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 27796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Compare in detail contiguous subsequences of the two files 27896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project which are known, as a whole, to match each other. 27996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 28096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The results are recorded in the vectors filevec[N].changed_flag, by 28196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project storing a 1 in the element for each line that is an insertion or deletion. 28296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 28396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. 28496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 28596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Note that XLIM, YLIM are exclusive bounds. 28696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project All line numbers are origin-0 and discarded lines are not counted. */ 28796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 28896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private void compareseq (int xoff, int xlim, int yoff, int ylim) { 28996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Slide down the bottom initial diagonal. */ 29096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff]) { 29196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++xoff; ++yoff; 29296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 29396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Slide up the top initial diagonal. */ 29496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1]) { 29596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project --xlim; --ylim; 29696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 29796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 29896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Handle simple cases. */ 29996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (xoff == xlim) 30096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (yoff < ylim) 30196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[1].changed_flag[1+filevec[1].realindexes[yoff++]] = true; 30296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (yoff == ylim) 30396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (xoff < xlim) 30496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[0].changed_flag[1+filevec[0].realindexes[xoff++]] = true; 30596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 30696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 30796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Find a point of correspondence in the middle of the files. */ 30896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 30996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int d = diag (xoff, xlim, yoff, ylim); 31096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int c = cost; 31196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int f = fdiag[fdiagoff + d]; 31296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int b = bdiag[bdiagoff + d]; 31396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 31496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (c == 1) 31596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 31696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* This should be impossible, because it implies that 31796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project one of the two subsequences is empty, 31896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and that case was handled above without calling `diag'. 31996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Let's verify that this is true. */ 32096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project throw new IllegalArgumentException("Empty subsequence"); 32196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 32296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 32396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 32496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Use that point to split this problem into two subproblems. */ 32596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project compareseq (xoff, b, yoff, b - d); 32696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* This used to use f instead of b, 32796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project but that is incorrect! 32896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project It is not necessarily the case that diagonal d 32996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project has a snake from b to f. */ 33096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project compareseq (b, xlim, b - d, ylim); 33196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 33296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 33396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 33496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 33596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Discard lines from one file that have no matches in the other file. 33696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 33796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 33896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private void discard_confusing_lines() { 33996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[0].discard_confusing_lines(filevec[1]); 34096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[1].discard_confusing_lines(filevec[0]); 34196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 34296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 34396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private boolean inhibit = false; 34496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 34596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Adjust inserts/deletes of blank lines to join changes 34696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project as much as possible. 34796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 34896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 34996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private void shift_boundaries() { 35096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (inhibit) 35196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return; 35296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[0].shift_boundaries(filevec[1]); 35396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[1].shift_boundaries(filevec[0]); 35496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 35596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 35696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Scan the tables of which lines are inserted and deleted, 35796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project producing an edit script in reverse order. */ 35896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 35996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private change build_reverse_script() { 36096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project change script = null; 36196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] changed0 = filevec[0].changed_flag; 36296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] changed1 = filevec[1].changed_flag; 36396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int len0 = filevec[0].buffered_lines; 36496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int len1 = filevec[1].buffered_lines; 36596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 36696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Note that changedN[len0] does exist, and contains 0. */ 36796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 36896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int i0 = 0, i1 = 0; 36996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 37096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (i0 < len0 || i1 < len1) 37196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 37296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (changed0[1+i0] || changed1[1+i1]) 37396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 37496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int line0 = i0, line1 = i1; 37596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 37696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Find # lines changed here in each file. */ 37796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (changed0[1+i0]) ++i0; 37896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (changed1[1+i1]) ++i1; 37996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 38096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Record this change. */ 38196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project script = new change(line0, line1, i0 - line0, i1 - line1, script); 38296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 38396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 38496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* We have reached lines in the two files that match each other. */ 38596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project i0++; i1++; 38696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 38796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 38896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return script; 38996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 39096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 39196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Scan the tables of which lines are inserted and deleted, 39296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project producing an edit script in forward order. */ 39396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 39496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private change build_script() { 39596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project change script = null; 39696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] changed0 = filevec[0].changed_flag; 39796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] changed1 = filevec[1].changed_flag; 39896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int len0 = filevec[0].buffered_lines; 39996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int len1 = filevec[1].buffered_lines; 40096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int i0 = len0, i1 = len1; 40196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 40296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Note that changedN[-1] does exist, and contains 0. */ 40396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 40496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (i0 >= 0 || i1 >= 0) 40596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 40696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (changed0[i0] || changed1[i1]) 40796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 40896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int line0 = i0, line1 = i1; 40996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 41096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Find # lines changed here in each file. */ 41196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (changed0[i0]) --i0; 41296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (changed1[i1]) --i1; 41396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 41496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Record this change. */ 41596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project script = new change(i0, i1, line0 - i0, line1 - i1, script); 41696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 41796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 41896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* We have reached lines in the two files that match each other. */ 41996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project i0--; i1--; 42096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 42196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 42296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return script; 42396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 42496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 42596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Report the differences of two files. DEPTH is the current directory 42696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project depth. */ 42796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public change diff_2(final boolean reverse) { 42896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 42996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Some lines are obviously insertions or deletions 43096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project because they don't match anything. Detect them now, 43196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and avoid even thinking about them in the main comparison algorithm. */ 43296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 43396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discard_confusing_lines (); 43496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 43596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Now do the main comparison algorithm, considering just the 43696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project undiscarded lines. */ 43796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 43896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project xvec = filevec[0].undiscarded; 43996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project yvec = filevec[1].undiscarded; 44096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 44196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int diags = 44296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3; 44396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fdiag = new int[diags]; 44496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fdiagoff = filevec[1].nondiscarded_lines + 1; 44596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bdiag = new int[diags]; 44696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bdiagoff = filevec[1].nondiscarded_lines + 1; 44796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 44896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project compareseq (0, filevec[0].nondiscarded_lines, 44996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 0, filevec[1].nondiscarded_lines); 45096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project fdiag = null; 45196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project bdiag = null; 45296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 45396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Modify the results slightly to make them prettier 45496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project in cases where that can validly be done. */ 45596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 45696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project shift_boundaries (); 45796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 45896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Get the results of comparison in the form of a chain 45996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of `struct change's -- an edit script. */ 46096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 46196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (reverse) 46296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return build_reverse_script(); 46396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 46496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return build_script(); 46596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 46696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 46796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** The result of comparison is an "edit script": a chain of change objects. 46896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Each change represents one place where some lines are deleted 46996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and some are inserted. 47096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 47196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project LINE0 and LINE1 are the first affected lines in the two files (origin 0). 47296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project DELETED is the number of lines deleted here from file 0. 47396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project INSERTED is the number of lines inserted here in file 1. 47496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 47596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project If DELETED is 0 then LINE0 is the number of the line before 47696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project which the insertion was done; vice versa for INSERTED and LINE1. */ 47796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 47896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public static class change { 47996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Previous or next edit command. */ 48096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public change link; 48196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** # lines of file 1 changed here. */ 48296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public int inserted; 48396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** # lines of file 0 changed here. */ 48496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public int deleted; 48596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Line number of 1st deleted line. */ 48696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public final int line0; 48796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Line number of 1st inserted line. */ 48896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project public final int line1; 48996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 49096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Cons an additional entry onto the front of an edit script OLD. 49196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project LINE0 and LINE1 are the first affected lines in the two files (origin 0). 49296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project DELETED is the number of lines deleted here from file 0. 49396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project INSERTED is the number of lines inserted here in file 1. 49496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 49596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project If DELETED is 0 then LINE0 is the number of the line before 49696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project which the insertion was done; vice versa for INSERTED and LINE1. */ 49796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project change(int line0, int line1, int deleted, int inserted, change old) { 49896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this.line0 = line0; 49996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this.line1 = line1; 50096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this.inserted = inserted; 50196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this.deleted = deleted; 50296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this.link = old; 50396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project //System.err.println(line0+","+line1+","+inserted+","+deleted); 50496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 50596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 50696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 50796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Data on one input file being compared. 50896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 50996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 51096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project class file_data { 51196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 51296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Allocate changed array for the results of comparison. */ 51396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project void clear() { 51496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Allocate a flag for each line of each file, saying whether that line 51596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project is an insertion or deletion. 51696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Allocate an extra element, always zero, at each end of each vector. 51796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 51896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project changed_flag = new boolean[buffered_lines + 2]; 51996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 52096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 52196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Return equiv_count[I] as the number of lines in this file 52296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project that fall in equivalence class I. 52396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @return the array of equivalence class counts. 52496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 52596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int[] equivCount() { 52696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int[] equiv_count = new int[equiv_max]; 52796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int i = 0; i < buffered_lines; ++i) 52896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++equiv_count[equivs[i]]; 52996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return equiv_count; 53096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 53196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 53296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Discard lines that have no matches in another file. 53396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 53496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project A line which is discarded will not be considered by the actual 53596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project comparison algorithm; it will be as if that line were not in the file. 53696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The file's `realindexes' table maps virtual line numbers 53796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project (which don't count the discarded lines) into real line numbers; 53896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project this is how the actual comparison algorithm produces results 53996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project that are comprehensible when the discarded lines are counted. 54096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project<p> 54196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project When we discard a line, we also mark it as a deletion or insertion 54296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project so that it will be printed in the output. 54396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @param f the other file 54496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 54596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project void discard_confusing_lines(file_data f) { 54696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project clear(); 54796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Set up table of which lines are going to be discarded. */ 54896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final byte[] discarded = discardable(f.equivCount()); 54996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 55096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Don't really discard the provisional lines except when they occur 55196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project in a run of discardables, with nonprovisionals at the beginning 55296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and end. */ 55396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project filterDiscards(discarded); 55496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 55596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Actually discard the lines. */ 55696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discard(discarded); 55796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 55896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 55996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Mark to be discarded each line that matches no line of another file. 56096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project If a line matches many lines, mark it as provisionally discardable. 56196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @see equivCount() 56296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @param counts The count of each equivalence number for the other file. 56396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @return 0=nondiscardable, 1=discardable or 2=provisionally discardable 56496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for each line 56596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 56696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 56796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private byte[] discardable(final int[] counts) { 56896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int end = buffered_lines; 56996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final byte[] discards = new byte[end]; 57096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] equivs = this.equivs; 57196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int many = 5; 57296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int tem = end / 64; 57396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 57496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Multiply MANY by approximate square root of number of lines. 57596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project That is the threshold for provisionally discardable lines. */ 57696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while ((tem = tem >> 2) > 0) 57796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project many *= 2; 57896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 57996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int i = 0; i < end; i++) 58096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 58196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int nmatch; 58296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (equivs[i] == 0) 58396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project continue; 58496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project nmatch = counts[equivs[i]]; 58596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (nmatch == 0) 58696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[i] = 1; 58796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (nmatch > many) 58896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[i] = 2; 58996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 59096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project return discards; 59196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 59296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 59396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Don't really discard the provisional lines except when they occur 59496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project in a run of discardables, with nonprovisionals at the beginning 59596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and end. */ 59696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 59796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private void filterDiscards(final byte[] discards) { 59896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int end = buffered_lines; 59996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 60096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int i = 0; i < end; i++) 60196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 60296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Cancel provisional discards not in middle of run of discards. */ 60396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[i] == 2) 60496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[i] = 0; 60596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (discards[i] != 0) 60696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 60796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* We have found a nonprovisional discard. */ 60896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int j; 60996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int length; 61096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int provisional = 0; 61196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 61296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Find end of this run of discardable lines. 61396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Count how many are provisionally discardable. */ 61496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (j = i; j < end; j++) 61596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 61696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[j] == 0) 61796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 61896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[j] == 2) 61996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++provisional; 62096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 62196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 62296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Cancel provisional discards at end, and shrink the run. */ 62396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (j > i && discards[j - 1] == 2) { 62496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[--j] = 0; --provisional; 62596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 62696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 62796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Now we have the length of a run of discardable lines 62896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project whose first and last are not provisional. */ 62996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project length = j - i; 63096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 63196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* If 1/4 of the lines in the run are provisional, 63296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project cancel discarding of all provisional lines in the run. */ 63396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (provisional * 4 > length) 63496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 63596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (j > i) 63696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[--j] == 2) 63796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[j] = 0; 63896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 63996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 64096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 64196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int consec; 64296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int minimum = 1; 64396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int tem = length / 4; 64496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 64596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* MINIMUM is approximate square root of LENGTH/4. 64696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project A subrun of two or more provisionals can stand 64796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project when LENGTH is at least 16. 64896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project A subrun of 4 or more can stand when LENGTH >= 64. */ 64996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while ((tem = tem >> 2) > 0) 65096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project minimum *= 2; 65196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project minimum++; 65296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 65396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Cancel any subrun of MINIMUM or more provisionals 65496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project within the larger run. */ 65596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (j = 0, consec = 0; j < length; j++) 65696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[i + j] != 2) 65796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec = 0; 65896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (minimum == ++consec) 65996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Back up to start of subrun, to cancel it all. */ 66096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project j -= consec; 66196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (minimum < consec) 66296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project discards[i + j] = 0; 66396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 66496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Scan from beginning of run 66596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project until we find 3 or more nonprovisionals in a row 66696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project or until the first nonprovisional at least 8 lines in. 66796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Until that point, cancel any provisionals. */ 66896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (j = 0, consec = 0; j < length; j++) 66996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 67096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (j >= 8 && discards[i + j] == 1) 67196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 67296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[i + j] == 2) { 67396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec = 0; discards[i + j] = 0; 67496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 67596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (discards[i + j] == 0) 67696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec = 0; 67796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 67896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec++; 67996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (consec == 3) 68096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 68196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 68296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 68396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* I advances to the last line of the run. */ 68496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project i += length - 1; 68596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 68696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Same thing, from end. */ 68796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (j = 0, consec = 0; j < length; j++) 68896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 68996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (j >= 8 && discards[i - j] == 1) 69096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 69196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (discards[i - j] == 2) { 69296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec = 0; discards[i - j] = 0; 69396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 69496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else if (discards[i - j] == 0) 69596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec = 0; 69696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 69796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project consec++; 69896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (consec == 3) 69996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 70096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 70196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 70296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 70396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 70496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 70596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 70696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Actually discard the lines. 70796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @param discards flags lines to be discarded 70896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 70996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private void discard(final byte[] discards) { 71096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int end = buffered_lines; 71196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int j = 0; 71296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int i = 0; i < end; ++i) 71396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (no_discards || discards[i] == 0) 71496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 71596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project undiscarded[j] = equivs[i]; 71696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project realindexes[j++] = i; 71796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 71896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 71996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project changed_flag[1+i] = true; 72096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project nondiscarded_lines = j; 72196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 72296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 72396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project file_data(Object[] data,Hashtable h) { 72496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project buffered_lines = data.length; 72596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 72696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project equivs = new int[buffered_lines]; 72796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project undiscarded = new int[buffered_lines]; 72896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project realindexes = new int[buffered_lines]; 72996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 73096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (int i = 0; i < data.length; ++i) { 73196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Integer ir = (Integer)h.get(data[i]); 73296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (ir == null) 73396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project h.put(data[i],new Integer(equivs[i] = equiv_max++)); 73496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 73596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project equivs[i] = ir.intValue(); 73696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 73796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 73896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 73996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Adjust inserts/deletes of blank lines to join changes 74096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project as much as possible. 74196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 74296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project We do something when a run of changed lines include a blank 74396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project line at one end and have an excluded blank line at the other. 74496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project We are free to choose which blank line is included. 74596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project `compareseq' always chooses the one at the beginning, 74696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project but usually it is cleaner to consider the following blank line 74796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project to be the "change". The only exception is if the preceding blank line 74896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project would join this change to other changes. 74996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project @param f the file being compared against 75096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project */ 75196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 75296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project void shift_boundaries(file_data f) { 75396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] changed = changed_flag; 75496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final boolean[] other_changed = f.changed_flag; 75596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int i = 0; 75696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int j = 0; 75796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int i_end = buffered_lines; 75896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int preceding = -1; 75996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int other_preceding = -1; 76096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 76196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (;;) 76296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 76396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int start, end, other_start; 76496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 76596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Scan forwards to find beginning of another run of changes. 76696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Also keep track of the corresponding point in the other file. */ 76796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 76896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (i < i_end && !changed[1+i]) 76996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 77096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (other_changed[1+j++]) 77196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Non-corresponding lines in the other file 77296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project will count as the preceding batch of changes. */ 77396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project other_preceding = j; 77496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project i++; 77596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 77696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 77796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (i == i_end) 77896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 77996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 78096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project start = i; 78196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project other_start = j; 78296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 78396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project for (;;) 78496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 78596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Now find the end of this run of changes. */ 78696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 78796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project while (i < i_end && changed[1+i]) i++; 78896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project end = i; 78996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 79096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* If the first changed line matches the following unchanged one, 79196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and this run does not follow right after a previous run, 79296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and there are no lines deleted from the other file here, 79396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project then classify the first changed line as unchanged 79496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project and the following line as changed in its place. */ 79596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 79696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* You might ask, how could this run follow right after another? 79796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project Only because the previous run was shifted here. */ 79896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 79996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project if (end != i_end 80096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && equivs[start] == equivs[end] 80196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && !other_changed[1+j] 80296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && end != i_end 80396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && !((preceding >= 0 && start == preceding) 80496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project || (other_preceding >= 0 80596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project && other_start == other_preceding))) 80696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project { 80796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project changed[1+end++] = true; 80896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project changed[1+start++] = false; 80996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++i; 81096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /* Since one line-that-matches is now before this run 81196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project instead of after, we must advance in the other file 81296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project to keep in synch. */ 81396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project ++j; 81496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 81596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project else 81696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project break; 81796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 81896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 81996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project preceding = i; 82096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project other_preceding = j; 82196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 82296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 82396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 82496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Number of elements (lines) in this file. */ 82596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int buffered_lines; 82696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 82796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Vector, indexed by line number, containing an equivalence code for 82896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project each line. It is this vector that is actually compared with that 82996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project of another file to generate differences. */ 83096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project private final int[] equivs; 83196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 83296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Vector, like the previous one except that 83396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project the elements for discarded lines have been squeezed out. */ 83496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] undiscarded; 83596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 83696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Vector mapping virtual line numbers (not counting discarded lines) 83796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project to real ones (counting those lines). Both are origin-0. */ 83896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project final int[] realindexes; 83996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 84096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Total number of nondiscarded lines. */ 84196b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project int nondiscarded_lines; 84296b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 84396b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project /** Array, indexed by real origin-1 line number, 84496b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project containing true for a line that is an insertion or a deletion. 84596b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project The results of comparison are stored here. */ 84696b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project boolean[] changed_flag; 84796b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 84896b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project } 84996b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project 85096b00fec6cd6068c1c5ae09de0358340c0ec499eThe Android Open Source Project} 851