SparseLongArray.java revision c40d1153e060fdd2024be84cf22d4b856efa02e0 
1/*
2 * Copyright (C) 2011 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 * SparseLongArrays map integers to longs.  Unlike a normal array of longs,
23 * there can be gaps in the indices.  It is intended to be more efficient
24 * than using a HashMap to map Integers to Longs.
25 */
26public class SparseLongArray implements Cloneable {
27
28    private int[] mKeys;
29    private long[] mValues;
30    private int mSize;
31
32    /**
33     * Creates a new SparseLongArray containing no mappings.
34     */
35    public SparseLongArray() {
36        this(10);
37    }
38
39    /**
40     * Creates a new SparseLongArray containing no mappings that will not
41     * require any additional memory allocation to store the specified
42     * number of mappings.
43     */
44    public SparseLongArray(int initialCapacity) {
45        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
46
47        mKeys = new int[initialCapacity];
48        mValues = new long[initialCapacity];
49        mSize = 0;
50    }
51
52    @Override
53    public SparseLongArray clone() {
54        SparseLongArray clone = null;
55        try {
56            clone = (SparseLongArray) 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 long mapped from the specified key, or <code>0</code>
67     * if no such mapping has been made.
68     */
69    public long get(int key) {
70        return get(key, 0);
71    }
72
73    /**
74     * Gets the long mapped from the specified key, or the specified value
75     * if no such mapping has been made.
76     */
77    public long get(int key, long 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, long 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                growKeyAndValueArrays(mSize + 1);
122            }
123
124            if (mSize - i != 0) {
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 SparseIntArray
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     * SparseLongArray 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     * SparseLongArray stores.
156     */
157    public long 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(long 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 SparseIntArray.
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, long 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            growKeyAndValueArrays(pos + 1);
206        }
207
208        mKeys[pos] = key;
209        mValues[pos] = value;
210        mSize = pos + 1;
211    }
212
213    private void growKeyAndValueArrays(int minNeededSize) {
214        int n = ArrayUtils.idealLongArraySize(minNeededSize);
215
216        int[] nkeys = new int[n];
217        long[] nvalues = new long[n];
218
219        System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
220        System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
221
222        mKeys = nkeys;
223        mValues = nvalues;
224    }
225
226    private static int binarySearch(int[] a, int start, int len, long key) {
227        int high = start + len, low = start - 1, guess;
228
229        while (high - low > 1) {
230            guess = (high + low) / 2;
231
232            if (a[guess] < key)
233                low = guess;
234            else
235                high = guess;
236        }
237
238        if (high == start + len)
239            return ~(start + len);
240        else if (a[high] == key)
241            return high;
242        else
243            return ~high;
244    }
245}
246