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 * SparseIntArrays map integers to integers.  Unlike a normal array of integers,
23 * there can be gaps in the indices.  It is intended to be more efficient
24 * than using a HashMap to map Integers to Integers.
25 */
26public class SparseIntArray implements Cloneable {
27
28    private int[] mKeys;
29    private int[] mValues;
30    private int mSize;
31
32    /**
33     * Creates a new SparseIntArray containing no mappings.
34     */
35    public SparseIntArray() {
36        this(10);
37    }
38
39    /**
40     * Creates a new SparseIntArray containing no mappings that will not
41     * require any additional memory allocation to store the specified
42     * number of mappings.
43     */
44    public SparseIntArray(int initialCapacity) {
45        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
46
47        mKeys = new int[initialCapacity];
48        mValues = new int[initialCapacity];
49        mSize = 0;
50    }
51
52    @Override
53    public SparseIntArray clone() {
54        SparseIntArray clone = null;
55        try {
56            clone = (SparseIntArray) super.clone();
57            clone.mKeys = mKeys.clone();
58            clone.mValues = mValues.clone();
59        } catch (CloneNotSupportedException cnse) {
60            /* ignore */
61        }
62        return clone;
63    }
64
65    /**
66     * Gets the int mapped from the specified key, or <code>0</code>
67     * if no such mapping has been made.
68     */
69    public int get(int key) {
70        return get(key, 0);
71    }
72
73    /**
74     * Gets the int mapped from the specified key, or the specified value
75     * if no such mapping has been made.
76     */
77    public int get(int key, int valueIfKeyNotFound) {
78        int i = binarySearch(mKeys, 0, mSize, key);
79
80        if (i < 0) {
81            return valueIfKeyNotFound;
82        } else {
83            return mValues[i];
84        }
85    }
86
87    /**
88     * Removes the mapping from the specified key, if there was any.
89     */
90    public void delete(int key) {
91        int i = binarySearch(mKeys, 0, mSize, key);
92
93        if (i >= 0) {
94            removeAt(i);
95        }
96    }
97
98    /**
99     * Removes the mapping at the given index.
100     */
101    public void removeAt(int index) {
102        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
103        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
104        mSize--;
105    }
106
107    /**
108     * Adds a mapping from the specified key to the specified value,
109     * replacing the previous mapping from the specified key if there
110     * was one.
111     */
112    public void put(int key, int value) {
113        int i = binarySearch(mKeys, 0, mSize, key);
114
115        if (i >= 0) {
116            mValues[i] = value;
117        } else {
118            i = ~i;
119
120            if (mSize >= mKeys.length) {
121                int n = ArrayUtils.idealIntArraySize(mSize + 1);
122
123                int[] nkeys = new int[n];
124                int[] nvalues = new int[n];
125
126                // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
127                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
128                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
129
130                mKeys = nkeys;
131                mValues = nvalues;
132            }
133
134            if (mSize - i != 0) {
135                // Log.e("SparseIntArray", "move " + (mSize - i));
136                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
137                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
138            }
139
140            mKeys[i] = key;
141            mValues[i] = value;
142            mSize++;
143        }
144    }
145
146    /**
147     * Returns the number of key-value mappings that this SparseIntArray
148     * currently stores.
149     */
150    public int size() {
151        return mSize;
152    }
153
154    /**
155     * Given an index in the range <code>0...size()-1</code>, returns
156     * the key from the <code>index</code>th key-value mapping that this
157     * SparseIntArray stores.
158     */
159    public int keyAt(int index) {
160        return mKeys[index];
161    }
162
163    /**
164     * Given an index in the range <code>0...size()-1</code>, returns
165     * the value from the <code>index</code>th key-value mapping that this
166     * SparseIntArray stores.
167     */
168    public int valueAt(int index) {
169        return mValues[index];
170    }
171
172    /**
173     * Returns the index for which {@link #keyAt} would return the
174     * specified key, or a negative number if the specified
175     * key is not mapped.
176     */
177    public int indexOfKey(int key) {
178        return binarySearch(mKeys, 0, mSize, key);
179    }
180
181    /**
182     * Returns an index for which {@link #valueAt} would return the
183     * specified key, or a negative number if no keys map to the
184     * specified value.
185     * Beware that this is a linear search, unlike lookups by key,
186     * and that multiple keys can map to the same value and this will
187     * find only one of them.
188     */
189    public int indexOfValue(int value) {
190        for (int i = 0; i < mSize; i++)
191            if (mValues[i] == value)
192                return i;
193
194        return -1;
195    }
196
197    /**
198     * Removes all key-value mappings from this SparseIntArray.
199     */
200    public void clear() {
201        mSize = 0;
202    }
203
204    /**
205     * Puts a key/value pair into the array, optimizing for the case where
206     * the key is greater than all existing keys in the array.
207     */
208    public void append(int key, int value) {
209        if (mSize != 0 && key <= mKeys[mSize - 1]) {
210            put(key, value);
211            return;
212        }
213
214        int pos = mSize;
215        if (pos >= mKeys.length) {
216            int n = ArrayUtils.idealIntArraySize(pos + 1);
217
218            int[] nkeys = new int[n];
219            int[] nvalues = new int[n];
220
221            // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
222            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
223            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
224
225            mKeys = nkeys;
226            mValues = nvalues;
227        }
228
229        mKeys[pos] = key;
230        mValues[pos] = value;
231        mSize = pos + 1;
232    }
233
234    private static int binarySearch(int[] a, int start, int len, int key) {
235        int high = start + len, low = start - 1, guess;
236
237        while (high - low > 1) {
238            guess = (high + low) / 2;
239
240            if (a[guess] < key)
241                low = guess;
242            else
243                high = guess;
244        }
245
246        if (high == start + len)
247            return ~(start + len);
248        else if (a[high] == key)
249            return high;
250        else
251            return ~high;
252    }
253}
254