001: /**
002: *******************************************************************************
003: * Copyright (C) 1996-2005, International Business Machines Corporation and *
004: * others. All Rights Reserved. *
005: *******************************************************************************
006: */package com.ibm.icu.dev.test.util;
007:
008: /** VERY Basic Diff program. Compares two sequences of objects fed into it, and
009: * lets you know where they are different.
010: * @author Mark Davis
011: * @version 1.0
012: */
013:
014: final public class Differ {
015: public static final String copyright = "Copyright (C) 2000, International Business Machines Corporation and others. All Rights Reserved.";
016:
017: /**
018: * @param stackSize The size of the largest difference you expect.
019: * @param matchCount The number of items that have to be the same to count as a match
020: */
021: public Differ(int stackSize, int matchCount) {
022: this .STACKSIZE = stackSize;
023: this .EQUALSIZE = matchCount;
024: a = new Object[stackSize + matchCount];
025: b = new Object[stackSize + matchCount];
026: }
027:
028: public void add(Object aStr, Object bStr) {
029: addA(aStr);
030: addB(bStr);
031: }
032:
033: public void addA(Object aStr) {
034: flush();
035: a[aCount++] = aStr;
036: }
037:
038: public void addB(Object bStr) {
039: flush();
040: b[bCount++] = bStr;
041: }
042:
043: public int getALine(int offset) {
044: return aLine + maxSame + offset;
045: }
046:
047: public Object getA(int offset) {
048: if (offset < 0)
049: return last;
050: if (offset > aTop - maxSame)
051: return next;
052: return a[offset];
053: }
054:
055: public int getACount() {
056: return aTop - maxSame;
057: }
058:
059: public int getBCount() {
060: return bTop - maxSame;
061: }
062:
063: public int getBLine(int offset) {
064: return bLine + maxSame + offset;
065: }
066:
067: public Object getB(int offset) {
068: if (offset < 0)
069: return last;
070: if (offset > bTop - maxSame)
071: return next;
072: return b[offset];
073: }
074:
075: public void checkMatch(boolean finalPass) {
076: // find the initial strings that are the same
077: int max = aCount;
078: if (max > bCount)
079: max = bCount;
080: int i;
081: for (i = 0; i < max; ++i) {
082: if (!a[i].equals(b[i]))
083: break;
084: }
085: // at this point, all items up to i are equal
086: maxSame = i;
087: aTop = bTop = maxSame;
088: if (maxSame > 0)
089: last = a[maxSame - 1];
090: next = "";
091:
092: if (finalPass) {
093: aTop = aCount;
094: bTop = bCount;
095: next = "";
096: return;
097: }
098:
099: if (aCount - maxSame < EQUALSIZE
100: || bCount - maxSame < EQUALSIZE)
101: return;
102:
103: // now see if the last few a's occur anywhere in the b's, or vice versa
104: int match = find(a, aCount - EQUALSIZE, aCount, b, maxSame,
105: bCount);
106: if (match != -1) {
107: aTop = aCount - EQUALSIZE;
108: bTop = match;
109: next = a[aTop];
110: return;
111: }
112: match = find(b, bCount - EQUALSIZE, bCount, a, maxSame, aCount);
113: if (match != -1) {
114: bTop = bCount - EQUALSIZE;
115: aTop = match;
116: next = b[bTop];
117: return;
118: }
119: if (aCount >= STACKSIZE || bCount >= STACKSIZE) {
120: // flush some of them
121: aCount = (aCount + maxSame) / 2;
122: bCount = (bCount + maxSame) / 2;
123: next = "";
124: }
125: }
126:
127: /** Convenient utility
128: * finds a segment of the first array in the second array.
129: * @return -1 if not found, otherwise start position in b
130: */
131:
132: public int find(Object[] a, int aStart, int aEnd, Object[] b,
133: int bStart, int bEnd) {
134: int len = aEnd - aStart;
135: int bEndMinus = bEnd - len;
136: tryA: for (int i = bStart; i <= bEndMinus; ++i) {
137: for (int j = 0; j < len; ++j) {
138: if (!b[i + j].equals(a[aStart + j]))
139: continue tryA;
140: }
141: return i; // we have a match!
142: }
143: return -1;
144: }
145:
146: // ====================== PRIVATES ======================
147:
148: private void flush() {
149: if (aTop != 0) {
150: int newCount = aCount - aTop;
151: System.arraycopy(a, aTop, a, 0, newCount);
152: aCount = newCount;
153: aLine += aTop;
154: aTop = 0;
155: }
156:
157: if (bTop != 0) {
158: int newCount = bCount - bTop;
159: System.arraycopy(b, bTop, b, 0, newCount);
160: bCount = newCount;
161: bLine += bTop;
162: bTop = 0;
163: }
164: }
165:
166: private int STACKSIZE;
167: private int EQUALSIZE;
168:
169: private Object[] a;
170: private Object[] b;
171: private Object last = "";
172: private Object next = "";
173: private int aCount = 0;
174: private int bCount = 0;
175: private int aLine = 1;
176: private int bLine = 1;
177: private int maxSame = 0, aTop = 0, bTop = 0;
178:
179: }
|