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