TrieBuilder


1   /*
2   ******************************************************************************
3   * Copyright (C) 1996-2005, International Business Machines Corporation and   *
4   * others. All Rights Reserved.                                               *
5   ******************************************************************************
6   */
7   
8   package com.ibm.icu.impl;
9   
10  import com.ibm.icu.lang.UCharacter;
11  import java.util.Arrays  ;
12  
13  /**
14   * Builder class to manipulate and generate a trie.
15   * This is useful for ICU data in primitive types.
16   * Provides a compact way to store information that is indexed by Unicode 
17   * values, such as character properties, types, keyboard values, etc. This is 
18   * very useful when you have a block of Unicode data that contains significant 
19   * values while the rest of the Unicode data is unused in the application or 
20   * when you have a lot of redundance, such as where all 21,000 Han ideographs 
21   * have the same value.  However, lookup is much faster than a hash table.
22   * A trie of any primitive data type serves two purposes:
23   * <UL type = round>
24   *     <LI>Fast access of the indexed values.
25   *     <LI>Smaller memory footprint.
26   * </UL>
27   * This is a direct port from the ICU4C version
28   * @author             Syn Wee Quek
29   */
30  public class TrieBuilder
31  {
32      // public data member ----------------------------------------------
33          
34      /** 
35       * Number of data values in a stage 2 (data array) block. 2, 4, 8, .., 
36       * 0x200 
37       */
38      public static final int DATA_BLOCK_LENGTH = 1 << Trie.INDEX_STAGE_1_SHIFT_;
39      
40      // public class declaration ----------------------------------------
41      
42      /**
43       * Character data in com.ibm.impl.Trie have different user-specified format
44       * for different purposes.
45       * This interface specifies methods to be implemented in order for
46       * com.ibm.impl.Trie, to surrogate offset information encapsulated within 
47       * the data.
48       * @draft 2.2
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 }
262
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags