Debian Codegraph @

demos/src/main/java/com/ibm/icu/dev/demo/translit/IntDiffer.java

raw
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /**
4 *******************************************************************************
5 * Copyright (C) 1996-2016, International Business Machines Corporation and
6 * others. All Rights Reserved.
7 *******************************************************************************
8 */
9
10 package 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 */
21 final 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 }