jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/impl/Differ.java

   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")
  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
  32     public void add (T aStr, T bStr) {
  33         addA(aStr);
  34         addB(bStr);
  35     }
  36
  37     public void addA (T aStr) {
  38         flush();
  39         a[aCount++] = aStr;
  40     }
  41
  42     public void addB (T bStr) {
  43         flush();
  44         b[bCount++] = bStr;
  45     }
  46
  47     public int getALine(int offset) {
  48         return aLine + maxSame + offset;
  49     }
  50
  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
  57     public int getACount() {
  58         return aTop-maxSame;
  59     }
  60
  61     public int getBCount() {
  62         return bTop-maxSame;
  63     }
  64
  65     public int getBLine(int offset) {
  66         return bLine + maxSame + offset;
  67     }
  68
  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
  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
 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
 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 }