jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/util/CompactCharArray.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.util;\r
   9 \r
  10 import com.ibm.icu.impl.Utility;\r
  11 \r
  12 /**\r
  13  * class CompactATypeArray : use only on primitive data types\r
  14  * Provides a compact way to store information that is indexed by Unicode\r
  15  * values, such as character properties, types, keyboard values, etc.This\r
  16  * is very useful when you have a block of Unicode data that contains\r
  17  * significant values while the rest of the Unicode data is unused in the\r
  18  * application or when you have a lot of redundance, such as where all 21,000\r
  19  * Han ideographs have the same value.  However, lookup is much faster than a\r
  20  * hash table.\r
  21  * A compact array of any primitive data type serves two purposes:\r
  22  * <UL type = round>\r
  23  *     <LI>Fast access of the indexed values.\r
  24  *     <LI>Smaller memory footprint.\r
  25  * </UL>\r
  26  * A compact array is composed of a index array and value array.  The index\r
  27  * array contains the indicies of Unicode characters to the value array.\r
  28  * @see                CompactByteArray\r
  29  * @author             Helena Shih\r
  30  * @internal\r
  31  * @deprecated This API is ICU internal only.\r
  32  */\r
  33 public final class CompactCharArray implements Cloneable {\r
  34 \r
  35     /**\r
  36      * The total number of Unicode characters.\r
  37      * @internal\r
  38      * @deprecated This API is ICU internal only.\r
  39      */\r
  40     public static  final int UNICODECOUNT = 65536;\r
  41 \r
  42     /**\r
  43      * Default constructor for CompactCharArray, the default value of the\r
  44      * compact array is 0.\r
  45      * @internal\r
  46      * @deprecated This API is ICU internal only.\r
  47      */\r
  48     public CompactCharArray()\r
  49     {\r
  50         this((char)0);\r
  51     }\r
  52 \r
  53     /**\r
  54      * Constructor for CompactCharArray.\r
  55      * @param defaultValue the default value of the compact array.\r
  56      * @internal\r
  57      * @deprecated This API is ICU internal only.\r
  58      */\r
  59     public CompactCharArray(char defaultValue)\r
  60     {\r
  61         int i;\r
  62         values = new char[UNICODECOUNT];\r
  63         indices = new char[INDEXCOUNT];\r
  64         hashes = new int[INDEXCOUNT];\r
  65         for (i = 0; i < UNICODECOUNT; ++i) {\r
  66             values[i] = defaultValue;\r
  67         }\r
  68         for (i = 0; i < INDEXCOUNT; ++i) {\r
  69             indices[i] = (char)(i<<BLOCKSHIFT);\r
  70             hashes[i] = 0;\r
  71         }\r
  72         isCompact = false;\r
  73 \r
  74         this.defaultValue = defaultValue;\r
  75     }\r
  76 \r
  77     /**\r
  78      * Constructor for CompactCharArray.\r
  79      * @param indexArray the indicies of the compact array.\r
  80      * @param newValues the values of the compact array.\r
  81      * @exception IllegalArgumentException If the index is out of range.\r
  82      * @internal\r
  83      * @deprecated This API is ICU internal only.\r
  84      */\r
  85     public CompactCharArray(char indexArray[],\r
  86                              char newValues[])\r
  87     {\r
  88         int i;\r
  89         if (indexArray.length != INDEXCOUNT)\r
  90             throw new IllegalArgumentException("Index out of bounds.");\r
  91         for (i = 0; i < INDEXCOUNT; ++i) {\r
  92             char index = indexArray[i];\r
  93             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))\r
  94                 throw new IllegalArgumentException("Index out of bounds.");\r
  95         }\r
  96         indices = indexArray;\r
  97         values = newValues;\r
  98         isCompact = true;\r
  99     }\r
 100 \r
 101     /**\r
 102      * Constructor for CompactCharArray.\r
 103      *\r
 104      * @param indexArray the RLE-encoded indicies of the compact array.\r
 105      * @param valueArray the RLE-encoded values of the compact array.\r
 106      *\r
 107      * @throws IllegalArgumentException if the index or value array is\r
 108      *          the wrong size.\r
 109      * @internal\r
 110      * @deprecated This API is ICU internal only.\r
 111      */\r
 112     public CompactCharArray(String indexArray,\r
 113                 String valueArray)\r
 114     {\r
 115         this( Utility.RLEStringToCharArray(indexArray),\r
 116               Utility.RLEStringToCharArray(valueArray));\r
 117     }\r
 118 \r
 119     /**\r
 120      * Get the mapped value of a Unicode character.\r
 121      * @param index the character to get the mapped value with\r
 122      * @return the mapped value of the given character\r
 123      * @internal\r
 124      * @deprecated This API is ICU internal only.\r
 125      */\r
 126     public char elementAt(char index)\r
 127     {\r
 128     int ix = (indices[index >> BLOCKSHIFT] & 0xFFFF)\r
 129         + (index & BLOCKMASK);\r
 130     return ix >= values.length ? defaultValue : values[ix];\r
 131     }\r
 132 \r
 133     /**\r
 134      * Set a new value for a Unicode character.\r
 135      * Set automatically expands the array if it is compacted.\r
 136      * @param index the character to set the mapped value with\r
 137      * @param value the new mapped value\r
 138      * @internal\r
 139      * @deprecated This API is ICU internal only.\r
 140      */\r
 141     public void setElementAt(char index, char value)\r
 142     {\r
 143         if (isCompact)\r
 144             expand();\r
 145          values[(int)index] = value;\r
 146         touchBlock(index >> BLOCKSHIFT, value);\r
 147     }\r
 148 \r
 149     /**\r
 150      * Set new values for a range of Unicode character.\r
 151      *\r
 152      * @param start the starting offset of the range\r
 153      * @param end the ending offset of the range\r
 154      * @param value the new mapped value\r
 155      * @internal\r
 156      * @deprecated This API is ICU internal only.\r
 157      */\r
 158     public void setElementAt(char start, char end, char value)\r
 159     {\r
 160         int i;\r
 161         if (isCompact) {\r
 162             expand();\r
 163         }\r
 164         for (i = start; i <= end; ++i) {\r
 165             values[i] = value;\r
 166             touchBlock(i >> BLOCKSHIFT, value);\r
 167         }\r
 168     }\r
 169     /**\r
 170      * Compact the array\r
 171      * @internal\r
 172      * @deprecated This API is ICU internal only.\r
 173      */\r
 174     public void compact() {\r
 175         compact(true);\r
 176     }\r
 177 \r
 178     /**\r
 179      * Compact the array.\r
 180      * @internal\r
 181      * @deprecated This API is ICU internal only.\r
 182      */\r
 183     public void compact(boolean exhaustive)\r
 184     {\r
 185         if (!isCompact) {\r
 186             int iBlockStart = 0;\r
 187             char iUntouched = 0xFFFF;\r
 188             int newSize = 0;\r
 189 \r
 190             char[] target = exhaustive ? new char[UNICODECOUNT] : values;\r
 191 \r
 192             for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {\r
 193                 indices[i] = 0xFFFF;\r
 194                 boolean touched = blockTouched(i);\r
 195                 if (!touched && iUntouched != 0xFFFF) {\r
 196                     // If no values in this block were set, we can just set its\r
 197                     // index to be the same as some other block with no values\r
 198                     // set, assuming we've seen one yet.\r
 199                     indices[i] = iUntouched;\r
 200                 } else {\r
 201                     int jBlockStart = 0;\r
 202                     // See if we can find a previously compacted block that's identical\r
 203                     for (int j = 0; j < i; ++j, jBlockStart += BLOCKCOUNT) {\r
 204                         if (hashes[i] == hashes[j] &&\r
 205                                 arrayRegionMatches(values, iBlockStart,\r
 206                                                    values, jBlockStart, BLOCKCOUNT)) {\r
 207                             indices[i] = indices[j];\r
 208                         }\r
 209                     }\r
 210                     if (indices[i] == 0xFFFF) {\r
 211                         int dest;   // Where to copy\r
 212                         if (exhaustive) {\r
 213                             // See if we can find some overlap with another block\r
 214                             dest = FindOverlappingPosition(iBlockStart, target,\r
 215                                                             newSize);\r
 216                         } else {\r
 217                             // Just copy to the end; it's quicker\r
 218                             dest = newSize;\r
 219                         }\r
 220                         int limit = dest + BLOCKCOUNT;\r
 221                         if (limit > newSize) {\r
 222                             for (int j = newSize; j < limit; ++j) {\r
 223                                 target[j] = values[iBlockStart + j - dest];\r
 224                             }\r
 225                             newSize = limit;\r
 226                         }\r
 227                         indices[i] = (char)dest;\r
 228                         if (!touched) {\r
 229                             // If this is the first untouched block we've seen,\r
 230                             // remember its index.\r
 231                             iUntouched = (char)jBlockStart;\r
 232                         }\r
 233                     }\r
 234                 }\r
 235             }\r
 236             // we are done compacting, so now make the array shorter\r
 237             char[] result = new char[newSize];\r
 238             System.arraycopy(target, 0, result, 0, newSize);\r
 239             values = result;\r
 240             isCompact = true;\r
 241             hashes = null;\r
 242         }\r
 243     }\r
 244 \r
 245     private int FindOverlappingPosition(int start, char[] tempValues, int tempCount)\r
 246     {\r
 247         for (int i = 0; i < tempCount; i += 1) {\r
 248             int currentCount = BLOCKCOUNT;\r
 249             if (i + BLOCKCOUNT > tempCount) {\r
 250                 currentCount = tempCount - i;\r
 251             }\r
 252             if (arrayRegionMatches(values, start, tempValues, i, currentCount))\r
 253                 return i;\r
 254         }\r
 255         return tempCount;\r
 256     }\r
 257 \r
 258     /**\r
 259      * Convenience utility to compare two arrays of doubles.\r
 260      * @param len the length to compare.\r
 261      * The start indices and start+len must be valid.\r
 262      */\r
 263     final static boolean arrayRegionMatches(char[] source, int sourceStart,\r
 264                                             char[] target, int targetStart,\r
 265                                             int len)\r
 266     {\r
 267         int sourceEnd = sourceStart + len;\r
 268         int delta = targetStart - sourceStart;\r
 269         for (int i = sourceStart; i < sourceEnd; i++) {\r
 270             if (source[i] != target[i + delta])\r
 271             return false;\r
 272         }\r
 273         return true;\r
 274     }\r
 275 \r
 276     /**\r
 277      * Remember that a specified block was "touched", i.e. had a value set.\r
 278      * Untouched blocks can be skipped when compacting the array\r
 279      */\r
 280     private final void touchBlock(int i, int value) {\r
 281         hashes[i] = (hashes[i] + (value<<1)) | 1;\r
 282     }\r
 283 \r
 284     /**\r
 285      * Query whether a specified block was "touched", i.e. had a value set.\r
 286      * Untouched blocks can be skipped when compacting the array\r
 287      */\r
 288     private final boolean blockTouched(int i) {\r
 289         return hashes[i] != 0;\r
 290     }\r
 291 \r
 292     /**\r
 293      * For internal use only.  Do not modify the result, the behavior of\r
 294      * modified results are undefined.\r
 295      * @internal\r
 296      * @deprecated This API is ICU internal only.\r
 297      */\r
 298     public char[] getIndexArray()\r
 299     {\r
 300         return indices;\r
 301     }\r
 302 \r
 303     /**\r
 304      * For internal use only.  Do not modify the result, the behavior of\r
 305      * modified results are undefined.\r
 306      * @internal\r
 307      * @deprecated This API is ICU internal only.\r
 308      */\r
 309     public char[] getValueArray()\r
 310     {\r
 311         return values;\r
 312     }\r
 313 \r
 314     /**\r
 315      * Overrides Cloneable\r
 316      * @internal\r
 317      * @deprecated This API is ICU internal only.\r
 318      */\r
 319     public Object clone()\r
 320     {\r
 321         try {\r
 322             CompactCharArray other = (CompactCharArray) super.clone();\r
 323             other.values = values.clone();\r
 324             other.indices = indices.clone();\r
 325             if (hashes != null) other.hashes = hashes.clone();\r
 326             return other;\r
 327         } catch (CloneNotSupportedException e) {\r
 328             throw new IllegalStateException();\r
 329         }\r
 330     }\r
 331 \r
 332     /**\r
 333      * Compares the equality of two compact array objects.\r
 334      * @param obj the compact array object to be compared with this.\r
 335      * @return true if the current compact array object is the same\r
 336      * as the compact array object obj; false otherwise.\r
 337      * @internal\r
 338      * @deprecated This API is ICU internal only.\r
 339      */\r
 340     public boolean equals(Object obj) {\r
 341         if (obj == null) return false;\r
 342         if (this == obj)                      // quick check\r
 343             return true;\r
 344         if (getClass() != obj.getClass())         // same class?\r
 345             return false;\r
 346         CompactCharArray other = (CompactCharArray) obj;\r
 347         for (int i = 0; i < UNICODECOUNT; i++) {\r
 348             // could be sped up later\r
 349             if (elementAt((char)i) != other.elementAt((char)i))\r
 350                 return false;\r
 351         }\r
 352         return true; // we made it through the guantlet.\r
 353     }\r
 354 \r
 355     /**\r
 356      * Generates the hash code for the compact array object\r
 357      * @internal\r
 358      * @deprecated This API is ICU internal only.\r
 359      */\r
 360     public int hashCode() {\r
 361         int result = 0;\r
 362         int increment = Math.min(3, values.length/16);\r
 363         for (int i = 0; i < values.length; i+= increment) {\r
 364             result = result * 37 + values[i];\r
 365         }\r
 366         return result;\r
 367     }\r
 368 \r
 369 \r
 370     // --------------------------------------------------------------\r
 371     // private\r
 372     // --------------------------------------------------------------\r
 373 \r
 374     /**\r
 375      * Expanding takes the array back to a 65536 element array.\r
 376      */\r
 377     private void expand()\r
 378     {\r
 379         int i;\r
 380         if (isCompact) {\r
 381             char[] tempArray;\r
 382             hashes = new int[INDEXCOUNT];\r
 383             tempArray = new char[UNICODECOUNT];\r
 384             for (i = 0; i < UNICODECOUNT; ++i) {\r
 385                 tempArray[i] = elementAt((char)i);\r
 386             }\r
 387             for (i = 0; i < INDEXCOUNT; ++i) {\r
 388                 indices[i] = (char)(i<<BLOCKSHIFT);\r
 389             }\r
 390             values = null;\r
 391             values = tempArray;\r
 392             isCompact = false;\r
 393         }\r
 394     }\r
 395     /**\r
 396      * @internal\r
 397      * @deprecated This API is ICU internal only.\r
 398      */\r
 399     public static  final int BLOCKSHIFT = 5; // NormalizerBuilder needs - liu\r
 400     static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);\r
 401     static  final int INDEXSHIFT =(16-BLOCKSHIFT);\r
 402     static  final int INDEXCOUNT =(1<<INDEXSHIFT);\r
 403     static  final int BLOCKMASK = BLOCKCOUNT - 1;\r
 404 \r
 405     private char values[];\r
 406     private char indices[];\r
 407     private int[] hashes;\r
 408     private boolean isCompact;\r
 409     char defaultValue;\r
 410 }\r