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 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 */ IntDiffer(int stackSize, int matchCount)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 addA(int aStr)33 public void addA(int aStr) { 34 flush(); 35 a[aCount++] = aStr; 36 } 37 addB(int bStr)38 public void addB(int bStr) { 39 flush(); 40 b[bCount++] = bStr; 41 } 42 getA(int offset)43 public int getA(int offset) { 44 return a[maxSame + offset]; 45 } 46 getACount()47 public int getACount() { 48 return aTop-maxSame; 49 } 50 getBCount()51 public int getBCount() { 52 return bTop-maxSame; 53 } 54 getB(int offset)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 */ checkMatch(boolean finalPass)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 */ find(int[] aArr, int aStart, int aEnd, int[] bArr, int bStart, int bEnd)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. */ flush()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