Home | History | Annotate | Download | only in translit 
      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      */
     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 
     33     public void addA(int aStr) {
     34         flush();
     35         a[aCount++] = aStr;
     36     }
     37 
     38     public void addB(int bStr) {
     39         flush();
     40         b[bCount++] = bStr;
     41     }
     42 
     43     public int getA(int offset) {
     44         return a[maxSame + offset];
     45     }
     46 
     47     public int getACount() {
     48         return aTop-maxSame;
     49     }
     50 
     51     public int getBCount() {
     52         return bTop-maxSame;
     53     }
     54 
     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      */
     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      */
    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. */
    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