2 *******************************************************************************
3 * Copyright (C) 1996-2009, International Business Machines Corporation and *
4 * others. All Rights Reserved. *
5 *******************************************************************************
8 package com.ibm.icu.util;
10 import com.ibm.icu.impl.Utility;
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
21 * A compact array of any primitive data type serves two purposes:
23 * <LI>Fast access of the indexed values.
24 * <LI>Smaller memory footprint.
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
31 * @deprecated This API is ICU internal only.
33 public final class CompactCharArray implements Cloneable {
36 * The total number of Unicode characters.
38 * @deprecated This API is ICU internal only.
40 public static final int UNICODECOUNT = 65536;
43 * Default constructor for CompactCharArray, the default value of the
46 * @deprecated This API is ICU internal only.
48 public CompactCharArray()
54 * Constructor for CompactCharArray.
55 * @param defaultValue the default value of the compact array.
57 * @deprecated This API is ICU internal only.
59 public CompactCharArray(char defaultValue)
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;
68 for (i = 0; i < INDEXCOUNT; ++i) {
69 indices[i] = (char)(i<<BLOCKSHIFT);
74 this.defaultValue = defaultValue;
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.
83 * @deprecated This API is ICU internal only.
85 public CompactCharArray(char indexArray[],
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.");
102 * Constructor for CompactCharArray.
104 * @param indexArray the RLE-encoded indicies of the compact array.
105 * @param valueArray the RLE-encoded values of the compact array.
107 * @throws IllegalArgumentException if the index or value array is
110 * @deprecated This API is ICU internal only.
112 public CompactCharArray(String indexArray,
115 this( Utility.RLEStringToCharArray(indexArray),
116 Utility.RLEStringToCharArray(valueArray));
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
124 * @deprecated This API is ICU internal only.
126 public char elementAt(char index)
128 int ix = (indices[index >> BLOCKSHIFT] & 0xFFFF)
129 + (index & BLOCKMASK);
130 return ix >= values.length ? defaultValue : values[ix];
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
139 * @deprecated This API is ICU internal only.
141 public void setElementAt(char index, char value)
145 values[(int)index] = value;
146 touchBlock(index >> BLOCKSHIFT, value);
150 * Set new values for a range of Unicode character.
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
156 * @deprecated This API is ICU internal only.
158 public void setElementAt(char start, char end, char value)
164 for (i = start; i <= end; ++i) {
166 touchBlock(i >> BLOCKSHIFT, value);
172 * @deprecated This API is ICU internal only.
174 public void compact() {
181 * @deprecated This API is ICU internal only.
183 public void compact(boolean exhaustive)
187 char iUntouched = 0xFFFF;
190 char[] target = exhaustive ? new char[UNICODECOUNT] : values;
192 for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
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;
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];
210 if (indices[i] == 0xFFFF) {
211 int dest; // Where to copy
213 // See if we can find some overlap with another block
214 dest = FindOverlappingPosition(iBlockStart, target,
217 // Just copy to the end; it's quicker
220 int limit = dest + BLOCKCOUNT;
221 if (limit > newSize) {
222 for (int j = newSize; j < limit; ++j) {
223 target[j] = values[iBlockStart + j - dest];
227 indices[i] = (char)dest;
229 // If this is the first untouched block we've seen,
230 // remember its index.
231 iUntouched = (char)jBlockStart;
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);
245 private int FindOverlappingPosition(int start, char[] tempValues, int tempCount)
247 for (int i = 0; i < tempCount; i += 1) {
248 int currentCount = BLOCKCOUNT;
249 if (i + BLOCKCOUNT > tempCount) {
250 currentCount = tempCount - i;
252 if (arrayRegionMatches(values, start, tempValues, i, currentCount))
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.
263 final static boolean arrayRegionMatches(char[] source, int sourceStart,
264 char[] target, int targetStart,
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])
277 * Remember that a specified block was "touched", i.e. had a value set.
278 * Untouched blocks can be skipped when compacting the array
280 private final void touchBlock(int i, int value) {
281 hashes[i] = (hashes[i] + (value<<1)) | 1;
285 * Query whether a specified block was "touched", i.e. had a value set.
286 * Untouched blocks can be skipped when compacting the array
288 private final boolean blockTouched(int i) {
289 return hashes[i] != 0;
293 * For internal use only. Do not modify the result, the behavior of
294 * modified results are undefined.
296 * @deprecated This API is ICU internal only.
298 public char[] getIndexArray()
304 * For internal use only. Do not modify the result, the behavior of
305 * modified results are undefined.
307 * @deprecated This API is ICU internal only.
309 public char[] getValueArray()
315 * Overrides Cloneable
317 * @deprecated This API is ICU internal only.
319 public Object clone()
322 CompactCharArray other = (CompactCharArray) super.clone();
323 other.values = values.clone();
324 other.indices = indices.clone();
325 if (hashes != null) other.hashes = hashes.clone();
327 } catch (CloneNotSupportedException e) {
328 throw new IllegalStateException();
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.
338 * @deprecated This API is ICU internal only.
340 public boolean equals(Object obj) {
341 if (obj == null) return false;
342 if (this == obj) // quick check
344 if (getClass() != obj.getClass()) // same class?
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))
352 return true; // we made it through the guantlet.
356 * Generates the hash code for the compact array object
358 * @deprecated This API is ICU internal only.
360 public int hashCode() {
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];
370 // --------------------------------------------------------------
372 // --------------------------------------------------------------
375 * Expanding takes the array back to a 65536 element array.
377 private void expand()
382 hashes = new int[INDEXCOUNT];
383 tempArray = new char[UNICODECOUNT];
384 for (i = 0; i < UNICODECOUNT; ++i) {
385 tempArray[i] = elementAt((char)i);
387 for (i = 0; i < INDEXCOUNT; ++i) {
388 indices[i] = (char)(i<<BLOCKSHIFT);
397 * @deprecated This API is ICU internal only.
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;
405 private char values[];
406 private char indices[];
407 private int[] hashes;
408 private boolean isCompact;