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 = 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  */
  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     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 };