CompactCharArray


1   /*
2    *******************************************************************************
3    * Copyright (C) 1996-2006, International Business Machines Corporation and    *
4    * others. All Rights Reserved.                                                *
5    *******************************************************************************
6    */
7   
8   package com.ibm.icu.util;
9   
10  import com.ibm.icu.impl.Utility;
11  
12  /**
13   * class CompactATypeArray : use only on primitive data types
14   * Provides a compact way to store information that is indexed by Unicode
15   * values, such as character properties, types, keyboard values, etc.This
16   * is very useful when you have a block of Unicode data that contains
17   * significant values while the rest of the Unicode data is unused in the
18   * application or when you have a lot of redundance, such as where all 21,000
19   * Han ideographs have the same value.  However, lookup is much faster than a
20   * hash table.
21   * A compact array of any primitive data type serves two purposes:
22   * <UL type = round>
23   *     <LI>Fast access of the indexed values.
24   *     <LI>Smaller memory footprint.
25   * </UL>
26   * A compact array is composed of a index array and value array.  The index
27   * array contains the indicies of Unicode characters to the value array.
28   * @see                CompactByteArray
29   * @author             Helena Shih
30   * @internal
31   * @deprecated This API is ICU internal only.
32   */
33  public final class CompactCharArray implements Cloneable   {
34  
35      /**
36       * The total number of Unicode characters.
37       * @internal
38       * @deprecated This API is ICU internal only.
39       */
40      public static  final int UNICODECOUNT = 65536;
41  
42      /**
43       * Default constructor for CompactCharArray, the default value of the
44       * compact array is 0.
45       * @internal
46       * @deprecated This API is ICU internal only.
47       */
48      public CompactCharArray()
49      {
50          this((char)0);
51      }
52  
53      /**
54       * Constructor for CompactCharArray.
55       * @param defaultValue the default value of the compact array.
56       * @internal
57       * @deprecated This API is ICU internal only.
58       */
59      public CompactCharArray(char defaultValue)
60      {
61          int i;
62          values = new char[UNICODECOUNT];
63          indices = new char[INDEXCOUNT];
64          hashes = new int[INDEXCOUNT];
65          for (i = 0; i < UNICODECOUNT; ++i) {
66              values[i] = defaultValue;
67          }
68          for (i = 0; i < INDEXCOUNT; ++i) {
69              indices[i] = (char)(i<<BLOCKSHIFT);
70              hashes[i] = 0;
71          }
72          isCompact = false;
73  
74          this.defaultValue = defaultValue;
75      }
76  
77      /**
78       * Constructor for CompactCharArray.
79       * @param indexArray the indicies of the compact array.
80       * @param newValues the values of the compact array.
81       * @exception IllegalArgumentException If the index is out of range.
82       * @internal
83       * @deprecated This API is ICU internal only.
84       */
85      public CompactCharArray(char indexArray[],
86                               char newValues[])
87      {
88          int i;
89          if (indexArray.length != INDEXCOUNT)
90              throw new IllegalArgumentException  ("Index out of bounds.");
91          for (i = 0; i < INDEXCOUNT; ++i) {
92              char index = indexArray[i];
93              if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
94                  throw new IllegalArgumentException  ("Index out of bounds.");
95          }
96          indices = indexArray;
97          values = newValues;
98          isCompact = true;
99      }
100 
101     /**
102      * Constructor for CompactCharArray.
103      *
104      * @param indexArray the RLE-encoded indicies of the compact array.
105      * @param valueArray the RLE-encoded values of the compact array.
106      *
107      * @throws IllegalArgumentException if the index or value array is
108      *          the wrong size.
109      * @internal
110      * @deprecated This API is ICU internal only.
111      */
112     public CompactCharArray(String   indexArray,
113                 String   valueArray)
114     {
115         this( Utility.RLEStringToCharArray(indexArray),
116               Utility.RLEStringToCharArray(valueArray));
117     }
118 
119     /**
120      * Get the mapped value of a Unicode character.
121      * @param index the character to get the mapped value with
122      * @return the mapped value of the given character
123      * @internal
124      * @deprecated This API is ICU internal only.
125      */
126     public char elementAt(char index)
127     {
128     int ix = (indices[index >> BLOCKSHIFT] & 0xFFFF)
129         + (index & BLOCKMASK);
130     return ix >= values.length ? defaultValue : values[ix];
131     }
132 
133     /**
134      * Set a new value for a Unicode character.
135      * Set automatically expands the array if it is compacted.
136      * @param index the character to set the mapped value with
137      * @param value the new mapped value
138      * @internal
139      * @deprecated This API is ICU internal only.
140      */
141     public void setElementAt(char index, char value)
142     {
143         if (isCompact)
144             expand();
145          values[(int)index] = value;
146         touchBlock(index >> BLOCKSHIFT, value);
147     }
148 
149     /**
150      * Set new values for a range of Unicode character.
151      *
152      * @param start the starting offset of the range
153      * @param end the ending offset of the range
154      * @param value the new mapped value
155      * @internal
156      * @deprecated This API is ICU internal only.
157      */
158     public void setElementAt(char start, char end, char value)
159     {
160         int i;
161         if (isCompact) {
162             expand();
163         }
164         for (i = start; i <= end; ++i) {
165             values[i] = value;
166             touchBlock(i >> BLOCKSHIFT, value);
167         }
168     }
169     /**
170      * Compact the array
171      * @internal
172      * @deprecated This API is ICU internal only.
173      */
174     public void compact() {
175         compact(true);
176     }
177 
178     /**
179      * Compact the array.
180      * @internal
181      * @deprecated This API is ICU internal only.
182      */
183     public void compact(boolean exhaustive)
184     {
185         if (!isCompact) {
186             int iBlockStart = 0;
187             char iUntouched = 0xFFFF;
188             int newSize = 0;
189 
190             char[] target = exhaustive ? new char[UNICODECOUNT] : values;
191 
192             for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
193                 indices[i] = 0xFFFF;
194                 boolean touched = blockTouched(i);
195                 if (!touched && iUntouched != 0xFFFF) {
196                     // If no values in this block were set, we can just set its
197                     // index to be the same as some other block with no values
198                     // set, assuming we've seen one yet.
199                     indices[i] = iUntouched;
200                 } else {
201                     int jBlockStart = 0;
202                     // See if we can find a previously compacted block that's identical
203                     for (int j = 0; j < i; ++j, jBlockStart += BLOCKCOUNT) {
204                         if (hashes[i] == hashes[j] &&
205                                 arrayRegionMatches(values, iBlockStart,
206                                                    values, jBlockStart, BLOCKCOUNT)) {
207                             indices[i] = indices[j];
208                         }
209                     }
210                     if (indices[i] == 0xFFFF) {
211                         int dest;   // Where to copy
212                         if (exhaustive) {
213                             // See if we can find some overlap with another block
214                             dest = FindOverlappingPosition(iBlockStart, target,
215                                                             newSize);
216                         } else {
217                             // Just copy to the end; it's quicker
218                             dest = newSize;
219                         }
220                         int limit = dest + BLOCKCOUNT;
221                         if (limit > newSize) {
222                             for (int j = newSize; j < limit; ++j) {
223                                 target[j] = values[iBlockStart + j - dest];
224                             }
225                             newSize = limit;
226                         }
227                         indices[i] = (char)dest;
228                         if (!touched) {
229                             // If this is the first untouched block we've seen,
230                             // remember its index.
231                             iUntouched = (char)jBlockStart;
232                         }
233                     }
234                 }
235             }
236             // we are done compacting, so now make the array shorter
237             char[] result = new char[newSize];
238             System.arraycopy(target, 0, result, 0, newSize);
239             values = result;
240             isCompact = true;
241             hashes = null;
242         }
243     }
244 
245     private int FindOverlappingPosition(int start, char[] tempValues, int tempCount)
246     {
247         for (int i = 0; i < tempCount; i += 1) {
248             int currentCount = BLOCKCOUNT;
249             if (i + BLOCKCOUNT > tempCount) {
250                 currentCount = tempCount - i;
251             }
252             if (arrayRegionMatches(values, start, tempValues, i, currentCount))
253                 return i;
254         }
255         return tempCount;
256     }
257 
258     /**
259      * Convenience utility to compare two arrays of doubles.
260      * @param len the length to compare.
261      * The start indices and start+len must be valid.
262      */
263     final static boolean arrayRegionMatches(char[] source, int sourceStart,
264                                             char[] target, int targetStart,
265                                             int len)
266     {
267         int sourceEnd = sourceStart + len;
268         int delta = targetStart - sourceStart;
269         for (int i = sourceStart; i < sourceEnd; i++) {
270             if (source[i] != target[i + delta])
271             return false;
272         }
273         return true;
274     }
275 
276     /**
277      * Remember that a specified block was "touched", i.e. had a value set.
278      * Untouched blocks can be skipped when compacting the array
279      */
280     private final void touchBlock(int i, int value) {
281         hashes[i] = (hashes[i] + (value<<1)) | 1;
282     }
283 
284     /**
285      * Query whether a specified block was "touched", i.e. had a value set.
286      * Untouched blocks can be skipped when compacting the array
287      */
288     private final boolean blockTouched(int i) {
289         return hashes[i] != 0;
290     }
291 
292     /**
293      * For internal use only.  Do not modify the result, the behavior of
294      * modified results are undefined.
295      * @internal
296      * @deprecated This API is ICU internal only.
297      */
298     public char[] getIndexArray()
299     {
300         return indices;
301     }
302 
303     /**
304      * For internal use only.  Do not modify the result, the behavior of
305      * modified results are undefined.
306      * @internal
307      * @deprecated This API is ICU internal only.
308      */
309     public char[] getValueArray()
310     {
311         return values;
312     }
313 
314     /**
315      * Overrides Cloneable
316      * @internal
317      * @deprecated This API is ICU internal only.
318      */
319     public Object   clone()
320     {
321         try {
322             CompactCharArray other = (CompactCharArray) super.clone();
323             other.values = (char[])values.clone();
324             other.indices = (char[])indices.clone();
325             if (hashes != null) other.hashes = (int[])hashes.clone();
326             return other;
327         } catch (CloneNotSupportedException   e) {
328             throw new IllegalStateException  ();
329         }
330     }
331 
332     /**
333      * Compares the equality of two compact array objects.
334      * @param obj the compact array object to be compared with this.
335      * @return true if the current compact array object is the same
336      * as the compact array object obj; false otherwise.
337      * @internal
338      * @deprecated This API is ICU internal only.
339      */
340     public boolean equals(Object   obj) {
341         if (obj == null) return false;
342         if (this == obj)                      // quick check
343             return true;
344         if (getClass() != obj.getClass())         // same class?
345             return false;
346         CompactCharArray other = (CompactCharArray) obj;
347         for (int i = 0; i < UNICODECOUNT; i++) {
348             // could be sped up later
349             if (elementAt((char)i) != other.elementAt((char)i))
350                 return false;
351         }
352         return true; // we made it through the guantlet.
353     }
354 
355     /**
356      * Generates the hash code for the compact array object
357      * @internal
358      * @deprecated This API is ICU internal only.
359      */
360     public int hashCode() {
361         int result = 0;
362         int increment = Math.min(3, values.length/16);
363         for (int i = 0; i < values.length; i+= increment) {
364             result = result * 37 + values[i];
365         }
366         return result;
367     }
368 
369 
370     // --------------------------------------------------------------
371     // private
372     // --------------------------------------------------------------
373 
374     /**
375      * Expanding takes the array back to a 65536 element array.
376      */
377     private void expand()
378     {
379         int i;
380         if (isCompact) {
381             char[] tempArray;
382             hashes = new int[INDEXCOUNT];
383             tempArray = new char[UNICODECOUNT];
384             for (i = 0; i < UNICODECOUNT; ++i) {
385                 tempArray[i] = elementAt((char)i);
386             }
387             for (i = 0; i < INDEXCOUNT; ++i) {
388                 indices[i] = (char)(i<<BLOCKSHIFT);
389             }
390             values = null;
391             values = tempArray;
392             isCompact = false;
393         }
394     }
395     /**
396      * @internal
397      * @deprecated This API is ICU internal only.
398      */
399     public static  final int BLOCKSHIFT = 5; // NormalizerBuilder needs - liu
400     static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
401     static  final int INDEXSHIFT =(16-BLOCKSHIFT);
402     static  final int INDEXCOUNT =(1<<INDEXSHIFT);
403     static  final int BLOCKMASK = BLOCKCOUNT - 1;
404 
405     private char values[];
406     private char indices[];
407     private int[] hashes;
408     private boolean isCompact;
409     char defaultValue;
410 };
411
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags