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
26package sun.text;
27
28public 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};
206