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