jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/impl/TrieBuilder.java

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 1996-2010, International Business Machines Corporation and   *
   4 * others. All Rights Reserved.                                               *
   5 ******************************************************************************
   6 */
   7
   8 package com.ibm.icu.impl;
   9
  10 import java.util.Arrays;
  11
  12 import com.ibm.icu.lang.UCharacter;
  13
  14 /**
  15  * Builder class to manipulate and generate a trie.
  16  * This is useful for ICU data in primitive types.
  17  * Provides a compact way to store information that is indexed by Unicode
  18  * values, such as character properties, types, keyboard values, etc. This is
  19  * very useful when you have a block of Unicode data that contains significant
  20  * values while the rest of the Unicode data is unused in the application or
  21  * when you have a lot of redundance, such as where all 21,000 Han ideographs
  22  * have the same value.  However, lookup is much faster than a hash table.
  23  * A trie of any primitive data type serves two purposes:
  24  * <UL type = round>
  25  *     <LI>Fast access of the indexed values.
  26  *     <LI>Smaller memory footprint.
  27  * </UL>
  28  * This is a direct port from the ICU4C version
  29  * @author             Syn Wee Quek
  30  */
  31 public class TrieBuilder
  32 {
  33     // public data member ----------------------------------------------
  34
  35     /**
  36      * Number of data values in a stage 2 (data array) block. 2, 4, 8, ..,
  37      * 0x200
  38      */
  39     public static final int DATA_BLOCK_LENGTH = 1 << Trie.INDEX_STAGE_1_SHIFT_;
  40
  41     // public class declaration ----------------------------------------
  42
  43     /**
  44      * Character data in com.ibm.impl.Trie have different user-specified format
  45      * for different purposes.
  46      * This interface specifies methods to be implemented in order for
  47      * com.ibm.impl.Trie, to surrogate offset information encapsulated within
  48      * the data.
  49      */
  50     public static interface DataManipulate
  51     {
  52         /**
  53          * Build-time trie callback function, used with serialize().
  54          * This function calculates a lead surrogate's value including a
  55          * folding offset from the 1024 supplementary code points
  56          * [start..start+1024[ .
  57          * It is U+10000 <= start <= U+10fc00 and (start&0x3ff)==0.
  58          * The folding offset is provided by the caller.
  59          * It is offset=UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT
  60          * with n=0..1023.
  61          * Instead of the offset itself, n can be stored in 10 bits - or fewer
  62          * if it can be assumed that few lead surrogates have associated data.
  63          * The returned value must be
  64          *  - not zero if and only if there is relevant data for the
  65          *                        corresponding 1024 supplementary code points
  66          *  - such that UTrie.getFoldingOffset(UNewTrieGetFoldedValue(...,
  67          *                                                    offset))==offset
  68          * @return a folded value, or 0 if there is no relevant data for the
  69          *         lead surrogate.
  70          */
  71         public int getFoldedValue(int start, int offset);
  72     }
  73
  74     // public methods ----------------------------------------------------
  75
  76     /**
  77      * Checks if the character belongs to a zero block in the trie
  78      * @param ch codepoint which data is to be retrieved
  79      * @return true if ch is in the zero block
  80      */
  81     public boolean isInZeroBlock(int ch)
  82     {
  83         // valid, uncompacted trie and valid c?
  84         if (m_isCompacted_ || ch > UCharacter.MAX_VALUE
  85             || ch < UCharacter.MIN_VALUE) {
  86             return true;
  87         }
  88
  89         return m_index_[ch >> SHIFT_] == 0;
  90     }
  91
  92     // package private method -----------------------------------------------
  93
  94     // protected data member -----------------------------------------------
  95
  96     /**
  97      * Index values at build-time are 32 bits wide for easier processing.
  98      * Bit 31 is set if the data block is used by multiple index values
  99      * (from setRange()).
 100      */
 101     protected int m_index_[];
 102     protected int m_indexLength_;
 103     protected int m_dataCapacity_;
 104     protected int m_dataLength_;
 105     protected boolean m_isLatin1Linear_;
 106     protected boolean m_isCompacted_;
 107     /**
 108      * Map of adjusted indexes, used in utrie_compact().
 109      * Maps from original indexes to new ones.
 110      */
 111     protected int m_map_[];
 112
 113     /**
 114      * Shift size for shifting right the input index. 1..9
 115      */
 116     protected static final int SHIFT_ = Trie.INDEX_STAGE_1_SHIFT_;
 117     /**
 118      * Length of the index (stage 1) array before folding.
 119      * Maximum number of Unicode code points (0x110000) shifted right by
 120      * SHIFT.
 121      */
 122     protected static final int MAX_INDEX_LENGTH_ = (0x110000 >> SHIFT_);
 123     /**
 124      * Length of the BMP portion of the index (stage 1) array.
 125      */
 126     protected static final int BMP_INDEX_LENGTH_ = 0x10000 >> SHIFT_;
 127     /**
 128      * Number of index (stage 1) entries per lead surrogate.
 129      * Same as number of indexe entries for 1024 trail surrogates,
 130      * ==0x400>>UTRIE_SHIFT
 131      * 10 - SHIFT == Number of bits of a trail surrogate that are used in
 132      *               index table lookups.
 133      */
 134     protected static final int SURROGATE_BLOCK_COUNT_ = 1 << (10 - SHIFT_);
 135     /**
 136      * Mask for getting the lower bits from the input index.
 137      * DATA_BLOCK_LENGTH - 1.
 138      */
 139     protected static final int MASK_ = Trie.INDEX_STAGE_3_MASK_;
 140     /**
 141      * Shift size for shifting left the index array values.
 142      * Increases possible data size with 16-bit index values at the cost
 143      * of compactability.
 144      * This requires blocks of stage 2 data to be aligned by UTRIE_DATA_GRANULARITY.
 145      * 0..UTRIE_SHIFT
 146      */
 147     protected static final int INDEX_SHIFT_ = Trie.INDEX_STAGE_2_SHIFT_;
 148     /**
 149      * Maximum length of the runtime data (stage 2) array.
 150      * Limited by 16-bit index values that are left-shifted by INDEX_SHIFT_.
 151      */
 152     protected static final int MAX_DATA_LENGTH_ = (0x10000 << INDEX_SHIFT_);
 153     /**
 154      * Shifting to position the index value in options
 155      */
 156     protected static final int OPTIONS_INDEX_SHIFT_ = 4;
 157     /**
 158      * If set, then the data (stage 2) array is 32 bits wide.
 159      */
 160     protected static final int OPTIONS_DATA_IS_32_BIT_ = 0x100;
 161     /**
 162      * If set, then Latin-1 data (for U+0000..U+00ff) is stored in the data
 163      * (stage 2) array as a simple, linear array at data + DATA_BLOCK_LENGTH.
 164      */
 165     protected static final int OPTIONS_LATIN1_IS_LINEAR_ = 0x200;
 166     /**
 167      * The alignment size of a stage 2 data block. Also the granularity for
 168      * compaction.
 169      */
 170     protected static final int DATA_GRANULARITY_ = 1 << INDEX_SHIFT_;
 171
 172     // protected constructor ----------------------------------------------
 173
 174     protected TrieBuilder()
 175     {
 176         m_index_ = new int[MAX_INDEX_LENGTH_];
 177         m_map_ = new int[MAX_BUILD_TIME_DATA_LENGTH_ >> SHIFT_];
 178         m_isLatin1Linear_ = false;
 179         m_isCompacted_ = false;
 180         m_indexLength_ = MAX_INDEX_LENGTH_;
 181     }
 182
 183     protected TrieBuilder(TrieBuilder table)
 184     {
 185         m_index_ = new int[MAX_INDEX_LENGTH_];
 186         m_indexLength_ = table.m_indexLength_;
 187         System.arraycopy(table.m_index_, 0, m_index_, 0, m_indexLength_);
 188         m_dataCapacity_ = table.m_dataCapacity_;
 189         m_dataLength_ = table.m_dataLength_;
 190         m_map_ = new int[table.m_map_.length];
 191         System.arraycopy(table.m_map_, 0, m_map_, 0, m_map_.length);
 192         m_isLatin1Linear_ = table.m_isLatin1Linear_;
 193         m_isCompacted_ = table.m_isCompacted_;
 194     }
 195
 196     // protected functions ------------------------------------------------
 197
 198     /**
 199      * Compare two sections of an array for equality.
 200      */
 201     protected static final boolean equal_int(int[] array, int start1, int start2, int length) {
 202         while(length>0 && array[start1]==array[start2]) {
 203             ++start1;
 204             ++start2;
 205             --length;
 206         }
 207         return length==0;
 208     }
 209
 210     /**
 211      * Set a value in the trie index map to indicate which data block
 212      * is referenced and which one is not.
 213      * utrie_compact() will remove data blocks that are not used at all.
 214      * Set
 215      * - 0 if it is used
 216      * - -1 if it is not used
 217      */
 218     protected void findUnusedBlocks()
 219     {
 220         // fill the entire map with "not used"
 221         Arrays.fill(m_map_, 0xff);
 222
 223         // mark each block that _is_ used with 0
 224         for (int i = 0; i < m_indexLength_; ++ i) {
 225             m_map_[Math.abs(m_index_[i]) >> SHIFT_] = 0;
 226         }
 227
 228         // never move the all-initial-value block 0
 229         m_map_[0] = 0;
 230     }
 231
 232     /**
 233      * Finds the same index block as the otherBlock
 234      * @param index array
 235      * @param indexLength size of index
 236      * @param otherBlock
 237      * @return same index block
 238      */
 239     protected static final int findSameIndexBlock(int index[], int indexLength,
 240                                                   int otherBlock)
 241     {
 242         for (int block = BMP_INDEX_LENGTH_; block < indexLength;
 243              block += SURROGATE_BLOCK_COUNT_) {
 244             if(equal_int(index, block, otherBlock, SURROGATE_BLOCK_COUNT_)) {
 245                 return block;
 246             }
 247         }
 248         return indexLength;
 249     }
 250
 251     // private data member ------------------------------------------------
 252
 253     /**
 254      * Maximum length of the build-time data (stage 2) array.
 255      * The maximum length is 0x110000 + DATA_BLOCK_LENGTH + 0x400.
 256      * (Number of Unicode code points + one all-initial-value block +
 257      *  possible duplicate entries for 1024 lead surrogates.)
 258      */
 259     private static final int MAX_BUILD_TIME_DATA_LENGTH_ =
 260         0x110000 + DATA_BLOCK_LENGTH + 0x400;
 261 }