jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/impl/Differ.java

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