1/*
2 * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26/*
27 * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
28 * (C) Copyright IBM Corp. 1996 - All Rights Reserved
29 *
30 *   The original version of this source code and documentation is copyrighted
31 * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
32 * materials are provided under terms of a License Agreement between Taligent
33 * and Sun. This technology is protected by multiple US and International
34 * patents. This notice and attribution to Taligent may not be removed.
35 *   Taligent is a registered trademark of Taligent, Inc.
36 *
37 */
38
39package sun.text;
40
41
42/**
43 * class CompactATypeArray : use only on primitive data types
44 * Provides a compact way to store information that is indexed by Unicode
45 * values, such as character properties, types, keyboard values, etc.This
46 * is very useful when you have a block of Unicode data that contains
47 * significant values while the rest of the Unicode data is unused in the
48 * application or when you have a lot of redundance, such as where all 21,000
49 * Han ideographs have the same value.  However, lookup is much faster than a
50 * hash table.
51 * A compact array of any primitive data type serves two purposes:
52 * <UL type = circle>
53 *     <LI>Fast access of the indexed values.
54 *     <LI>Smaller memory footprint.
55 * </UL>
56 * A compact array is composed of a index array and value array.  The index
57 * array contains the indicies of Unicode characters to the value array.
58 *
59 * @see                CompactIntArray
60 * @see                CompactShortArray
61 * @author             Helena Shih
62 */
63public final class CompactByteArray implements Cloneable {
64
65    /**
66     * The total number of Unicode characters.
67     */
68    public static  final int UNICODECOUNT =65536;
69
70    /**
71     * Constructor for CompactByteArray.
72     * @param defaultValue the default value of the compact array.
73     */
74    public CompactByteArray(byte defaultValue)
75    {
76        int i;
77        values = new byte[UNICODECOUNT];
78        indices = new short[INDEXCOUNT];
79        hashes = new int[INDEXCOUNT];
80        for (i = 0; i < UNICODECOUNT; ++i) {
81            values[i] = defaultValue;
82        }
83        for (i = 0; i < INDEXCOUNT; ++i) {
84            indices[i] = (short)(i<<BLOCKSHIFT);
85            hashes[i] = 0;
86        }
87        isCompact = false;
88    }
89
90    /**
91     * Constructor for CompactByteArray.
92     * @param indexArray the indicies of the compact array.
93     * @param newValues the values of the compact array.
94     * @exception IllegalArgumentException If index is out of range.
95     */
96     public CompactByteArray(short indexArray[],
97                            byte newValues[])
98    {
99        int i;
100        if (indexArray.length != INDEXCOUNT)
101            throw new IllegalArgumentException("Index out of bounds!");
102        for (i = 0; i < INDEXCOUNT; ++i) {
103            short index = indexArray[i];
104            if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
105                throw new IllegalArgumentException("Index out of bounds!");
106        }
107        indices = indexArray;
108        values = newValues;
109        isCompact = true;
110    }
111
112    /**
113     * Get the mapped value of a Unicode character.
114     * @param index the character to get the mapped value with
115     * @return the mapped value of the given character
116     */
117    public byte elementAt(char index)
118    {
119        return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
120                       + (index & BLOCKMASK)]);
121    }
122    /**
123     * Set a new value for a Unicode character.
124     * Set automatically expands the array if it is compacted.
125     * @param index the character to set the mapped value with
126     * @param value the new mapped value
127     */
128    public void setElementAt(char index, byte value)
129    {
130        if (isCompact)
131            expand();
132        values[(int)index] = value;
133        touchBlock(index >> BLOCKSHIFT, value);
134    }
135
136    /**
137     * Set new values for a range of Unicode character.
138     * @param start the starting offset o of the range
139     * @param end the ending offset of the range
140     * @param value the new mapped value
141     */
142    public void setElementAt(char start, char end, byte value)
143    {
144        int i;
145        if (isCompact) {
146            expand();
147        }
148        for (i = start; i <= end; ++i) {
149            values[i] = value;
150            touchBlock(i >> BLOCKSHIFT, value);
151        }
152    }
153
154    /**
155      *Compact the array.
156      */
157    public void compact()
158    {
159        if (!isCompact) {
160            int limitCompacted = 0;
161            int iBlockStart = 0;
162            short iUntouched = -1;
163
164            for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
165                indices[i] = -1;
166                boolean touched = blockTouched(i);
167                if (!touched && iUntouched != -1) {
168                    // If no values in this block were set, we can just set its
169                    // index to be the same as some other block with no values
170                    // set, assuming we've seen one yet.
171                    indices[i] = iUntouched;
172                } else {
173                    int jBlockStart = 0;
174                    int j = 0;
175                    for (j = 0; j < limitCompacted;
176                            ++j, jBlockStart += BLOCKCOUNT) {
177                        if (hashes[i] == hashes[j] &&
178                                arrayRegionMatches(values, iBlockStart,
179                                values, jBlockStart, BLOCKCOUNT)) {
180                            indices[i] = (short)jBlockStart;
181                            break;
182                        }
183                    }
184                    if (indices[i] == -1) {
185                        // we didn't match, so copy & update
186                        System.arraycopy(values, iBlockStart,
187                            values, jBlockStart, BLOCKCOUNT);
188                        indices[i] = (short)jBlockStart;
189                        hashes[j] = hashes[i];
190                        ++limitCompacted;
191
192                        if (!touched) {
193                            // If this is the first untouched block we've seen,
194                            // remember its index.
195                            iUntouched = (short)jBlockStart;
196                        }
197                    }
198                }
199            }
200            // we are done compacting, so now make the array shorter
201            int newSize = limitCompacted*BLOCKCOUNT;
202            byte[] result = new byte[newSize];
203            System.arraycopy(values, 0, result, 0, newSize);
204            values = result;
205            isCompact = true;
206            hashes = null;
207        }
208    }
209
210    /**
211     * Convenience utility to compare two arrays of doubles.
212     * @param len the length to compare.
213     * The start indices and start+len must be valid.
214     */
215    static final boolean arrayRegionMatches(byte[] source, int sourceStart,
216                                            byte[] target, int targetStart,
217                                            int len)
218    {
219        int sourceEnd = sourceStart + len;
220        int delta = targetStart - sourceStart;
221        for (int i = sourceStart; i < sourceEnd; i++) {
222            if (source[i] != target[i + delta])
223            return false;
224        }
225        return true;
226    }
227
228    /**
229     * Remember that 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 void touchBlock(int i, int value) {
233        hashes[i] = (hashes[i] + (value<<1)) | 1;
234    }
235
236    /**
237     * Query whether a specified block was "touched", i.e. had a value set.
238     * Untouched blocks can be skipped when compacting the array
239     */
240    private final boolean blockTouched(int i) {
241        return hashes[i] != 0;
242    }
243
244    /** For internal use only.  Do not modify the result, the behavior of
245      * modified results are undefined.
246      */
247    public short getIndexArray()[]
248    {
249        return indices;
250    }
251
252    /** For internal use only.  Do not modify the result, the behavior of
253      * modified results are undefined.
254      */
255    public byte getStringArray()[]
256    {
257        return values;
258    }
259
260    /**
261     * Overrides Cloneable
262     */
263    public Object clone()
264    {
265        try {
266            CompactByteArray other = (CompactByteArray) super.clone();
267            other.values = values.clone();
268            other.indices = indices.clone();
269            if (hashes != null) other.hashes = hashes.clone();
270            return other;
271        } catch (CloneNotSupportedException e) {
272            throw new InternalError(e);
273        }
274    }
275
276    /**
277     * Compares the equality of two compact array objects.
278     * @param obj the compact array object to be compared with this.
279     * @return true if the current compact array object is the same
280     * as the compact array object obj; false otherwise.
281     */
282    public boolean equals(Object obj) {
283        if (obj == null) return false;
284        if (this == obj)                      // quick check
285            return true;
286        if (getClass() != obj.getClass())         // same class?
287            return false;
288        CompactByteArray other = (CompactByteArray) obj;
289        for (int i = 0; i < UNICODECOUNT; i++) {
290            // could be sped up later
291            if (elementAt((char)i) != other.elementAt((char)i))
292                return false;
293        }
294        return true; // we made it through the guantlet.
295    }
296
297    /**
298     * Generates the hash code for the compact array object
299     */
300
301    public int hashCode() {
302        int result = 0;
303        int increment = Math.min(3, values.length/16);
304        for (int i = 0; i < values.length; i+= increment) {
305            result = result * 37 + values[i];
306        }
307        return result;
308    }
309
310    // --------------------------------------------------------------
311    // package private
312    // --------------------------------------------------------------
313    /**
314      * Expanding takes the array back to a 65536 element array.
315      */
316    private void expand()
317    {
318        int i;
319        if (isCompact) {
320            byte[]  tempArray;
321            hashes = new int[INDEXCOUNT];
322            tempArray = new byte[UNICODECOUNT];
323            for (i = 0; i < UNICODECOUNT; ++i) {
324                byte value = elementAt((char)i);
325                tempArray[i] = value;
326                touchBlock(i >> BLOCKSHIFT, value);
327            }
328            for (i = 0; i < INDEXCOUNT; ++i) {
329                indices[i] = (short)(i<<BLOCKSHIFT);
330            }
331            values = null;
332            values = tempArray;
333            isCompact = false;
334        }
335    }
336
337    private byte[] getArray()
338    {
339        return values;
340    }
341
342    private static  final int BLOCKSHIFT =7;
343    private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
344    private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
345    private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
346    private static  final int BLOCKMASK = BLOCKCOUNT - 1;
347
348    private byte[] values;  // char -> short (char parameterized short)
349    private short indices[];
350    private boolean isCompact;
351    private int[] hashes;
352};
353