1/* GENERATED SOURCE. DO NOT MODIFY. */ 2/** 3******************************************************************************* 4* Copyright (C) 1996-2009, International Business Machines Corporation and * 5* others. All Rights Reserved. * 6******************************************************************************* 7*/ 8 9package android.icu.impl; 10 11/** VERY Basic Diff program. Compares two sequences of objects fed into it, and 12 * lets you know where they are different. 13 * @author Mark Davis 14 * @version 1.0 15 * @hide Only a subset of ICU is exposed in Android 16 */ 17 18final public class Differ<T> { 19// public static final String copyright = 20// "Copyright (C) 2010, International Business Machines Corporation and others. All Rights Reserved."; 21 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 @SuppressWarnings("unchecked") 27 public Differ(int stackSize, int matchCount) { 28 this.STACKSIZE = stackSize; 29 this.EQUALSIZE = matchCount; 30 a = (T[]) new Object[stackSize+matchCount]; 31 b = (T[]) new Object[stackSize+matchCount]; 32 } 33 34 public void add (T aStr, T bStr) { 35 addA(aStr); 36 addB(bStr); 37 } 38 39 public void addA (T aStr) { 40 flush(); 41 a[aCount++] = aStr; 42 } 43 44 public void addB (T bStr) { 45 flush(); 46 b[bCount++] = bStr; 47 } 48 49 public int getALine(int offset) { 50 return aLine + maxSame + offset; 51 } 52 53 public T getA(int offset) { 54 if (offset < 0) return last; 55 if (offset > aTop-maxSame) return next; 56 return a[offset]; 57 } 58 59 public int getACount() { 60 return aTop-maxSame; 61 } 62 63 public int getBCount() { 64 return bTop-maxSame; 65 } 66 67 public int getBLine(int offset) { 68 return bLine + maxSame + offset; 69 } 70 71 public T getB(int offset) { 72 if (offset < 0) return last; 73 if (offset > bTop-maxSame) return next; 74 return b[offset]; 75 } 76 77 public void checkMatch(boolean finalPass) { 78 // find the initial strings that are the same 79 int max = aCount; 80 if (max > bCount) max = bCount; 81 int i; 82 for (i = 0; i < max; ++i) { 83 if (!a[i].equals(b[i])) break; 84 } 85 // at this point, all items up to i are equal 86 maxSame = i; 87 aTop = bTop = maxSame; 88 if (maxSame > 0) last = a[maxSame-1]; 89 next = null; 90 91 if (finalPass) { 92 aTop = aCount; 93 bTop = bCount; 94 next = null; 95 return; 96 } 97 98 if (aCount - maxSame < EQUALSIZE || bCount - maxSame < EQUALSIZE) return; 99 100 // now see if the last few a's occur anywhere in the b's, or vice versa 101 int match = find (a, aCount-EQUALSIZE, aCount, b, maxSame, bCount); 102 if (match != -1) { 103 aTop = aCount-EQUALSIZE; 104 bTop = match; 105 next = a[aTop]; 106 return; 107 } 108 match = find (b, bCount-EQUALSIZE, bCount, a, maxSame, aCount); 109 if (match != -1) { 110 bTop = bCount-EQUALSIZE; 111 aTop = match; 112 next = b[bTop]; 113 return; 114 } 115 if (aCount >= STACKSIZE || bCount >= STACKSIZE) { 116 // flush some of them 117 aCount = (aCount + maxSame) / 2; 118 bCount = (bCount + maxSame) / 2; 119 next = null; 120 } 121 } 122 123 /** Convenient utility 124 * finds a segment of the first array in the second array. 125 * @return -1 if not found, otherwise start position in b 126 */ 127 128 public int find (T[] aArr, int aStart, int aEnd, T[] bArr, int bStart, int bEnd) { 129 int len = aEnd - aStart; 130 int bEndMinus = bEnd - len; 131 tryA: 132 for (int i = bStart; i <= bEndMinus; ++i) { 133 for (int j = 0; j < len; ++j) { 134 if (!bArr[i + j].equals(aArr[aStart + j])) continue tryA; 135 } 136 return i; // we have a match! 137 } 138 return -1; 139 } 140 141 // ====================== PRIVATES ====================== 142 143 private void flush() { 144 if (aTop != 0) { 145 int newCount = aCount-aTop; 146 System.arraycopy(a, aTop, a, 0, newCount); 147 aCount = newCount; 148 aLine += aTop; 149 aTop = 0; 150 } 151 152 if (bTop != 0) { 153 int newCount = bCount-bTop; 154 System.arraycopy(b, bTop, b, 0, newCount); 155 bCount = newCount; 156 bLine += bTop; 157 bTop = 0; 158 } 159 } 160 161 private int STACKSIZE; 162 private int EQUALSIZE; 163 164 private T [] a; 165 private T [] b; 166 private T last = null; 167 private T next = null; 168 private int aCount = 0; 169 private int bCount = 0; 170 private int aLine = 1; 171 private int bLine = 1; 172 private int maxSame = 0, aTop = 0, bTop = 0; 173 174} 175