View Javadoc
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  
39  package 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 = round>
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   */
63  public 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     final static 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 };