Back to index...

	/*
	* Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	/*
	* (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
	* (C) Copyright IBM Corp. 1996 - All Rights Reserved
	*
	* The original version of this source code and documentation is copyrighted
	* and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
	* materials are provided under terms of a License Agreement between Taligent
	* and Sun. This technology is protected by multiple US and International
	* patents. This notice and attribution to Taligent may not be removed.
	* Taligent is a registered trademark of Taligent, Inc.
	*
	*/

	package sun.text;


	/**
	* class CompactATypeArray : use only on primitive data types
	* Provides a compact way to store information that is indexed by Unicode
	* values, such as character properties, types, keyboard values, etc.This
	* is very useful when you have a block of Unicode data that contains
	* significant values while the rest of the Unicode data is unused in the
	* application or when you have a lot of redundance, such as where all 21,000
	* Han ideographs have the same value. However, lookup is much faster than a
	* hash table.
	* A compact array of any primitive data type serves two purposes:
	* <UL type = round>
	* <LI>Fast access of the indexed values.
	* <LI>Smaller memory footprint.
	* </UL>
	* A compact array is composed of a index array and value array. The index
	* array contains the indicies of Unicode characters to the value array.
	*
	* @see CompactIntArray
	* @see CompactShortArray
	* @author Helena Shih
	*/
	public final class CompactByteArray implements Cloneable {

	/**
	* The total number of Unicode characters.
	*/
	public static final int UNICODECOUNT =65536;

	/**
	* Constructor for CompactByteArray.
	* @param defaultValue the default value of the compact array.
	*/
	public CompactByteArray(byte defaultValue)
	{
	int i;
	values = new byte[UNICODECOUNT];
	indices = new short[INDEXCOUNT];
	hashes = new int[INDEXCOUNT];
	for (i = 0; i < UNICODECOUNT; ++i) {
	values[i] = defaultValue;
	}
	for (i = 0; i < INDEXCOUNT; ++i) {
	indices[i] = (short)(i<<BLOCKSHIFT);
	hashes[i] = 0;
	}
	isCompact = false;
	}

	/**
	* Constructor for CompactByteArray.
	* @param indexArray the indicies of the compact array.
	* @param newValues the values of the compact array.
	* @exception IllegalArgumentException If index is out of range.
	*/
	public CompactByteArray(short indexArray[],
	byte newValues[])
	{
	int i;
	if (indexArray.length != INDEXCOUNT)
	throw new IllegalArgumentException("Index out of bounds!");
	for (i = 0; i < INDEXCOUNT; ++i) {
	short index = indexArray[i];
	if ((index < 0) \|\| (index >= newValues.length+BLOCKCOUNT))
	throw new IllegalArgumentException("Index out of bounds!");
	}
	indices = indexArray;
	values = newValues;
	isCompact = true;
	}

	/**
	* Get the mapped value of a Unicode character.
	* @param index the character to get the mapped value with
	* @return the mapped value of the given character
	*/
	public byte elementAt(char index)
	{
	return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
	+ (index & BLOCKMASK)]);
	}
	/**
	* Set a new value for a Unicode character.
	* Set automatically expands the array if it is compacted.
	* @param index the character to set the mapped value with
	* @param value the new mapped value
	*/
	public void setElementAt(char index, byte value)
	{
	if (isCompact)
	expand();
	values[(int)index] = value;
	touchBlock(index >> BLOCKSHIFT, value);
	}

	/**
	* Set new values for a range of Unicode character.
	* @param start the starting offset o of the range
	* @param end the ending offset of the range
	* @param value the new mapped value
	*/
	public void setElementAt(char start, char end, byte value)
	{
	int i;
	if (isCompact) {
	expand();
	}
	for (i = start; i <= end; ++i) {
	values[i] = value;
	touchBlock(i >> BLOCKSHIFT, value);
	}
	}

	/**
	*Compact the array.
	*/
	public void compact()
	{
	if (!isCompact) {
	int limitCompacted = 0;
	int iBlockStart = 0;
	short iUntouched = -1;

	for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
	indices[i] = -1;
	boolean touched = blockTouched(i);
	if (!touched && iUntouched != -1) {
	// If no values in this block were set, we can just set its
	// index to be the same as some other block with no values
	// set, assuming we've seen one yet.
	indices[i] = iUntouched;
	} else {
	int jBlockStart = 0;
	int j = 0;
	for (j = 0; j < limitCompacted;
	++j, jBlockStart += BLOCKCOUNT) {
	if (hashes[i] == hashes[j] &&
	arrayRegionMatches(values, iBlockStart,
	values, jBlockStart, BLOCKCOUNT)) {
	indices[i] = (short)jBlockStart;
	break;
	}
	}
	if (indices[i] == -1) {
	// we didn't match, so copy & update
	System.arraycopy(values, iBlockStart,
	values, jBlockStart, BLOCKCOUNT);
	indices[i] = (short)jBlockStart;
	hashes[j] = hashes[i];
	++limitCompacted;

	if (!touched) {
	// If this is the first untouched block we've seen,
	// remember its index.
	iUntouched = (short)jBlockStart;
	}
	}
	}
	}
	// we are done compacting, so now make the array shorter
	int newSize = limitCompacted*BLOCKCOUNT;
	byte[] result = new byte[newSize];
	System.arraycopy(values, 0, result, 0, newSize);
	values = result;
	isCompact = true;
	hashes = null;
	}
	}

	/**
	* Convenience utility to compare two arrays of doubles.
	* @param len the length to compare.
	* The start indices and start+len must be valid.
	*/
	final static boolean arrayRegionMatches(byte[] source, int sourceStart,
	byte[] target, int targetStart,
	int len)
	{
	int sourceEnd = sourceStart + len;
	int delta = targetStart - sourceStart;
	for (int i = sourceStart; i < sourceEnd; i++) {
	if (source[i] != target[i + delta])
	return false;
	}
	return true;
	}

	/**
	* Remember that a specified block was "touched", i.e. had a value set.
	* Untouched blocks can be skipped when compacting the array
	*/
	private final void touchBlock(int i, int value) {
	hashes[i] = (hashes[i] + (value<<1)) \| 1;
	}

	/**
	* Query whether a specified block was "touched", i.e. had a value set.
	* Untouched blocks can be skipped when compacting the array
	*/
	private final boolean blockTouched(int i) {
	return hashes[i] != 0;
	}

	/** For internal use only. Do not modify the result, the behavior of
	* modified results are undefined.
	*/
	public short getIndexArray()[]
	{
	return indices;
	}

	/** For internal use only. Do not modify the result, the behavior of
	* modified results are undefined.
	*/
	public byte getStringArray()[]
	{
	return values;
	}

	/**
	* Overrides Cloneable
	*/
	public Object clone()
	{
	try {
	CompactByteArray other = (CompactByteArray) super.clone();
	other.values = values.clone();
	other.indices = indices.clone();
	if (hashes != null) other.hashes = hashes.clone();
	return other;
	} catch (CloneNotSupportedException e) {
	throw new InternalError(e);
	}
	}

	/**
	* Compares the equality of two compact array objects.
	* @param obj the compact array object to be compared with this.
	* @return true if the current compact array object is the same
	* as the compact array object obj; false otherwise.
	*/
	public boolean equals(Object obj) {
	if (obj == null) return false;
	if (this == obj) // quick check
	return true;
	if (getClass() != obj.getClass()) // same class?
	return false;
	CompactByteArray other = (CompactByteArray) obj;
	for (int i = 0; i < UNICODECOUNT; i++) {
	// could be sped up later
	if (elementAt((char)i) != other.elementAt((char)i))
	return false;
	}
	return true; // we made it through the guantlet.
	}

	/**
	* Generates the hash code for the compact array object
	*/

	public int hashCode() {
	int result = 0;
	int increment = Math.min(3, values.length/16);
	for (int i = 0; i < values.length; i+= increment) {
	result = result * 37 + values[i];
	}
	return result;
	}

	// --------------------------------------------------------------
	// package private
	// --------------------------------------------------------------
	/**
	* Expanding takes the array back to a 65536 element array.
	*/
	private void expand()
	{
	int i;
	if (isCompact) {
	byte[] tempArray;
	hashes = new int[INDEXCOUNT];
	tempArray = new byte[UNICODECOUNT];
	for (i = 0; i < UNICODECOUNT; ++i) {
	byte value = elementAt((char)i);
	tempArray[i] = value;
	touchBlock(i >> BLOCKSHIFT, value);
	}
	for (i = 0; i < INDEXCOUNT; ++i) {
	indices[i] = (short)(i<<BLOCKSHIFT);
	}
	values = null;
	values = tempArray;
	isCompact = false;
	}
	}

	private byte[] getArray()
	{
	return values;
	}

	private static final int BLOCKSHIFT =7;
	private static final int BLOCKCOUNT =(1<<BLOCKSHIFT);
	private static final int INDEXSHIFT =(16-BLOCKSHIFT);
	private static final int INDEXCOUNT =(1<<INDEXSHIFT);
	private static final int BLOCKMASK = BLOCKCOUNT - 1;

	private byte[] values; // char -> short (char parameterized short)
	private short indices[];
	private boolean isCompact;
	private int[] hashes;
	};

Back to index...