jars/icu4j-4_2_1-src/src/com/ibm/icu/impl/Trie.java

   1 /*\r
   2 ******************************************************************************\r
   3 * Copyright (C) 1996-2008, 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 import java.io.InputStream;\r
  11 import java.io.DataInputStream;\r
  12 import java.io.IOException;\r
  13 import java.util.Arrays;\r
  14 import com.ibm.icu.text.UTF16;\r
  15 import com.ibm.icu.lang.UCharacter;\r
  16 \r
  17 /**\r
  18  * <p>A trie is a kind of compressed, serializable table of values \r
  19  * associated with Unicode code points (0..0x10ffff).</p>\r
  20  * <p>This class defines the basic structure of a trie and provides methods \r
  21  * to <b>retrieve the offsets to the actual data</b>.</p>\r
  22  * <p>Data will be the form of an array of basic types, char or int.</p>\r
  23  * <p>The actual data format will have to be specified by the user in the\r
  24  * inner static interface com.ibm.icu.impl.Trie.DataManipulate.</p>\r
  25  * <p>This trie implementation is optimized for getting offset while walking\r
  26  * forward through a UTF-16 string.\r
  27  * Therefore, the simplest and fastest access macros are the\r
  28  * fromLead() and fromOffsetTrail() methods.\r
  29  * The fromBMP() method are a little more complicated; they get offsets even\r
  30  * for lead surrogate codepoints, while the fromLead() method get special\r
  31  * "folded" offsets for lead surrogate code units if there is relevant data\r
  32  * associated with them.\r
  33  * From such a folded offsets, an offset needs to be extracted to supply\r
  34  * to the fromOffsetTrail() methods.\r
  35  * To handle such supplementary codepoints, some offset information are kept\r
  36  * in the data.</p>\r
  37  * <p>Methods in com.ibm.icu.impl.Trie.DataManipulate are called to retrieve \r
  38  * that offset from the folded value for the lead surrogate unit.</p>\r
  39  * <p>For examples of use, see com.ibm.icu.impl.CharTrie or \r
  40  * com.ibm.icu.impl.IntTrie.</p>\r
  41  * @author synwee\r
  42  * @see com.ibm.icu.impl.CharTrie\r
  43  * @see com.ibm.icu.impl.IntTrie\r
  44  * @since release 2.1, Jan 01 2002\r
  45  */\r
  46 public abstract class Trie\r
  47 {\r
  48     // public class declaration ----------------------------------------\r
  49     \r
  50     /**\r
  51     * Character data in com.ibm.impl.Trie have different user-specified format\r
  52     * for different purposes.\r
  53     * This interface specifies methods to be implemented in order for\r
  54     * com.ibm.impl.Trie, to surrogate offset information encapsulated within \r
  55     * the data.\r
  56     */\r
  57     public static interface DataManipulate\r
  58     {\r
  59         /**\r
  60         * Called by com.ibm.icu.impl.Trie to extract from a lead surrogate's \r
  61         * data\r
  62         * the index array offset of the indexes for that lead surrogate.\r
  63         * @param value data value for a surrogate from the trie, including the\r
  64         *        folding offset\r
  65         * @return data offset or 0 if there is no data for the lead surrogate\r
  66         */\r
  67         public int getFoldingOffset(int value); \r
  68     }\r
  69 \r
  70     // default implementation\r
  71     private static class DefaultGetFoldingOffset implements DataManipulate {\r
  72         public int getFoldingOffset(int value) {\r
  73             return value; \r
  74         }\r
  75     }\r
  76 \r
  77     // public methods --------------------------------------------------\r
  78     \r
  79     /**\r
  80      * Determines if this trie has a linear latin 1 array\r
  81      * @return true if this trie has a linear latin 1 array, false otherwise\r
  82      */\r
  83     public final boolean isLatin1Linear()\r
  84     {\r
  85         return m_isLatin1Linear_;\r
  86     }\r
  87     \r
  88     /**\r
  89      * Checks if the argument Trie has the same data as this Trie.\r
  90      * Attributes are checked but not the index data.\r
  91      * @param other Trie to check\r
  92      * @return true if the argument Trie has the same data as this Trie, false\r
  93      *         otherwise\r
  94      */\r
  95     ///CLOVER:OFF\r
  96     public boolean equals(Object other) \r
  97     {\r
  98         if (other == this) {\r
  99             return true;\r
 100         }\r
 101         if (!(other instanceof Trie)) {\r
 102             return false;\r
 103         }\r
 104         Trie othertrie = (Trie)other;\r
 105         return m_isLatin1Linear_ == othertrie.m_isLatin1Linear_\r
 106                && m_options_ == othertrie.m_options_\r
 107                && m_dataLength_ == othertrie.m_dataLength_\r
 108                && Arrays.equals(m_index_, othertrie.m_index_);\r
 109     }\r
 110     ///CLOVER:ON\r
 111     \r
 112     /**\r
 113      * Gets the serialized data file size of the Trie. This is used during \r
 114      * trie data reading for size checking purposes. \r
 115      * @return size size of serialized trie data file in terms of the number\r
 116      *              of bytes\r
 117      */\r
 118     public int getSerializedDataSize()\r
 119     {\r
 120         // includes signature, option, dataoffset and datalength output\r
 121         int result = (4 << 2);\r
 122         result += (m_dataOffset_ << 1);\r
 123         if (isCharTrie()) {\r
 124             result += (m_dataLength_ << 1);\r
 125         }\r
 126         else if (isIntTrie()) {\r
 127             result += (m_dataLength_ << 2);\r
 128         }\r
 129         return result;\r
 130     }\r
 131 \r
 132     // protected constructor -------------------------------------------\r
 133 \r
 134     /**\r
 135     * Trie constructor for CharTrie use.\r
 136     * @param inputStream ICU data file input stream which contains the\r
 137     *                        trie\r
 138     * @param dataManipulate object containing the information to parse the \r
 139     *                       trie data\r
 140     * @throws IOException thrown when input stream does not have the\r
 141     *                        right header.\r
 142     */\r
 143     protected Trie(InputStream inputStream, \r
 144                    DataManipulate  dataManipulate) throws IOException\r
 145     {\r
 146         DataInputStream input = new DataInputStream(inputStream);\r
 147         // Magic number to authenticate the data.\r
 148         int signature = input.readInt();\r
 149         m_options_    = input.readInt();\r
 150         \r
 151         if (!checkHeader(signature)) {\r
 152             throw new IllegalArgumentException("ICU data file error: Trie header authentication failed, please check if you have the most updated ICU data file");\r
 153         }\r
 154 \r
 155         if(dataManipulate != null) {\r
 156             m_dataManipulate_ = dataManipulate;\r
 157         } else {\r
 158             m_dataManipulate_ = new DefaultGetFoldingOffset();\r
 159         }\r
 160         m_isLatin1Linear_ = (m_options_ &\r
 161                              HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;\r
 162         m_dataOffset_     = input.readInt();\r
 163         m_dataLength_     = input.readInt();\r
 164         unserialize(inputStream);\r
 165     }\r
 166     \r
 167     /**\r
 168     * Trie constructor\r
 169     * @param index array to be used for index\r
 170     * @param options used by the trie\r
 171     * @param dataManipulate object containing the information to parse the \r
 172     *                       trie data\r
 173     */\r
 174     protected Trie(char index[], int options, DataManipulate dataManipulate)\r
 175     {\r
 176         m_options_ = options;\r
 177         if(dataManipulate != null) {\r
 178             m_dataManipulate_ = dataManipulate;\r
 179         } else {\r
 180             m_dataManipulate_ = new DefaultGetFoldingOffset();\r
 181         }\r
 182         m_isLatin1Linear_ = (m_options_ &\r
 183                              HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_) != 0;\r
 184         m_index_ = index;\r
 185         m_dataOffset_ = m_index_.length;\r
 186     }\r
 187 \r
 188 \r
 189     // protected data members ------------------------------------------\r
 190 \r
 191     /**\r
 192     * Lead surrogate code points' index displacement in the index array.\r
 193     * 0x10000-0xd800=0x2800\r
 194     * 0x2800 >> INDEX_STAGE_1_SHIFT_\r
 195     */\r
 196     protected static final int LEAD_INDEX_OFFSET_ = 0x2800 >> 5;\r
 197     /**\r
 198     * Shift size for shifting right the input index. 1..9\r
 199     */\r
 200     protected static final int INDEX_STAGE_1_SHIFT_ = 5;\r
 201     /**\r
 202     * Shift size for shifting left the index array values.\r
 203     * Increases possible data size with 16-bit index values at the cost\r
 204     * of compactability.\r
 205     * This requires blocks of stage 2 data to be aligned by\r
 206     * DATA_GRANULARITY.\r
 207     * 0..INDEX_STAGE_1_SHIFT\r
 208     */\r
 209     protected static final int INDEX_STAGE_2_SHIFT_ = 2;\r
 210     /**\r
 211      * Number of data values in a stage 2 (data array) block.\r
 212      */\r
 213     protected static final int DATA_BLOCK_LENGTH=1<<INDEX_STAGE_1_SHIFT_;\r
 214     /**\r
 215     * Mask for getting the lower bits from the input index.\r
 216     * DATA_BLOCK_LENGTH - 1.\r
 217     */\r
 218     protected static final int INDEX_STAGE_3_MASK_ = DATA_BLOCK_LENGTH - 1;\r
 219     /** Number of bits of a trail surrogate that are used in index table lookups. */\r
 220     protected static final int SURROGATE_BLOCK_BITS=10-INDEX_STAGE_1_SHIFT_;\r
 221     /**\r
 222      * Number of index (stage 1) entries per lead surrogate.\r
 223      * Same as number of index entries for 1024 trail surrogates,\r
 224      * ==0x400>>INDEX_STAGE_1_SHIFT_\r
 225      */\r
 226     protected static final int SURROGATE_BLOCK_COUNT=(1<<SURROGATE_BLOCK_BITS);\r
 227     /** Length of the BMP portion of the index (stage 1) array. */\r
 228     protected static final int BMP_INDEX_LENGTH=0x10000>>INDEX_STAGE_1_SHIFT_;\r
 229     /**\r
 230     * Surrogate mask to use when shifting offset to retrieve supplementary\r
 231     * values\r
 232     */\r
 233     protected static final int SURROGATE_MASK_ = 0x3FF;                                              \r
 234     /**\r
 235     * Index or UTF16 characters\r
 236     */\r
 237     protected char m_index_[];\r
 238     /**\r
 239     * Internal TrieValue which handles the parsing of the data value.\r
 240     * This class is to be implemented by the user\r
 241     */\r
 242     protected DataManipulate m_dataManipulate_;\r
 243     /**\r
 244     * Start index of the data portion of the trie. CharTrie combines \r
 245     * index and data into a char array, so this is used to indicate the \r
 246     * initial offset to the data portion.\r
 247     * Note this index always points to the initial value.\r
 248     */\r
 249     protected int m_dataOffset_;\r
 250     /**\r
 251     * Length of the data array \r
 252     */\r
 253     protected int m_dataLength_;\r
 254      \r
 255     // protected methods -----------------------------------------------\r
 256 \r
 257     /**\r
 258     * Gets the offset to the data which the surrogate pair points to.\r
 259     * @param lead lead surrogate\r
 260     * @param trail trailing surrogate\r
 261     * @return offset to data\r
 262     */\r
 263     protected abstract int getSurrogateOffset(char lead, char trail);\r
 264     \r
 265     /**\r
 266     * Gets the value at the argument index\r
 267     * @param index value at index will be retrieved\r
 268     * @return 32 bit value \r
 269     */\r
 270     protected abstract int getValue(int index);\r
 271 \r
 272     /**\r
 273     * Gets the default initial value\r
 274     * @return 32 bit value \r
 275     */\r
 276     protected abstract int getInitialValue();\r
 277     \r
 278     /**\r
 279     * Gets the offset to the data which the index ch after variable offset\r
 280     * points to.\r
 281     * Note for locating a non-supplementary character data offset, calling\r
 282     * <p>\r
 283     * getRawOffset(0, ch);\r
 284     * </p>\r
 285     * will do. Otherwise if it is a supplementary character formed by\r
 286     * surrogates lead and trail. Then we would have to call getRawOffset()\r
 287     * with getFoldingIndexOffset(). See getSurrogateOffset().\r
 288     * @param offset index offset which ch is to start from\r
 289     * @param ch index to be used after offset\r
 290     * @return offset to the data\r
 291     */\r
 292     protected final int getRawOffset(int offset, char ch)\r
 293     {\r
 294         return (m_index_[offset + (ch >> INDEX_STAGE_1_SHIFT_)] \r
 295                 << INDEX_STAGE_2_SHIFT_) \r
 296                 + (ch & INDEX_STAGE_3_MASK_);\r
 297     }\r
 298     \r
 299     /**\r
 300     * Gets the offset to data which the BMP character points to\r
 301     * Treats a lead surrogate as a normal code point.\r
 302     * @param ch BMP character\r
 303     * @return offset to data\r
 304     */\r
 305     protected final int getBMPOffset(char ch)\r
 306     {\r
 307         return (ch >= UTF16.LEAD_SURROGATE_MIN_VALUE \r
 308                 && ch <= UTF16.LEAD_SURROGATE_MAX_VALUE) \r
 309                 ? getRawOffset(LEAD_INDEX_OFFSET_, ch)\r
 310                 : getRawOffset(0, ch); \r
 311                 // using a getRawOffset(ch) makes no diff\r
 312     }\r
 313 \r
 314     /**\r
 315     * Gets the offset to the data which this lead surrogate character points\r
 316     * to.\r
 317     * Data at the returned offset may contain folding offset information for\r
 318     * the next trailing surrogate character.\r
 319     * @param ch lead surrogate character\r
 320     * @return offset to data\r
 321     */\r
 322     protected final int getLeadOffset(char ch)\r
 323     {\r
 324        return getRawOffset(0, ch);\r
 325     }\r
 326 \r
 327     /**\r
 328     * Internal trie getter from a code point.\r
 329     * Could be faster(?) but longer with\r
 330     *   if((c32)<=0xd7ff) { (result)=_TRIE_GET_RAW(trie, data, 0, c32); }\r
 331     * Gets the offset to data which the codepoint points to\r
 332     * @param ch codepoint\r
 333     * @return offset to data\r
 334     */\r
 335     protected final int getCodePointOffset(int ch)\r
 336     {\r
 337         // if ((ch >> 16) == 0) slower\r
 338         if (ch < 0) {\r
 339             return -1;\r
 340         } else if (ch < UTF16.LEAD_SURROGATE_MIN_VALUE) {\r
 341             // fastpath for the part of the BMP below surrogates (D800) where getRawOffset() works\r
 342             return getRawOffset(0, (char)ch);\r
 343         } else if (ch < UTF16.SUPPLEMENTARY_MIN_VALUE) {\r
 344             // BMP codepoint\r
 345             return getBMPOffset((char)ch); \r
 346         } else if (ch <= UCharacter.MAX_VALUE) {\r
 347             // look at the construction of supplementary characters\r
 348             // trail forms the ends of it.\r
 349             return getSurrogateOffset(UTF16.getLeadSurrogate(ch), \r
 350                                       (char)(ch & SURROGATE_MASK_));\r
 351         } else {\r
 352             // return -1 if there is an error, in this case we return \r
 353             return -1;\r
 354         }\r
 355     }\r
 356 \r
 357     /**\r
 358     * <p>Parses the inputstream and creates the trie index with it.</p>\r
 359     * <p>This is overwritten by the child classes.\r
 360     * @param inputStream input stream containing the trie information\r
 361     * @exception IOException thrown when data reading fails.\r
 362     */\r
 363     protected void unserialize(InputStream inputStream) throws IOException\r
 364     {\r
 365         //indexLength is a multiple of 1024 >> INDEX_STAGE_2_SHIFT_\r
 366         m_index_              = new char[m_dataOffset_];\r
 367         DataInputStream input = new DataInputStream(inputStream);\r
 368         for (int i = 0; i < m_dataOffset_; i ++) {\r
 369              m_index_[i] = input.readChar();\r
 370         }\r
 371     }\r
 372 \r
 373     /**\r
 374     * Determines if this is a 32 bit trie\r
 375     * @return true if options specifies this is a 32 bit trie\r
 376     */\r
 377     protected final boolean isIntTrie()\r
 378     {\r
 379         return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) != 0;\r
 380     }\r
 381 \r
 382     /**\r
 383     * Determines if this is a 16 bit trie\r
 384     * @return true if this is a 16 bit trie\r
 385     */\r
 386     protected final boolean isCharTrie()\r
 387     {\r
 388         return (m_options_ & HEADER_OPTIONS_DATA_IS_32_BIT_) == 0;\r
 389     }\r
 390 \r
 391     // private data members --------------------------------------------\r
 392 \r
 393     //  struct UTrieHeader {\r
 394     //      int32_t   signature;\r
 395     //      int32_t   options  (a bit field)\r
 396     //      int32_t   indexLength\r
 397     //      int32_t   dataLength\r
 398 \r
 399     /**\r
 400     * Size of Trie header in bytes\r
 401     */\r
 402     protected static final int HEADER_LENGTH_ = 4 * 4;\r
 403     /**\r
 404     * Latin 1 option mask\r
 405     */\r
 406     protected static final int HEADER_OPTIONS_LATIN1_IS_LINEAR_MASK_ = 0x200;\r
 407     /**\r
 408     * Constant number to authenticate the byte block\r
 409     */\r
 410     protected static final int HEADER_SIGNATURE_ = 0x54726965;\r
 411     /**\r
 412     * Header option formatting\r
 413     */\r
 414     private static final int HEADER_OPTIONS_SHIFT_MASK_ = 0xF;\r
 415     protected static final int HEADER_OPTIONS_INDEX_SHIFT_ = 4;\r
 416     protected static final int HEADER_OPTIONS_DATA_IS_32_BIT_ = 0x100;\r
 417     \r
 418     /**\r
 419     * Flag indicator for Latin quick access data block\r
 420     */\r
 421     private boolean m_isLatin1Linear_;\r
 422     \r
 423     /**\r
 424     * <p>Trie options field.</p>\r
 425     * <p>options bit field:<br>\r
 426     * 9  1 = Latin-1 data is stored linearly at data + DATA_BLOCK_LENGTH<br>\r
 427     * 8  0 = 16-bit data, 1=32-bit data<br>\r
 428     * 7..4  INDEX_STAGE_1_SHIFT   // 0..INDEX_STAGE_2_SHIFT<br>\r
 429     * 3..0  INDEX_STAGE_2_SHIFT   // 1..9<br>\r
 430     */\r
 431     private int m_options_;\r
 432     \r
 433     // private methods ---------------------------------------------------\r
 434     \r
 435     /**\r
 436     * Authenticates raw data header.\r
 437     * Checking the header information, signature and options.\r
 438     * @param signature This contains the options and type of a Trie\r
 439     * @return true if the header is authenticated valid\r
 440     */\r
 441     private final boolean checkHeader(int signature)\r
 442     {\r
 443         // check the signature\r
 444         // Trie in big-endian US-ASCII (0x54726965).\r
 445         // Magic number to authenticate the data.\r
 446         if (signature != HEADER_SIGNATURE_) {\r
 447             return false;\r
 448         }\r
 449 \r
 450         if ((m_options_ & HEADER_OPTIONS_SHIFT_MASK_) != \r
 451                                                     INDEX_STAGE_1_SHIFT_ ||\r
 452             ((m_options_ >> HEADER_OPTIONS_INDEX_SHIFT_) &\r
 453                                                 HEADER_OPTIONS_SHIFT_MASK_)\r
 454                                                  != INDEX_STAGE_2_SHIFT_) {\r
 455             return false;\r
 456         }\r
 457         return true;\r
 458     }\r
 459 }\r