jars/icu4j-4_8_1_1/main/classes/core/src/com/ibm/icu/impl/Trie2_16.java

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