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

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 2009-2010, International Business Machines Corporation and\r
   4  * others. All Rights Reserved.\r
   5  *******************************************************************************\r
   6  */\r
   7 package com.ibm.icu.impl;\r
   8 \r
   9 import java.io.DataOutputStream;\r
  10 import java.io.IOException;\r
  11 import java.io.InputStream;\r
  12 import java.io.OutputStream;\r
  13 \r
  14 /**\r
  15  * @author aheninger\r
  16  *\r
  17  * A read-only Trie2, holding 32 bit data values.\r
  18  * \r
  19  * A Trie2 is a highly optimized data structure for mapping from Unicode\r
  20  * code points (values ranging from 0 to 0x10ffff) to a 16 or 32 bit value.\r
  21  *\r
  22  * See class Trie2 for descriptions of the API for accessing the contents of a trie.\r
  23  * \r
  24  * The fundamental data access methods are declared final in this class, with\r
  25  * the intent that applications might gain a little extra performance, when compared\r
  26  * with calling the same methods via the abstract UTrie2 base class.\r
  27  */\r
  28 \r
  29 public class Trie2_32 extends Trie2 {\r
  30     \r
  31     /**\r
  32      * Internal constructor, not for general use.\r
  33      */\r
  34     Trie2_32() {\r
  35     }\r
  36     \r
  37     \r
  38     /**\r
  39      * Create a Trie2 from its serialized form.  Inverse of utrie2_serialize().\r
  40      * The serialized format is identical between ICU4C and ICU4J, so this function\r
  41      * will work with serialized Trie2s from either.\r
  42      * \r
  43      * The serialized Trie2 on the stream may be in either little or big endian byte order.\r
  44      * This allows using serialized Tries from ICU4C without needing to consider the\r
  45      * byte order of the system that created them.\r
  46      *\r
  47      * @param is an input stream to the serialized form of a UTrie2.  \r
  48      * @return An unserialized Trie_32, ready for use.\r
  49      * @throws IllegalArgumentException if the stream does not contain a serialized Trie2.\r
  50      * @throws IOException if a read error occurs on the InputStream.\r
  51      * @throws ClassCastException if the stream contains a serialized Trie2_16\r
  52      */\r
  53     public static Trie2_32  createFromSerialized(InputStream is) throws IOException {\r
  54         return (Trie2_32) Trie2.createFromSerialized(is);\r
  55     }\r
  56 \r
  57     /**\r
  58      * Get the value for a code point as stored in the Trie2.\r
  59      *\r
  60      * @param codePoint the code point\r
  61      * @return the value\r
  62      */\r
  63     @Override\r
  64     public final int get(int codePoint) {\r
  65         int value;\r
  66         int ix;\r
  67         \r
  68         if (codePoint >= 0) {\r
  69             if (codePoint < 0x0d800 || (codePoint > 0x0dbff && codePoint <= 0x0ffff)) {\r
  70                 // Ordinary BMP code point, excluding leading surrogates.\r
  71                 // BMP uses a single level lookup.  BMP index starts at offset 0 in the Trie2 index.\r
  72                 // 32 bit data is stored in the index array itself.\r
  73                 ix = index[codePoint >> UTRIE2_SHIFT_2];\r
  74                 ix = (ix << UTRIE2_INDEX_SHIFT) + (codePoint & UTRIE2_DATA_MASK);\r
  75                 value = data32[ix];\r
  76                 return value;\r
  77             } \r
  78             if (codePoint <= 0xffff) {\r
  79                 // Lead Surrogate Code Point.  A Separate index section is stored for\r
  80                 // lead surrogate code units and code points.\r
  81                 //   The main index has the code unit data.\r
  82                 //   For this function, we need the code point data.\r
  83                 // Note: this expression could be refactored for slightly improved efficiency, but\r
  84                 //       surrogate code points will be so rare in practice that it's not worth it.\r
  85                 ix = index[UTRIE2_LSCP_INDEX_2_OFFSET + ((codePoint - 0xd800) >> UTRIE2_SHIFT_2)];\r
  86                 ix = (ix << UTRIE2_INDEX_SHIFT) + (codePoint & UTRIE2_DATA_MASK);\r
  87                 value = data32[ix];\r
  88                 return value;\r
  89             }\r
  90             if (codePoint < highStart) {\r
  91                 // Supplemental code point, use two-level lookup.\r
  92                 ix = (UTRIE2_INDEX_1_OFFSET - UTRIE2_OMITTED_BMP_INDEX_1_LENGTH) + (codePoint >> UTRIE2_SHIFT_1);\r
  93                 ix = index[ix];\r
  94                 ix += (codePoint >> UTRIE2_SHIFT_2) & UTRIE2_INDEX_2_MASK;\r
  95                 ix = index[ix];\r
  96                 ix = (ix << UTRIE2_INDEX_SHIFT) + (codePoint & UTRIE2_DATA_MASK);\r
  97                 value = data32[ix];\r
  98                 return value;\r
  99             }\r
 100             if (codePoint <= 0x10ffff) {\r
 101                 value = data32[highValueIndex];\r
 102                 return value;\r
 103             }\r
 104         }\r
 105         \r
 106         // Fall through.  The code point is outside of the legal range of 0..0x10ffff.\r
 107         return errorValue;\r
 108     }\r
 109 \r
 110     \r
 111     /**\r
 112      * Get a Trie2 value for a UTF-16 code unit.\r
 113      * \r
 114      * This function returns the same value as get() if the input \r
 115      * character is outside of the lead surrogate range\r
 116      * \r
 117      * There are two values stored in a Trie2 for inputs in the lead\r
 118      * surrogate range.  This function returns the alternate value,\r
 119      * while Trie2.get() returns the main value.\r
 120      * \r
 121      * @param codeUnit a 16 bit code unit or lead surrogate value.\r
 122      * @return the value\r
 123      */\r
 124     @Override\r
 125     public int getFromU16SingleLead(char codeUnit){\r
 126         int value;\r
 127         int ix;\r
 128         \r
 129         ix = index[codeUnit >> UTRIE2_SHIFT_2];\r
 130         ix = (ix << UTRIE2_INDEX_SHIFT) + (codeUnit & UTRIE2_DATA_MASK);\r
 131         value = data32[ix];\r
 132         return value;\r
 133 \r
 134     }\r
 135     \r
 136     /**\r
 137      * Serialize a Trie2_32 onto an OutputStream.\r
 138      * \r
 139      * A Trie2 can be serialized multiple times.\r
 140      * The serialized data is compatible with ICU4C UTrie2 serialization.\r
 141      * Trie2 serialization is unrelated to Java object serialization.\r
 142      *  \r
 143      * @param os the stream to which the serialized Trie2 data will be written.\r
 144      * @return the number of bytes written.\r
 145      * @throw IOException on an error writing to the OutputStream.\r
 146      */\r
 147     public int serialize(OutputStream os) throws IOException {\r
 148         DataOutputStream dos = new DataOutputStream(os);\r
 149         int  bytesWritten = 0;\r
 150         \r
 151         bytesWritten += serializeHeader(dos);        \r
 152         for (int i=0; i<dataLength; i++) {\r
 153             dos.writeInt(data32[i]);\r
 154         }\r
 155         bytesWritten += dataLength*4;\r
 156         return bytesWritten;\r
 157     }\r
 158 \r
 159     /**\r
 160      * @return the number of bytes of the serialized trie\r
 161      */\r
 162     public int getSerializedLength() {\r
 163         return 16+header.indexLength*2+dataLength*4;\r
 164     }\r
 165 \r
 166     /**\r
 167      * Given a starting code point, find the last in a range of code points,\r
 168      * all with the same value.\r
 169      * \r
 170      * This function is part of the implementation of iterating over the\r
 171      * Trie2's contents.\r
 172      * @param startingCP The code point at which to begin looking.\r
 173      * @return The last code point with the same value as the starting code point.\r
 174      */\r
 175     @Override\r
 176     int rangeEnd(int startingCP, int limit, int value) {\r
 177         int   cp = startingCP;\r
 178         int   block = 0;\r
 179         int   index2Block = 0;\r
 180         \r
 181         // Loop runs once for each of\r
 182         //   - a partial data block\r
 183         //   - a reference to the null (default) data block.\r
 184         //   - a reference to the index2 null block\r
 185         \r
 186       outerLoop:\r
 187         for (;;) {\r
 188             if (cp >= limit) {\r
 189                 break;\r
 190             }\r
 191             if (cp < 0x0d800 || (cp > 0x0dbff && cp <= 0x0ffff)) {\r
 192                 // Ordinary BMP code point, excluding leading surrogates.\r
 193                 // BMP uses a single level lookup.  BMP index starts at offset 0 in the Trie2 index.\r
 194                 // 16 bit data is stored in the index array itself.\r
 195                 index2Block = 0;\r
 196                 block       = index[cp >> UTRIE2_SHIFT_2] << UTRIE2_INDEX_SHIFT;\r
 197             } else if (cp < 0xffff) {\r
 198                 // Lead Surrogate Code Point, 0xd800 <= cp < 0xdc00\r
 199                 index2Block = UTRIE2_LSCP_INDEX_2_OFFSET;\r
 200                 block       = index[index2Block + ((cp - 0xd800) >> UTRIE2_SHIFT_2)] << UTRIE2_INDEX_SHIFT;\r
 201             } else if (cp < highStart) {\r
 202                 // Supplemental code point, use two-level lookup.\r
 203                 int ix = (UTRIE2_INDEX_1_OFFSET - UTRIE2_OMITTED_BMP_INDEX_1_LENGTH) + (cp >> UTRIE2_SHIFT_1);\r
 204                 index2Block = index[ix];\r
 205                 block = index[index2Block + ((cp >> UTRIE2_SHIFT_2) & UTRIE2_INDEX_2_MASK)] << UTRIE2_INDEX_SHIFT;\r
 206             } else  {\r
 207                 // Code point above highStart.\r
 208                 if (value == data32[highValueIndex]) {\r
 209                     cp = limit;\r
 210                 }\r
 211                 break;\r
 212             } \r
 213             \r
 214             if (index2Block == index2NullOffset) {\r
 215                 if (value != initialValue) {\r
 216                     break;\r
 217                 }\r
 218                 cp += UTRIE2_CP_PER_INDEX_1_ENTRY;\r
 219             } else if (block == dataNullOffset) {\r
 220                 // The block at dataNullOffset has all values == initialValue.\r
 221                 // Because Trie2 iteration always proceeds in ascending order, we will always\r
 222                 //   encounter a null block at its beginning, and can skip over\r
 223                 //   a number of code points equal to the length of the block.\r
 224                 if (value != initialValue) {\r
 225                     break;\r
 226                 }\r
 227                 cp += UTRIE2_DATA_BLOCK_LENGTH;\r
 228             } else {\r
 229                 // Current position refers to an ordinary data block.\r
 230                 // Walk over the data entries, checking the values.\r
 231                 int startIx = block + (cp & UTRIE2_DATA_MASK);\r
 232                 int limitIx = block + UTRIE2_DATA_BLOCK_LENGTH;\r
 233                 for (int ix = startIx; ix<limitIx; ix++) {\r
 234                     if (data32[ix] != value) {\r
 235                         // We came to an entry with a different value.\r
 236                         //   We are done.\r
 237                         cp += (ix - startIx);\r
 238                         break outerLoop;\r
 239                     }\r
 240                 }\r
 241                 // The ordinary data block contained our value until its end.\r
 242                 //  Advance the current code point, and continue the outer loop.\r
 243                 cp += limitIx - startIx;\r
 244             }\r
 245         }\r
 246         if (cp > limit) {\r
 247             cp = limit;\r
 248         }\r
 249     \r
 250         return cp - 1;\r
 251     }\r
 252 \r
 253 }\r
 254 \r