12d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// © 2016 and later: Unicode, Inc. and others. 22d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert// License & terms of use: http://www.unicode.org/copyright.html#License 37935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert/** 47935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert******************************************************************************* 52d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert* Copyright (C) 1996-2016, International Business Machines Corporation and 62d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert* others. All Rights Reserved. 77935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert******************************************************************************* 87935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert*/ 97935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 102d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubertpackage com.ibm.icu.dev.demo.translit; 117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 122d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert/** 132d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * VERY Basic Diff program. Compares two sequences of ints fed into it, and 147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * lets you know where they are different. 152d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 162d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * <p>This version compares ints while the CLDR class Differ compares Objects. 172d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @author Mark Davis 197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @version 1.0 207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 212d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubertfinal public class IntDiffer { 227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert /** 237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param stackSize The size of the largest difference you expect. 247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert * @param matchCount The number of items that have to be the same to count as a match 257935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 262d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public IntDiffer(int stackSize, int matchCount) { 277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert this.STACKSIZE = stackSize; 287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert this.EQUALSIZE = matchCount; 292d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert a = new int[stackSize+matchCount]; 302d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert b = new int[stackSize+matchCount]; 317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 332d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public void addA(int aStr) { 347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert flush(); 357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert a[aCount++] = aStr; 367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 382d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public void addB(int bStr) { 397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert flush(); 407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert b[bCount++] = bStr; 417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 432d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int getA(int offset) { 442d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert return a[maxSame + offset]; 457935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 467935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 477935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getACount() { 487935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return aTop-maxSame; 497935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public int getBCount() { 527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return bTop-maxSame; 537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 547935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 552d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert public int getB(int offset) { 562d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert return b[maxSame + offset]; 577935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 587935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 592d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert /** 602d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Checks for initial & final match. 612d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * To be called after addA() and addB(). 622d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Middle segments that are different are returned via get*Count() and get*(). 632d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * 642d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * @param finalPass true if no more input 652d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert */ 667935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert public void checkMatch(boolean finalPass) { 677935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // find the initial strings that are the same 687935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int max = aCount; 697935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (max > bCount) max = bCount; 707935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int i; 717935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (i = 0; i < max; ++i) { 722d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert if (a[i] != b[i]) break; 737935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 747935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // at this point, all items up to i are equal 757935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert maxSame = i; 767935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aTop = bTop = maxSame; 777935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 787935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (finalPass) { 797935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aTop = aCount; 807935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bTop = bCount; 817935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return; 827935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 837935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 847935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (aCount - maxSame < EQUALSIZE || bCount - maxSame < EQUALSIZE) return; 857935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 867935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // now see if the last few a's occur anywhere in the b's, or vice versa 872d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert int match = find(a, aCount-EQUALSIZE, aCount, b, maxSame, bCount); 887935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (match != -1) { 897935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aTop = aCount-EQUALSIZE; 907935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bTop = match; 917935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return; 927935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 932d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert match = find(b, bCount-EQUALSIZE, bCount, a, maxSame, aCount); 947935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (match != -1) { 957935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bTop = bCount-EQUALSIZE; 967935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aTop = match; 977935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return; 987935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 997935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (aCount >= STACKSIZE || bCount >= STACKSIZE) { 1007935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // flush some of them 1017935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aCount = (aCount + maxSame) / 2; 1027935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bCount = (bCount + maxSame) / 2; 1037935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1047935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1057935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1062d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert /** 1072d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * Finds a segment of the first array in the second array. 1082d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert * @return -1 if not found, otherwise start position in bArr 1097935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert */ 1102d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert private int find(int[] aArr, int aStart, int aEnd, int[] bArr, int bStart, int bEnd) { 1117935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int len = aEnd - aStart; 1127935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int bEndMinus = bEnd - len; 1137935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert tryA: 1147935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int i = bStart; i <= bEndMinus; ++i) { 1157935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert for (int j = 0; j < len; ++j) { 1162d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert if (bArr[i + j] != aArr[aStart + j]) continue tryA; 1177935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1187935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return i; // we have a match! 1197935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1207935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert return -1; 1217935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1227935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1237935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert // ====================== PRIVATES ====================== 1247935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1252d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert /** Removes equal prefixes of both arrays. */ 1267935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private void flush() { 1277935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (aTop != 0) { 1287935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int newCount = aCount-aTop; 1297935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(a, aTop, a, 0, newCount); 1307935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aCount = newCount; 1317935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert aTop = 0; 1327935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1337935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1347935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert if (bTop != 0) { 1357935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert int newCount = bCount-bTop; 1367935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert System.arraycopy(b, bTop, b, 0, newCount); 1377935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bCount = newCount; 1387935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert bTop = 0; 1397935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1407935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert } 1417935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1427935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int STACKSIZE; 1437935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int EQUALSIZE; 1447935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert 1452d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert // a[] and b[] are equal at 0 to before maxSame. 1462d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert // maxSame to before *Top are different. 1472d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert // *Top to *Count are equal again. 1482d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert private int [] a; 1492d2bb24f747c65578da13d5b13b82f0669690461Fredrik Roubert private int [] b; 1507935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int aCount = 0; 1517935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int bCount = 0; 1527935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert private int maxSame = 0, aTop = 0, bTop = 0; 1537935b1839a081ed19ae0d33029ad3c09632a2caaFredrik Roubert} 154