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