| 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 |
} |