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