325N/A/*
325N/A * Copyright (c) 1996, 2005, Oracle and/or its affiliates. All rights reserved.
325N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
325N/A *
325N/A * This code is free software; you can redistribute it and/or modify it
325N/A * under the terms of the GNU General Public License version 2 only, as
325N/A * published by the Free Software Foundation. Oracle designates this
325N/A * particular file as subject to the "Classpath" exception as provided
325N/A * by Oracle in the LICENSE file that accompanied this code.
325N/A *
325N/A * This code is distributed in the hope that it will be useful, but WITHOUT
325N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
325N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
325N/A * version 2 for more details (a copy is included in the LICENSE file that
325N/A * accompanied this code).
325N/A *
325N/A * You should have received a copy of the GNU General Public License version
325N/A * 2 along with this work; if not, write to the Free Software Foundation,
325N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
325N/A *
325N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
325N/A * or visit www.oracle.com if you need additional information or have any
325N/A * questions.
325N/A */
325N/A
325N/A/*
325N/A * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
325N/A * (C) Copyright IBM Corp. 1996 - All Rights Reserved
325N/A *
325N/A * The original version of this source code and documentation is copyrighted
325N/A * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
325N/A * materials are provided under terms of a License Agreement between Taligent
325N/A * and Sun. This technology is protected by multiple US and International
325N/A * patents. This notice and attribution to Taligent may not be removed.
325N/A * Taligent is a registered trademark of Taligent, Inc.
325N/A *
325N/A */
325N/A
325N/Apackage sun.text;
325N/A
325N/A
325N/A/**
325N/A * class CompactATypeArray : use only on primitive data types
325N/A * Provides a compact way to store information that is indexed by Unicode
325N/A * values, such as character properties, types, keyboard values, etc.This
325N/A * is very useful when you have a block of Unicode data that contains
325N/A * significant values while the rest of the Unicode data is unused in the
325N/A * application or when you have a lot of redundance, such as where all 21,000
325N/A * Han ideographs have the same value. However, lookup is much faster than a
325N/A * hash table.
325N/A * A compact array of any primitive data type serves two purposes:
325N/A * <UL type = round>
325N/A * <LI>Fast access of the indexed values.
325N/A * <LI>Smaller memory footprint.
325N/A * </UL>
325N/A * A compact array is composed of a index array and value array. The index
325N/A * array contains the indicies of Unicode characters to the value array.
325N/A *
325N/A * @see CompactIntArray
325N/A * @see CompactShortArray
325N/A * @author Helena Shih
325N/A */
325N/Apublic final class CompactByteArray implements Cloneable {
325N/A
325N/A /**
325N/A * The total number of Unicode characters.
325N/A */
325N/A public static final int UNICODECOUNT =65536;
325N/A
325N/A /**
325N/A * Constructor for CompactByteArray.
325N/A * @param defaultValue the default value of the compact array.
325N/A */
325N/A public CompactByteArray(byte defaultValue)
325N/A {
325N/A int i;
325N/A values = new byte[UNICODECOUNT];
325N/A indices = new short[INDEXCOUNT];
325N/A hashes = new int[INDEXCOUNT];
325N/A for (i = 0; i < UNICODECOUNT; ++i) {
325N/A values[i] = defaultValue;
325N/A }
325N/A for (i = 0; i < INDEXCOUNT; ++i) {
325N/A indices[i] = (short)(i<<BLOCKSHIFT);
325N/A hashes[i] = 0;
325N/A }
325N/A isCompact = false;
325N/A }
325N/A
325N/A /**
325N/A * Constructor for CompactByteArray.
325N/A * @param indexArray the indicies of the compact array.
325N/A * @param newValues the values of the compact array.
325N/A * @exception IllegalArgumentException If index is out of range.
325N/A */
325N/A public CompactByteArray(short indexArray[],
325N/A byte newValues[])
325N/A {
325N/A int i;
325N/A if (indexArray.length != INDEXCOUNT)
325N/A throw new IllegalArgumentException("Index out of bounds!");
325N/A for (i = 0; i < INDEXCOUNT; ++i) {
325N/A short index = indexArray[i];
325N/A if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
325N/A throw new IllegalArgumentException("Index out of bounds!");
325N/A }
325N/A indices = indexArray;
325N/A values = newValues;
325N/A isCompact = true;
325N/A }
325N/A
325N/A /**
325N/A * Get the mapped value of a Unicode character.
325N/A * @param index the character to get the mapped value with
325N/A * @return the mapped value of the given character
325N/A */
325N/A public byte elementAt(char index)
325N/A {
325N/A return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
325N/A + (index & BLOCKMASK)]);
325N/A }
325N/A /**
325N/A * Set a new value for a Unicode character.
325N/A * Set automatically expands the array if it is compacted.
325N/A * @param index the character to set the mapped value with
325N/A * @param value the new mapped value
325N/A */
325N/A public void setElementAt(char index, byte value)
325N/A {
325N/A if (isCompact)
325N/A expand();
325N/A values[(int)index] = value;
325N/A touchBlock(index >> BLOCKSHIFT, value);
325N/A }
325N/A
325N/A /**
325N/A * Set new values for a range of Unicode character.
325N/A * @param start the starting offset o of the range
325N/A * @param end the ending offset of the range
325N/A * @param value the new mapped value
325N/A */
325N/A public void setElementAt(char start, char end, byte value)
325N/A {
325N/A int i;
325N/A if (isCompact) {
325N/A expand();
325N/A }
325N/A for (i = start; i <= end; ++i) {
325N/A values[i] = value;
325N/A touchBlock(i >> BLOCKSHIFT, value);
325N/A }
325N/A }
325N/A
325N/A /**
325N/A *Compact the array.
325N/A */
325N/A public void compact()
325N/A {
325N/A if (!isCompact) {
325N/A int limitCompacted = 0;
325N/A int iBlockStart = 0;
325N/A short iUntouched = -1;
325N/A
325N/A for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
325N/A indices[i] = -1;
325N/A boolean touched = blockTouched(i);
325N/A if (!touched && iUntouched != -1) {
325N/A // If no values in this block were set, we can just set its
325N/A // index to be the same as some other block with no values
325N/A // set, assuming we've seen one yet.
325N/A indices[i] = iUntouched;
325N/A } else {
325N/A int jBlockStart = 0;
325N/A int j = 0;
325N/A for (j = 0; j < limitCompacted;
325N/A ++j, jBlockStart += BLOCKCOUNT) {
325N/A if (hashes[i] == hashes[j] &&
325N/A arrayRegionMatches(values, iBlockStart,
325N/A values, jBlockStart, BLOCKCOUNT)) {
325N/A indices[i] = (short)jBlockStart;
325N/A break;
325N/A }
325N/A }
325N/A if (indices[i] == -1) {
325N/A // we didn't match, so copy & update
325N/A System.arraycopy(values, iBlockStart,
325N/A values, jBlockStart, BLOCKCOUNT);
325N/A indices[i] = (short)jBlockStart;
325N/A hashes[j] = hashes[i];
325N/A ++limitCompacted;
325N/A
325N/A if (!touched) {
325N/A // If this is the first untouched block we've seen,
325N/A // remember its index.
325N/A iUntouched = (short)jBlockStart;
325N/A }
325N/A }
325N/A }
325N/A }
325N/A // we are done compacting, so now make the array shorter
325N/A int newSize = limitCompacted*BLOCKCOUNT;
325N/A byte[] result = new byte[newSize];
325N/A System.arraycopy(values, 0, result, 0, newSize);
325N/A values = result;
325N/A isCompact = true;
325N/A hashes = null;
325N/A }
325N/A }
325N/A
325N/A /**
325N/A * Convenience utility to compare two arrays of doubles.
325N/A * @param len the length to compare.
325N/A * The start indices and start+len must be valid.
325N/A */
325N/A final static boolean arrayRegionMatches(byte[] source, int sourceStart,
325N/A byte[] target, int targetStart,
325N/A int len)
325N/A {
325N/A int sourceEnd = sourceStart + len;
325N/A int delta = targetStart - sourceStart;
325N/A for (int i = sourceStart; i < sourceEnd; i++) {
325N/A if (source[i] != target[i + delta])
325N/A return false;
325N/A }
325N/A return true;
325N/A }
325N/A
325N/A /**
325N/A * Remember that a specified block was "touched", i.e. had a value set.
325N/A * Untouched blocks can be skipped when compacting the array
325N/A */
325N/A private final void touchBlock(int i, int value) {
325N/A hashes[i] = (hashes[i] + (value<<1)) | 1;
325N/A }
325N/A
325N/A /**
325N/A * Query whether a specified block was "touched", i.e. had a value set.
325N/A * Untouched blocks can be skipped when compacting the array
325N/A */
325N/A private final boolean blockTouched(int i) {
325N/A return hashes[i] != 0;
325N/A }
325N/A
325N/A /** For internal use only. Do not modify the result, the behavior of
325N/A * modified results are undefined.
325N/A */
325N/A public short getIndexArray()[]
325N/A {
325N/A return indices;
325N/A }
325N/A
325N/A /** For internal use only. Do not modify the result, the behavior of
325N/A * modified results are undefined.
325N/A */
325N/A public byte getStringArray()[]
325N/A {
325N/A return values;
325N/A }
325N/A
325N/A /**
325N/A * Overrides Cloneable
325N/A */
325N/A public Object clone()
325N/A {
325N/A try {
325N/A CompactByteArray other = (CompactByteArray) super.clone();
325N/A other.values = (byte[])values.clone();
325N/A other.indices = (short[])indices.clone();
325N/A if (hashes != null) other.hashes = (int[])hashes.clone();
325N/A return other;
325N/A } catch (CloneNotSupportedException e) {
325N/A throw new InternalError();
325N/A }
325N/A }
325N/A
325N/A /**
325N/A * Compares the equality of two compact array objects.
325N/A * @param obj the compact array object to be compared with this.
325N/A * @return true if the current compact array object is the same
325N/A * as the compact array object obj; false otherwise.
325N/A */
325N/A public boolean equals(Object obj) {
325N/A if (obj == null) return false;
325N/A if (this == obj) // quick check
325N/A return true;
325N/A if (getClass() != obj.getClass()) // same class?
325N/A return false;
325N/A CompactByteArray other = (CompactByteArray) obj;
325N/A for (int i = 0; i < UNICODECOUNT; i++) {
325N/A // could be sped up later
325N/A if (elementAt((char)i) != other.elementAt((char)i))
325N/A return false;
325N/A }
325N/A return true; // we made it through the guantlet.
325N/A }
325N/A
325N/A /**
325N/A * Generates the hash code for the compact array object
325N/A */
325N/A
325N/A public int hashCode() {
325N/A int result = 0;
325N/A int increment = Math.min(3, values.length/16);
325N/A for (int i = 0; i < values.length; i+= increment) {
325N/A result = result * 37 + values[i];
325N/A }
325N/A return result;
325N/A }
325N/A
325N/A // --------------------------------------------------------------
325N/A // package private
325N/A // --------------------------------------------------------------
325N/A /**
325N/A * Expanding takes the array back to a 65536 element array.
325N/A */
325N/A private void expand()
325N/A {
325N/A int i;
325N/A if (isCompact) {
325N/A byte[] tempArray;
325N/A hashes = new int[INDEXCOUNT];
325N/A tempArray = new byte[UNICODECOUNT];
325N/A for (i = 0; i < UNICODECOUNT; ++i) {
325N/A byte value = elementAt((char)i);
325N/A tempArray[i] = value;
325N/A touchBlock(i >> BLOCKSHIFT, value);
325N/A }
325N/A for (i = 0; i < INDEXCOUNT; ++i) {
325N/A indices[i] = (short)(i<<BLOCKSHIFT);
325N/A }
325N/A values = null;
325N/A values = tempArray;
325N/A isCompact = false;
325N/A }
325N/A }
325N/A
325N/A private byte[] getArray()
325N/A {
325N/A return values;
325N/A }
325N/A
325N/A private static final int BLOCKSHIFT =7;
325N/A private static final int BLOCKCOUNT =(1<<BLOCKSHIFT);
325N/A private static final int INDEXSHIFT =(16-BLOCKSHIFT);
325N/A private static final int INDEXCOUNT =(1<<INDEXSHIFT);
325N/A private static final int BLOCKMASK = BLOCKCOUNT - 1;
325N/A
325N/A private byte[] values; // char -> short (char parameterized short)
325N/A private short indices[];
325N/A private boolean isCompact;
325N/A private int[] hashes;
325N/A};
325N/A