CompactByteArray


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