1 /*
   2  * Copyright (c) 2003, 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 package sun.text;
  27 
  28 public final class UCompactIntArray implements Cloneable {
  29     /**
  30      * Default constructor for UCompactIntArray, the default value of the
  31      * compact array is 0.
  32      */
  33     public UCompactIntArray() {
  34         values = new int[16][];
  35         indices = new short[16][];
  36         blockTouched = new boolean[16][];
  37         planeTouched = new boolean[16];
  38     }
  39 
  40     public UCompactIntArray(int defaultValue) {
  41         this();
  42         this.defaultValue = defaultValue;
  43     }
  44 
  45     /**
  46      * Get the mapped value of a Unicode character.
  47      * @param index the character to get the mapped value with
  48      * @return the mapped value of the given character
  49      */
  50     public int elementAt(int index) {
  51         int plane = (index & PLANEMASK) >> PLANESHIFT;
  52         if (!planeTouched[plane]) {
  53             return defaultValue;
  54         }
  55         index &= CODEPOINTMASK;
  56         return values[plane][(indices[plane][index >> BLOCKSHIFT] & 0xFFFF)
  57                        + (index & BLOCKMASK)];
  58     }
  59 
  60 
  61     /**
  62      * Set a new value for a Unicode character.
  63      * Set automatically expands the array if it is compacted.
  64      * @param index the character to set the mapped value with
  65      * @param value the new mapped value
  66      */
  67     public void setElementAt(int index, int value) {
  68         if (isCompact) {
  69             expand();
  70         }
  71         int plane = (index & PLANEMASK) >> PLANESHIFT;
  72         if (!planeTouched[plane]) {
  73             initPlane(plane);
  74         }
  75         index &= CODEPOINTMASK;
  76         values[plane][index] = value;
  77         blockTouched[plane][index >> BLOCKSHIFT] = true;
  78     }
  79 
  80 
  81     /**
  82      * Compact the array.
  83      */
  84     public void compact() {
  85         if (isCompact) {
  86             return;
  87         }
  88         for (int plane = 0; plane < PLANECOUNT; plane++) {
  89             if (!planeTouched[plane]) {
  90                 continue;
  91             }
  92             int limitCompacted = 0;
  93             int iBlockStart = 0;
  94             short iUntouched = -1;
  95 
  96             for (int i = 0; i < indices[plane].length; ++i, iBlockStart += BLOCKCOUNT) {
  97                 indices[plane][i] = -1;
  98                 if (!blockTouched[plane][i] && iUntouched != -1) {
  99                     // If no values in this block were set, we can just set its
 100                     // index to be the same as some other block with no values
 101                     // set, assuming we've seen one yet.
 102                     indices[plane][i] = iUntouched;
 103                 } else {
 104                     int jBlockStart = limitCompacted * BLOCKCOUNT;
 105                     if (i > limitCompacted) {
 106                         System.arraycopy(values[plane], iBlockStart,
 107                                          values[plane], jBlockStart, BLOCKCOUNT);
 108                     }
 109                     if (!blockTouched[plane][i]) {
 110                         // If this is the first untouched block we've seen, remember it.
 111                         iUntouched = (short)jBlockStart;
 112                     }
 113                     indices[plane][i] = (short)jBlockStart;
 114                     limitCompacted++;
 115                 }
 116             }
 117 
 118             // we are done compacting, so now make the array shorter
 119             int newSize = limitCompacted * BLOCKCOUNT;
 120             int[] result = new int[newSize];
 121             System.arraycopy(values[plane], 0, result, 0, newSize);
 122             values[plane] = result;
 123             blockTouched[plane] = null;
 124         }
 125         isCompact = true;
 126     }
 127 
 128 
 129     // --------------------------------------------------------------
 130     // private
 131     // --------------------------------------------------------------
 132     /**
 133      * Expanded takes the array back to a 0x10ffff element array
 134      */
 135     private void expand() {
 136         int i;
 137         if (isCompact) {
 138             int[]   tempArray;
 139             for (int plane = 0; plane < PLANECOUNT; plane++) {
 140                 if (!planeTouched[plane]) {
 141                     continue;
 142                 }
 143                 blockTouched[plane] = new boolean[INDEXCOUNT];
 144                 tempArray = new int[UNICODECOUNT];
 145                 for (i = 0; i < UNICODECOUNT; ++i) {
 146                     tempArray[i] = values[plane][indices[plane][i >> BLOCKSHIFT]
 147                                                 & 0xffff + (i & BLOCKMASK)];
 148                     blockTouched[plane][i >> BLOCKSHIFT] = true;
 149                 }
 150                 for (i = 0; i < INDEXCOUNT; ++i) {
 151                     indices[plane][i] = (short)(i<<BLOCKSHIFT);
 152                 }
 153                 values[plane] = tempArray;
 154             }
 155             isCompact = false;
 156         }
 157     }
 158 
 159     private void initPlane(int plane) {
 160         values[plane] = new int[UNICODECOUNT];
 161         indices[plane] = new short[INDEXCOUNT];
 162         blockTouched[plane] = new boolean[INDEXCOUNT];
 163         planeTouched[plane] = true;
 164 
 165         if (planeTouched[0] && plane != 0) {
 166             System.arraycopy(indices[0], 0, indices[plane], 0, INDEXCOUNT);
 167         } else {
 168             for (int i = 0; i < INDEXCOUNT; ++i) {
 169                 indices[plane][i] = (short)(i<<BLOCKSHIFT);
 170             }
 171         }
 172         for (int i = 0; i < UNICODECOUNT; ++i) {
 173             values[plane][i] = defaultValue;
 174         }
 175     }
 176 
 177     public int getKSize() {
 178         int size = 0;
 179         for (int plane = 0; plane < PLANECOUNT; plane++) {
 180             if (planeTouched[plane]) {
 181                 size += (values[plane].length * 4 + indices[plane].length * 2);
 182             }
 183         }
 184         return size / 1024;
 185     }
 186 
 187     private static final int PLANEMASK = 0x30000;
 188     private static final int PLANESHIFT = 16;
 189     private static final int PLANECOUNT = 0x10;
 190     private static final int CODEPOINTMASK  = 0xffff;
 191 
 192     private static final int UNICODECOUNT = 0x10000;
 193     private static final int BLOCKSHIFT = 7;
 194     private static final int BLOCKCOUNT = (1<<BLOCKSHIFT);
 195     private static final int INDEXSHIFT = (16-BLOCKSHIFT);
 196     private static final int INDEXCOUNT = (1<<INDEXSHIFT);
 197     private static final int BLOCKMASK = BLOCKCOUNT - 1;
 198 
 199     private int defaultValue;
 200     private int[][] values;
 201     private short[][] indices;
 202     private boolean isCompact;
 203     private boolean[][] blockTouched;
 204     private boolean[] planeTouched;
 205 };