1/**
2*******************************************************************************
3* Copyright (C) 1996-2009, International Business Machines Corporation and    *
4* others. All Rights Reserved.                                                *
5*******************************************************************************
6*/
7
8package com.ibm.icu.impl;
9
10/** VERY Basic Diff program. Compares two sequences of objects fed into it, and
11 * lets you know where they are different.
12 * @author Mark Davis
13 * @version 1.0
14 */
15
16final public class Differ<T> {
17//    public static final String copyright =
18//      "Copyright (C) 2010, International Business Machines Corporation and others. All Rights Reserved.";
19
20    /**
21     * @param stackSize The size of the largest difference you expect.
22     * @param matchCount The number of items that have to be the same to count as a match
23     */
24    @SuppressWarnings("unchecked")
25    public Differ(int stackSize, int matchCount) {
26        this.STACKSIZE = stackSize;
27        this.EQUALSIZE = matchCount;
28        a = (T[]) new Object[stackSize+matchCount];
29        b = (T[]) new Object[stackSize+matchCount];
30    }
31
32    public void add (T aStr, T bStr) {
33        addA(aStr);
34        addB(bStr);
35    }
36
37    public void addA (T aStr) {
38        flush();
39        a[aCount++] = aStr;
40    }
41
42    public void addB (T bStr) {
43        flush();
44        b[bCount++] = bStr;
45    }
46
47    public int getALine(int offset) {
48        return aLine + maxSame + offset;
49    }
50
51    public T getA(int offset) {
52        if (offset < 0) return last;
53        if (offset > aTop-maxSame) return next;
54        return a[offset];
55    }
56
57    public int getACount() {
58        return aTop-maxSame;
59    }
60
61    public int getBCount() {
62        return bTop-maxSame;
63    }
64
65    public int getBLine(int offset) {
66        return bLine + maxSame + offset;
67    }
68
69    public T getB(int offset) {
70        if (offset < 0) return last;
71        if (offset > bTop-maxSame) return next;
72        return b[offset];
73    }
74
75    public void checkMatch(boolean finalPass) {
76        // find the initial strings that are the same
77        int max = aCount;
78        if (max > bCount) max = bCount;
79        int i;
80        for (i = 0; i < max; ++i) {
81            if (!a[i].equals(b[i])) break;
82        }
83        // at this point, all items up to i are equal
84        maxSame = i;
85        aTop = bTop = maxSame;
86        if (maxSame > 0) last = a[maxSame-1];
87        next = null;
88
89        if (finalPass) {
90            aTop = aCount;
91            bTop = bCount;
92            next = null;
93            return;
94        }
95
96        if (aCount - maxSame < EQUALSIZE || bCount - maxSame < EQUALSIZE) return;
97
98        // now see if the last few a's occur anywhere in the b's, or vice versa
99        int match = find (a, aCount-EQUALSIZE, aCount, b, maxSame, bCount);
100        if (match != -1) {
101            aTop = aCount-EQUALSIZE;
102            bTop = match;
103            next = a[aTop];
104            return;
105        }
106        match = find (b, bCount-EQUALSIZE, bCount, a, maxSame, aCount);
107        if (match != -1) {
108            bTop = bCount-EQUALSIZE;
109            aTop = match;
110            next = b[bTop];
111            return;
112        }
113        if (aCount >= STACKSIZE || bCount >= STACKSIZE) {
114            // flush some of them
115            aCount = (aCount + maxSame) / 2;
116            bCount = (bCount + maxSame) / 2;
117            next = null;
118        }
119    }
120
121    /** Convenient utility
122     * finds a segment of the first array in the second array.
123     * @return -1 if not found, otherwise start position in b
124     */
125
126    public int find (T[] aArr, int aStart, int aEnd, T[] bArr, int bStart, int bEnd) {
127        int len = aEnd - aStart;
128        int bEndMinus = bEnd - len;
129        tryA:
130        for (int i = bStart; i <= bEndMinus; ++i) {
131            for (int j = 0; j < len; ++j) {
132                if (!bArr[i + j].equals(aArr[aStart + j])) continue tryA;
133            }
134            return i; // we have a match!
135        }
136        return -1;
137    }
138
139    // ====================== PRIVATES ======================
140
141    private void flush() {
142        if (aTop != 0) {
143            int newCount = aCount-aTop;
144            System.arraycopy(a, aTop, a, 0, newCount);
145            aCount = newCount;
146            aLine += aTop;
147            aTop = 0;
148        }
149
150        if (bTop != 0) {
151            int newCount = bCount-bTop;
152            System.arraycopy(b, bTop, b, 0, newCount);
153            bCount = newCount;
154            bLine += bTop;
155            bTop = 0;
156        }
157    }
158
159    private int STACKSIZE;
160    private int EQUALSIZE;
161
162    private T [] a;
163    private T [] b;
164    private T last = null;
165    private T next = null;
166    private int aCount = 0;
167    private int bCount = 0;
168    private int aLine = 1;
169    private int bLine = 1;
170    private int maxSame = 0, aTop = 0, bTop = 0;
171
172}
173