/*
 * 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 = circle>
 * <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.
 */
 static final 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;
};