diff.java

这个是网络上下载的一个struct框架的程序

        boolean odd = (fmid - bmid & 1) != 0;
        fd[fdiagoff + fmid] = xoff;
        bd[bdiagoff + bmid] = xlim;
        int c = 1;
        do
        {
            boolean big_snake = false;
            if(fmin > dmin)
                fd[(fdiagoff + --fmin) - 1] = -1;
            else
                fmin++;
            if(fmax < dmax)
                fd[fdiagoff + ++fmax + 1] = -1;
            else
                fmax--;
            for(int d = fmax; d >= fmin; d -= 2)
            {
                int tlo = fd[(fdiagoff + d) - 1];
                int thi = fd[fdiagoff + d + 1];
                int x;
                if(tlo >= thi)
                    x = tlo + 1;
                else
                    x = thi;
                int oldx = x;
                for(int y = x - d; x < xlim && y < ylim && xv[x] == yv[y]; y++)
                    x++;

                if(x - oldx > 20)
                    big_snake = true;
                fd[fdiagoff + d] = x;
                if(odd && bmin <= d && d <= bmax && bd[bdiagoff + d] <= fd[fdiagoff + d])
                {
                    cost = 2 * c - 1;
                    return d;
                }
            }

            if(bmin > dmin)
                bd[(bdiagoff + --bmin) - 1] = 0x7fffffff;
            else
                bmin++;
            if(bmax < dmax)
                bd[bdiagoff + ++bmax + 1] = 0x7fffffff;
            else
                bmax--;
            for(int d = bmax; d >= bmin; d -= 2)
            {
                int tlo = bd[(bdiagoff + d) - 1];
                int thi = bd[bdiagoff + d + 1];
                int x;
                if(tlo < thi)
                    x = tlo;
                else
                    x = thi - 1;
                int oldx = x;
                for(int y = x - d; x > xoff && y > yoff && xv[x - 1] == yv[y - 1]; y--)
                    x--;

                if(oldx - x > 20)
                    big_snake = true;
                bd[bdiagoff + d] = x;
                if(!odd && fmin <= d && d <= fmax && bd[bdiagoff + d] <= fd[fdiagoff + d])
                {
                    cost = 2 * c;
                    return d;
                }
            }

            if(c > 200 && big_snake && heuristic)
            {
                int best = 0;
                int bestpos = -1;
                for(int d = fmax; d >= fmin; d -= 2)
                {
                    int dd = d - fmid;
                    if((fd[fdiagoff + d] - xoff) * 2 - dd > 12 * (c + (dd <= 0 ? -dd : dd)) && (fd[fdiagoff + d] * 2 - dd > best && fd[fdiagoff + d] - xoff > 20 && fd[fdiagoff + d] - d - yoff > 20))
                    {
                        int x = fd[fdiagoff + d];
                        int k;
                        for(k = 1; k <= 20; k++)
                            if(xvec[x - k] != yvec[x - d - k])
                                break;

                        if(k == 21)
                        {
                            best = fd[fdiagoff + d] * 2 - dd;
                            bestpos = d;
                        }
                    }
                }

                if(best > 0)
                {
                    cost = 2 * c - 1;
                    return bestpos;
                }
                best = 0;
                for(int d = bmax; d >= bmin; d -= 2)
                {
                    int dd = d - bmid;
                    if((xlim - bd[bdiagoff + d]) * 2 + dd > 12 * (c + (dd <= 0 ? -dd : dd)) && ((xlim - bd[bdiagoff + d]) * 2 + dd > best && xlim - bd[bdiagoff + d] > 20 && ylim - (bd[bdiagoff + d] - d) > 20))
                    {
                        int x = bd[bdiagoff + d];
                        int k;
                        for(k = 0; k < 20; k++)
                            if(xvec[x + k] != yvec[(x - d) + k])
                                break;

                        if(k == 20)
                        {
                            best = (xlim - bd[bdiagoff + d]) * 2 + dd;
                            bestpos = d;
                        }
                    }
                }

                if(best > 0)
                {
                    cost = 2 * c - 1;
                    return bestpos;
                }
            }
            c++;
        } while(true);
    }

    private void compareseq(int xoff, int xlim, int yoff, int ylim)
    {
        for(; xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff]; yoff++)
            xoff++;

        for(; xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1]; ylim--)
            xlim--;

        if(xoff == xlim)
            while(yoff < ylim) 
                filevec[1].changed_flag[1 + filevec[1].realindexes[yoff++]] = true;
        else
        if(yoff == ylim)
        {
            while(xoff < xlim) 
                filevec[0].changed_flag[1 + filevec[0].realindexes[xoff++]] = true;
        } else
        {
            int d = diag(xoff, xlim, yoff, ylim);
            int c = cost;
            int f = fdiag[fdiagoff + d];
            int b = bdiag[bdiagoff + d];
            if(c == 1)
                throw new IllegalArgumentException("Empty subsequence");
            compareseq(xoff, b, yoff, b - d);
            compareseq(b, xlim, b - d, ylim);
        }
    }

    private void discard_confusing_lines()
    {
        filevec[0].discard_confusing_lines(filevec[1]);
        filevec[1].discard_confusing_lines(filevec[0]);
    }

    private void shift_boundaries()
    {
        if(inhibit)
        {
            return;
        } else
        {
            filevec[0].shift_boundaries(filevec[1]);
            filevec[1].shift_boundaries(filevec[0]);
            return;
        }
    }

    private change build_reverse_script()
    {
        change script = null;
        boolean changed0[] = filevec[0].changed_flag;
        boolean changed1[] = filevec[1].changed_flag;
        int len0 = filevec[0].buffered_lines;
        int len1 = filevec[1].buffered_lines;
        int i0 = 0;
        for(int i1 = 0; i0 < len0 || i1 < len1; i1++)
        {
            if(changed0[1 + i0] || changed1[1 + i1])
            {
                int line0 = i0;
                int line1 = i1;
                for(; changed0[1 + i0]; i0++);
                for(; changed1[1 + i1]; i1++);
                script = new change(line0, line1, i0 - line0, i1 - line1, script);
            }
            i0++;
        }

        return script;
    }

    private change build_script()
    {
        change script = null;
        boolean changed0[] = filevec[0].changed_flag;
        boolean changed1[] = filevec[1].changed_flag;
        int len0 = filevec[0].buffered_lines;
        int len1 = filevec[1].buffered_lines;
        int i0 = len0;
        for(int i1 = len1; i0 >= 0 || i1 >= 0; i1--)
        {
            if(changed0[i0] || changed1[i1])
            {
                int line0 = i0;
                int line1 = i1;
                for(; changed0[i0]; i0--);
                for(; changed1[i1]; i1--);
                script = new change(i0, i1, line0 - i0, line1 - i1, script);
            }
            i0--;
        }

        return script;
    }

    public change diff_2(boolean reverse)
    {
        discard_confusing_lines();
        xvec = filevec[0].undiscarded;
        yvec = filevec[1].undiscarded;
        int diags = filevec[0].nondiscarded_lines + filevec[1].nondiscarded_lines + 3;
        fdiag = new int[diags];
        fdiagoff = filevec[1].nondiscarded_lines + 1;
        bdiag = new int[diags];
        bdiagoff = filevec[1].nondiscarded_lines + 1;
        compareseq(0, filevec[0].nondiscarded_lines, 0, filevec[1].nondiscarded_lines);
        fdiag = null;
        bdiag = null;
        shift_boundaries();
        if(reverse)
            return build_reverse_script();
        else
            return build_script();
    }

    public Diff(Object a[], Object b[])
    {
        equiv_max = 1;
        heuristic = false;
        no_discards = false;
        inhibit = false;
        Hashtable h = new Hashtable(a.length + b.length);
        filevec[0] = new file_data(a, h);
        filevec[1] = new file_data(b, h);
    }

    private int equiv_max;
    public boolean heuristic;
    public boolean no_discards;
    private int xvec[];
    private int yvec[];
    private int fdiag[];
    private int bdiag[];
    private int fdiagoff;
    private int bdiagoff;
    private final file_data filevec[] = new file_data[2];
    private int cost;
    private boolean inhibit;


}