1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html#License
3/**
4*******************************************************************************
5* Copyright (C) 1996-2016, International Business Machines Corporation and
6* others. All Rights Reserved.
7*******************************************************************************
8*/
9
10package com.ibm.icu.dev.demo.translit;
11
12/**
13 * VERY Basic Diff program. Compares two sequences of ints fed into it, and
14 * lets you know where they are different.
15 *
16 * <p>This version compares ints while the CLDR class Differ compares Objects.
17 *
18 * @author Mark Davis
19 * @version 1.0
20 */
21final public class IntDiffer {
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    public IntDiffer(int stackSize, int matchCount) {
27        this.STACKSIZE = stackSize;
28        this.EQUALSIZE = matchCount;
29        a = new int[stackSize+matchCount];
30        b = new int[stackSize+matchCount];
31    }
32
33    public void addA(int aStr) {
34        flush();
35        a[aCount++] = aStr;
36    }
37
38    public void addB(int bStr) {
39        flush();
40        b[bCount++] = bStr;
41    }
42
43    public int getA(int offset) {
44        return a[maxSame + offset];
45    }
46
47    public int getACount() {
48        return aTop-maxSame;
49    }
50
51    public int getBCount() {
52        return bTop-maxSame;
53    }
54
55    public int getB(int offset) {
56        return b[maxSame + offset];
57    }
58
59    /**
60     * Checks for initial & final match.
61     * To be called after addA() and addB().
62     * Middle segments that are different are returned via get*Count() and get*().
63     *
64     * @param finalPass true if no more input
65     */
66    public void checkMatch(boolean finalPass) {
67        // find the initial strings that are the same
68        int max = aCount;
69        if (max > bCount) max = bCount;
70        int i;
71        for (i = 0; i < max; ++i) {
72            if (a[i] != b[i]) break;
73        }
74        // at this point, all items up to i are equal
75        maxSame = i;
76        aTop = bTop = maxSame;
77
78        if (finalPass) {
79            aTop = aCount;
80            bTop = bCount;
81            return;
82        }
83
84        if (aCount - maxSame < EQUALSIZE || bCount - maxSame < EQUALSIZE) return;
85
86        // now see if the last few a's occur anywhere in the b's, or vice versa
87        int match = find(a, aCount-EQUALSIZE, aCount, b, maxSame, bCount);
88        if (match != -1) {
89            aTop = aCount-EQUALSIZE;
90            bTop = match;
91            return;
92        }
93        match = find(b, bCount-EQUALSIZE, bCount, a, maxSame, aCount);
94        if (match != -1) {
95            bTop = bCount-EQUALSIZE;
96            aTop = match;
97            return;
98        }
99        if (aCount >= STACKSIZE || bCount >= STACKSIZE) {
100            // flush some of them
101            aCount = (aCount + maxSame) / 2;
102            bCount = (bCount + maxSame) / 2;
103        }
104    }
105
106    /**
107     * Finds a segment of the first array in the second array.
108     * @return -1 if not found, otherwise start position in bArr
109     */
110    private int find(int[] aArr, int aStart, int aEnd, int[] bArr, int bStart, int bEnd) {
111        int len = aEnd - aStart;
112        int bEndMinus = bEnd - len;
113        tryA:
114        for (int i = bStart; i <= bEndMinus; ++i) {
115            for (int j = 0; j < len; ++j) {
116                if (bArr[i + j] != aArr[aStart + j]) continue tryA;
117            }
118            return i; // we have a match!
119        }
120        return -1;
121    }
122
123    // ====================== PRIVATES ======================
124
125    /** Removes equal prefixes of both arrays. */
126    private void flush() {
127        if (aTop != 0) {
128            int newCount = aCount-aTop;
129            System.arraycopy(a, aTop, a, 0, newCount);
130            aCount = newCount;
131            aTop = 0;
132        }
133
134        if (bTop != 0) {
135            int newCount = bCount-bTop;
136            System.arraycopy(b, bTop, b, 0, newCount);
137            bCount = newCount;
138            bTop = 0;
139        }
140    }
141
142    private int STACKSIZE;
143    private int EQUALSIZE;
144
145    // a[] and b[] are equal at 0 to before maxSame.
146    // maxSame to before *Top are different.
147    // *Top to *Count are equal again.
148    private int [] a;
149    private int [] b;
150    private int aCount = 0;
151    private int bCount = 0;
152    private int maxSame = 0, aTop = 0, bTop = 0;
153}
154