1/*
2 * Copyright (C) 2006 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.util;
18
19import com.android.internal.util.ArrayUtils;
20
21/**
22 * SparseBooleanArrays map integers to booleans.
23 * Unlike a normal array of booleans
24 * there can be gaps in the indices.  It is intended to be more efficient
25 * than using a HashMap to map Integers to Booleans.
26 */
27public class SparseBooleanArray implements Cloneable {
28    /**
29     * Creates a new SparseBooleanArray containing no mappings.
30     */
31    public SparseBooleanArray() {
32        this(10);
33    }
34
35    /**
36     * Creates a new SparseBooleanArray containing no mappings that will not
37     * require any additional memory allocation to store the specified
38     * number of mappings.
39     */
40    public SparseBooleanArray(int initialCapacity) {
41        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
42
43        mKeys = new int[initialCapacity];
44        mValues = new boolean[initialCapacity];
45        mSize = 0;
46    }
47
48    @Override
49    public SparseBooleanArray clone() {
50        SparseBooleanArray clone = null;
51        try {
52            clone = (SparseBooleanArray) super.clone();
53            clone.mKeys = mKeys.clone();
54            clone.mValues = mValues.clone();
55        } catch (CloneNotSupportedException cnse) {
56            /* ignore */
57        }
58        return clone;
59    }
60
61    /**
62     * Gets the boolean mapped from the specified key, or <code>false</code>
63     * if no such mapping has been made.
64     */
65    public boolean get(int key) {
66        return get(key, false);
67    }
68
69    /**
70     * Gets the boolean mapped from the specified key, or the specified value
71     * if no such mapping has been made.
72     */
73    public boolean get(int key, boolean valueIfKeyNotFound) {
74        int i = binarySearch(mKeys, 0, mSize, key);
75
76        if (i < 0) {
77            return valueIfKeyNotFound;
78        } else {
79            return mValues[i];
80        }
81    }
82
83    /**
84     * Removes the mapping from the specified key, if there was any.
85     */
86    public void delete(int key) {
87        int i = binarySearch(mKeys, 0, mSize, key);
88
89        if (i >= 0) {
90            System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1));
91            System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1));
92            mSize--;
93        }
94    }
95
96    /**
97     * Adds a mapping from the specified key to the specified value,
98     * replacing the previous mapping from the specified key if there
99     * was one.
100     */
101    public void put(int key, boolean value) {
102        int i = binarySearch(mKeys, 0, mSize, key);
103
104        if (i >= 0) {
105            mValues[i] = value;
106        } else {
107            i = ~i;
108
109            if (mSize >= mKeys.length) {
110                int n = ArrayUtils.idealIntArraySize(mSize + 1);
111
112                int[] nkeys = new int[n];
113                boolean[] nvalues = new boolean[n];
114
115                // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n);
116                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
117                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
118
119                mKeys = nkeys;
120                mValues = nvalues;
121            }
122
123            if (mSize - i != 0) {
124                // Log.e("SparseBooleanArray", "move " + (mSize - i));
125                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
126                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
127            }
128
129            mKeys[i] = key;
130            mValues[i] = value;
131            mSize++;
132        }
133    }
134
135    /**
136     * Returns the number of key-value mappings that this SparseBooleanArray
137     * currently stores.
138     */
139    public int size() {
140        return mSize;
141    }
142
143    /**
144     * Given an index in the range <code>0...size()-1</code>, returns
145     * the key from the <code>index</code>th key-value mapping that this
146     * SparseBooleanArray stores.
147     */
148    public int keyAt(int index) {
149        return mKeys[index];
150    }
151
152    /**
153     * Given an index in the range <code>0...size()-1</code>, returns
154     * the value from the <code>index</code>th key-value mapping that this
155     * SparseBooleanArray stores.
156     */
157    public boolean valueAt(int index) {
158        return mValues[index];
159    }
160
161    /**
162     * Returns the index for which {@link #keyAt} would return the
163     * specified key, or a negative number if the specified
164     * key is not mapped.
165     */
166    public int indexOfKey(int key) {
167        return binarySearch(mKeys, 0, mSize, key);
168    }
169
170    /**
171     * Returns an index for which {@link #valueAt} would return the
172     * specified key, or a negative number if no keys map to the
173     * specified value.
174     * Beware that this is a linear search, unlike lookups by key,
175     * and that multiple keys can map to the same value and this will
176     * find only one of them.
177     */
178    public int indexOfValue(boolean value) {
179        for (int i = 0; i < mSize; i++)
180            if (mValues[i] == value)
181                return i;
182
183        return -1;
184    }
185
186    /**
187     * Removes all key-value mappings from this SparseBooleanArray.
188     */
189    public void clear() {
190        mSize = 0;
191    }
192
193    /**
194     * Puts a key/value pair into the array, optimizing for the case where
195     * the key is greater than all existing keys in the array.
196     */
197    public void append(int key, boolean value) {
198        if (mSize != 0 && key <= mKeys[mSize - 1]) {
199            put(key, value);
200            return;
201        }
202
203        int pos = mSize;
204        if (pos >= mKeys.length) {
205            int n = ArrayUtils.idealIntArraySize(pos + 1);
206
207            int[] nkeys = new int[n];
208            boolean[] nvalues = new boolean[n];
209
210            // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n);
211            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
212            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
213
214            mKeys = nkeys;
215            mValues = nvalues;
216        }
217
218        mKeys[pos] = key;
219        mValues[pos] = value;
220        mSize = pos + 1;
221    }
222
223    private static int binarySearch(int[] a, int start, int len, int key) {
224        int high = start + len, low = start - 1, guess;
225
226        while (high - low > 1) {
227            guess = (high + low) / 2;
228
229            if (a[guess] < key)
230                low = guess;
231            else
232                high = guess;
233        }
234
235        if (high == start + len)
236            return ~(start + len);
237        else if (a[high] == key)
238            return high;
239        else
240            return ~high;
241    }
242
243    private int[] mKeys;
244    private boolean[] mValues;
245    private int mSize;
246}
247