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