001: /*
002: *
003: * @(#)CompactIntArray.java 1.22 06/10/10
004: *
005: * Portions Copyright 2000-2006 Sun Microsystems, Inc. All Rights
006: * Reserved. Use is subject to license terms.
007: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
008: *
009: * This program is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU General Public License version
011: * 2 only, as published by the Free Software Foundation.
012: *
013: * This program is distributed in the hope that it will be useful, but
014: * WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * General Public License version 2 for more details (a copy is
017: * included at /legal/license.txt).
018: *
019: * You should have received a copy of the GNU General Public License
020: * version 2 along with this work; if not, write to the Free Software
021: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
022: * 02110-1301 USA
023: *
024: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
025: * Clara, CA 95054 or visit www.sun.com if you need additional
026: * information or have any questions.
027: */
028:
029: /*
030: * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
031: * (C) Copyright IBM Corp. 1996 - All Rights Reserved
032: *
033: * The original version of this source code and documentation is copyrighted
034: * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
035: * materials are provided under terms of a License Agreement between Taligent
036: * and Sun. This technology is protected by multiple US and International
037: * patents. This notice and attribution to Taligent may not be removed.
038: * Taligent is a registered trademark of Taligent, Inc.
039: *
040: */
041:
042: package sun.text;
043:
044: /**
045: * class CompactATypeArray : use only on primitive data types
046: * Provides a compact way to store information that is indexed by Unicode
047: * values, such as character properties, types, keyboard values, etc.This
048: * is very useful when you have a block of Unicode data that contains
049: * significant values while the rest of the Unicode data is unused in the
050: * application or when you have a lot of redundance, such as where all 21,000
051: * Han ideographs have the same value. However, lookup is much faster than a
052: * hash table.
053: * A compact array of any primitive data type serves two purposes:
054: * <UL type = round>
055: * <LI>Fast access of the indexed values.
056: * <LI>Smaller memory footprint.
057: * </UL>
058: * A compact array is composed of a index array and value array. The index
059: * array contains the indicies of Unicode characters to the value array.
060: *
061: * @see CompactShortArray
062: * @see CompactByteArray
063: * @version 1.22 10/10/06
064: * @author Helena Shih
065: */
066: public final class CompactIntArray implements Cloneable {
067:
068: /**
069: * The total number of Unicode characters.
070: */
071: public static final int UNICODECOUNT = 65536;
072:
073: /**
074: * Default constructor for CompactIntArray, the default value of the
075: * compact array is 0.
076: */
077: public CompactIntArray() {
078: this (0);
079: }
080:
081: /**
082: * Constructor for CompactIntArray.
083: * @param defaultValue the default value of the compact array.
084: */
085:
086: public CompactIntArray(int defaultValue) {
087: int i;
088: values = new int[UNICODECOUNT];
089: indices = new short[INDEXCOUNT];
090: hashes = new int[INDEXCOUNT];
091:
092: for (i = 0; i < UNICODECOUNT; ++i) {
093: values[i] = defaultValue;
094: }
095: for (i = 0; i < INDEXCOUNT; ++i) {
096: indices[i] = (short) (i << BLOCKSHIFT);
097: hashes[i] = 0;
098: }
099: isCompact = false;
100: }
101:
102: /**
103: * Constructor for CompactIntArray.
104: * @param indexArray the indicies of the compact array.
105: * @param newValues the values of the compact array.
106: * @exception IllegalArgumentException If the index is out of range.
107: */
108: public CompactIntArray(short indexArray[], int newValues[]) {
109: int i;
110: if (indexArray.length != INDEXCOUNT)
111: throw new IllegalArgumentException("Index out of bounds.");
112: for (i = 0; i < INDEXCOUNT; ++i) {
113: short index = indexArray[i];
114: if ((index < 0) || (index >= newValues.length + BLOCKCOUNT))
115: throw new IllegalArgumentException(
116: "Index out of bounds.");
117: }
118: indices = indexArray;
119: values = newValues;
120: isCompact = true;
121: }
122:
123: /**
124: * Get the mapped value of a Unicode character.
125: * @param index the character to get the mapped value with
126: * @return the mapped value of the given character
127: */
128: public int elementAt(char index) {
129: return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
130: + (index & BLOCKMASK)]);
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: */
139: public void setElementAt(char index, int value) {
140: if (isCompact) {
141: expand();
142: }
143: values[(int) index] = value;
144: touchBlock(index >> BLOCKSHIFT, value);
145: }
146:
147: /**
148: * Set new values for a range of Unicode character.
149: * @param start the startting offset of the range
150: * @param end the ending offset of the range
151: * @param value the new mapped value
152: */
153: public void setElementAt(char start, char end, int value) {
154: int i;
155: if (isCompact) {
156: expand();
157: }
158: for (i = start; i <= end; ++i) {
159: values[i] = value;
160: touchBlock(i >> BLOCKSHIFT, value);
161: }
162: }
163:
164: /**
165: * Compact the array.
166: */
167: public void compact() {
168: if (!isCompact) {
169: int limitCompacted = 0;
170: int iBlockStart = 0;
171: short iUntouched = -1;
172:
173: for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
174: indices[i] = -1;
175: boolean touched = blockTouched(i);
176: if (!touched && iUntouched != -1) {
177: // If no values in this block were set, we can just set its
178: // index to be the same as some other block with no values
179: // set, assuming we've seen one yet.
180: indices[i] = iUntouched;
181: } else {
182: int jBlockStart = 0;
183: int j = 0;
184: for (j = 0; j < limitCompacted; ++j, jBlockStart += BLOCKCOUNT) {
185: if (hashes[i] == hashes[j]
186: && Utility.arrayRegionMatches(values,
187: iBlockStart, values,
188: jBlockStart, BLOCKCOUNT)) {
189: indices[i] = (short) jBlockStart;
190: break;
191: }
192: }
193: if (indices[i] == -1) {
194: // we didn't match, so copy & update
195: System.arraycopy(values, iBlockStart, values,
196: jBlockStart, BLOCKCOUNT);
197: indices[i] = (short) jBlockStart;
198: hashes[j] = hashes[i];
199: ++limitCompacted;
200:
201: if (!touched) {
202: // If this is the first untouched block we've seen,
203: // remember its index.
204: iUntouched = (short) jBlockStart;
205: }
206: }
207: }
208: }
209:
210: // we are done compacting, so now make the array shorter
211: int newSize = limitCompacted * BLOCKCOUNT;
212: int[] result = new int[newSize];
213: System.arraycopy(values, 0, result, 0, newSize);
214: values = result;
215: isCompact = true;
216: hashes = null;
217: }
218: }
219:
220: /**
221: * Remember that a specified block was "touched", i.e. had a value set.
222: * Untouched blocks can be skipped when compacting the array
223: */
224: private final void touchBlock(int i, int value) {
225: hashes[i] = (hashes[i] + (value << 1)) | 1;
226: }
227:
228: /**
229: * Query whether a specified block was "touched", i.e. had a value set.
230: * Untouched blocks can be skipped when compacting the array
231: */
232: private final boolean blockTouched(int i) {
233: return hashes[i] != 0;
234: }
235:
236: /** For internal use only. Do not modify the result, the behavior of
237: * modified results are undefined.
238: */
239: public short getIndexArray()[] {
240: return indices;
241: }
242:
243: /** For internal use only. Do not modify the result, the behavior of
244: * modified results are undefined.
245: */
246: public int getStringArray()[] {
247: return values;
248: }
249:
250: /**
251: * Overrides Cloneable
252: */
253: public Object clone() {
254: try {
255: CompactIntArray other = (CompactIntArray) super .clone();
256: other.values = (int[]) values.clone();
257: other.indices = (short[]) indices.clone();
258:
259: if (hashes != null)
260: other.hashes = (int[]) hashes.clone();
261: return other;
262: } catch (CloneNotSupportedException e) {
263: throw new InternalError();
264: }
265: }
266:
267: /**
268: * Compares the equality of two compact array objects.
269: * @param obj the compact array object to be compared with this.
270: * @return true if the current compact array object is the same
271: * as the compact array object obj; false otherwise.
272: */
273: public boolean equals(Object obj) {
274: if (obj == null)
275: return false;
276: if (this == obj) // quick check
277: return true;
278: if (getClass() != obj.getClass()) // same class?
279: return false;
280: CompactIntArray other = (CompactIntArray) obj;
281: for (int i = 0; i < UNICODECOUNT; i++) {
282: // could be sped up later
283: if (elementAt((char) i) != other.elementAt((char) i))
284: return false;
285: }
286: return true; // we made it through the gauntlet.
287: }
288:
289: /**
290: * Generates the hash code for the compact array object
291: */
292: public int hashCode() {
293: int result = 0;
294: int increment = Math.min(3, values.length / 16);
295: for (int i = 0; i < values.length; i += increment) {
296: result = result * 37 + values[i];
297: }
298: return result;
299: }
300:
301: // --------------------------------------------------------------
302: // private
303: // --------------------------------------------------------------
304: /**
305: * Expanded takes the array back to a 65536 element array
306: */
307: private void expand() {
308: int i;
309: if (isCompact) {
310: int[] tempArray;
311: hashes = new int[INDEXCOUNT];
312: tempArray = new int[UNICODECOUNT];
313: for (i = 0; i < UNICODECOUNT; ++i) {
314: int value = elementAt((char) i);
315: tempArray[i] = value;
316: touchBlock(i >> BLOCKSHIFT, value);
317: }
318: for (i = 0; i < INDEXCOUNT; ++i) {
319: indices[i] = (short) (i << BLOCKSHIFT);
320: }
321: values = tempArray;
322: isCompact = false;
323: }
324: }
325:
326: private static final int BLOCKSHIFT = 7;
327: private static final int BLOCKCOUNT = (1 << BLOCKSHIFT);
328: private static final int INDEXSHIFT = (16 - BLOCKSHIFT);
329: private static final int INDEXCOUNT = (1 << INDEXSHIFT);
330: private static final int BLOCKMASK = BLOCKCOUNT - 1;
331:
332: private int[] values; // char -> int (char parameterized int)
333: private short indices[];
334: private boolean isCompact;
335: private int[] hashes;
336: };
|