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