1 /*
2  * Copyright (C) 2007 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 
17 package android.util;
18 
19 import android.compat.annotation.UnsupportedAppUsage;
20 import android.os.Parcel;
21 
22 import com.android.internal.util.ArrayUtils;
23 import com.android.internal.util.GrowingArrayUtils;
24 import com.android.internal.util.Preconditions;
25 
26 /**
27  * Map of {@code long} to {@code long}. Unlike a normal array of longs, there
28  * can be gaps in the indices. It is intended to be more memory efficient than using a
29  * {@code HashMap}, both because it avoids
30  * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
31  * for each mapping.
32  *
33  * <p>Note that this container keeps its mappings in an array data structure,
34  * using a binary search to find keys.  The implementation is not intended to be appropriate for
35  * data structures
36  * that may contain large numbers of items.  It is generally slower than a traditional
37  * HashMap, since lookups require a binary search and adds and removes require inserting
38  * and deleting entries in the array.  For containers holding up to hundreds of items,
39  * the performance difference is not significant, less than 50%.</p>
40  *
41  * <p>It is possible to iterate over the items in this container using
42  * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
43  * <code>keyAt(int)</code> with ascending values of the index will return the
44  * keys in ascending order, or the values corresponding to the keys in ascending
45  * order in the case of <code>valueAt(int)</code>.</p>
46  *
47  * @hide
48  */
49 @android.ravenwood.annotation.RavenwoodKeepWholeClass
50 public class LongSparseLongArray implements Cloneable {
51     @UnsupportedAppUsage(maxTargetSdk = 28) // The type isn't even public.
52     private long[] mKeys;
53     @UnsupportedAppUsage(maxTargetSdk = 28) // The type isn't even public.
54     private long[] mValues;
55     @UnsupportedAppUsage(maxTargetSdk = 28) // The type isn't even public.
56     private int mSize;
57 
58     /**
59      * Creates a new SparseLongArray containing no mappings.
60      */
LongSparseLongArray()61     public LongSparseLongArray() {
62         this(10);
63     }
64 
65     /**
66      * Creates a new SparseLongArray containing no mappings that will not
67      * require any additional memory allocation to store the specified
68      * number of mappings.  If you supply an initial capacity of 0, the
69      * sparse array will be initialized with a light-weight representation
70      * not requiring any additional array allocations.
71      */
LongSparseLongArray(int initialCapacity)72     public LongSparseLongArray(int initialCapacity) {
73         if (initialCapacity == 0) {
74             mKeys = EmptyArray.LONG;
75             mValues = EmptyArray.LONG;
76         } else {
77             mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity);
78             mValues = new long[mKeys.length];
79         }
80         mSize = 0;
81     }
82 
83     @Override
clone()84     public LongSparseLongArray clone() {
85         LongSparseLongArray clone = null;
86         try {
87             clone = (LongSparseLongArray) super.clone();
88             clone.mKeys = mKeys.clone();
89             clone.mValues = mValues.clone();
90         } catch (CloneNotSupportedException cnse) {
91             /* ignore */
92         }
93         return clone;
94     }
95 
96     /**
97      * Gets the long mapped from the specified key, or <code>0</code>
98      * if no such mapping has been made.
99      */
get(long key)100     public long get(long key) {
101         return get(key, 0);
102     }
103 
104     /**
105      * Gets the long mapped from the specified key, or the specified value
106      * if no such mapping has been made.
107      */
get(long key, long valueIfKeyNotFound)108     public long get(long key, long valueIfKeyNotFound) {
109         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
110 
111         if (i < 0) {
112             return valueIfKeyNotFound;
113         } else {
114             return mValues[i];
115         }
116     }
117 
118     /**
119      * Removes the mapping from the specified key, if there was any.
120      */
delete(long key)121     public void delete(long key) {
122         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
123 
124         if (i >= 0) {
125             removeAt(i);
126         }
127     }
128 
129     /**
130      * Removes the mapping at the given index.
131      */
removeAt(int index)132     public void removeAt(int index) {
133         System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
134         System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
135         mSize--;
136     }
137 
138     /**
139      * Adds a mapping from the specified key to the specified value,
140      * replacing the previous mapping from the specified key if there
141      * was one.
142      */
put(long key, long value)143     public void put(long key, long value) {
144         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
145 
146         if (i >= 0) {
147             mValues[i] = value;
148         } else {
149             i = ~i;
150 
151             mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
152             mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
153             mSize++;
154         }
155     }
156 
157     /**
158      * Returns the number of key-value mappings that this SparseIntArray
159      * currently stores.
160      */
size()161     public int size() {
162         return mSize;
163     }
164 
165     /**
166      * Given an index in the range <code>0...size()-1</code>, returns
167      * the key from the <code>index</code>th key-value mapping that this
168      * SparseLongArray stores.
169      *
170      * <p>The keys corresponding to indices in ascending order are guaranteed to
171      * be in ascending order, e.g., <code>keyAt(0)</code> will return the
172      * smallest key and <code>keyAt(size()-1)</code> will return the largest
173      * key.</p>
174      *
175      * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for
176      * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an
177      * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting
178      * {@link android.os.Build.VERSION_CODES#Q} and later.</p>
179      */
keyAt(int index)180     public long keyAt(int index) {
181         if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
182             // The array might be slightly bigger than mSize, in which case, indexing won't fail.
183             // Check if exception should be thrown outside of the critical path.
184             throw new ArrayIndexOutOfBoundsException(index);
185         }
186         return mKeys[index];
187     }
188 
189     /**
190      * Given an index in the range <code>0...size()-1</code>, returns
191      * the value from the <code>index</code>th key-value mapping that this
192      * SparseLongArray stores.
193      *
194      * <p>The values corresponding to indices in ascending order are guaranteed
195      * to be associated with keys in ascending order, e.g.,
196      * <code>valueAt(0)</code> will return the value associated with the
197      * smallest key and <code>valueAt(size()-1)</code> will return the value
198      * associated with the largest key.</p>
199      *
200      * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for
201      * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an
202      * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting
203      * {@link android.os.Build.VERSION_CODES#Q} and later.</p>
204      */
valueAt(int index)205     public long valueAt(int index) {
206         if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {
207             // The array might be slightly bigger than mSize, in which case, indexing won't fail.
208             // Check if exception should be thrown outside of the critical path.
209             throw new ArrayIndexOutOfBoundsException(index);
210         }
211         return mValues[index];
212     }
213 
214     /**
215      * Returns the index for which {@link #keyAt} would return the
216      * specified key, or a negative number if the specified
217      * key is not mapped.
218      */
indexOfKey(long key)219     public int indexOfKey(long key) {
220         return ContainerHelpers.binarySearch(mKeys, mSize, key);
221     }
222 
223     /**
224      * Returns an index for which {@link #valueAt} would return the
225      * specified key, or a negative number if no keys map to the
226      * specified value.
227      * Beware that this is a linear search, unlike lookups by key,
228      * and that multiple keys can map to the same value and this will
229      * find only one of them.
230      */
indexOfValue(long value)231     public int indexOfValue(long value) {
232         for (int i = 0; i < mSize; i++)
233             if (mValues[i] == value)
234                 return i;
235 
236         return -1;
237     }
238 
239     /**
240      * Removes all key-value mappings from this SparseIntArray.
241      */
clear()242     public void clear() {
243         mSize = 0;
244     }
245 
246     /**
247      * Puts a key/value pair into the array, optimizing for the case where
248      * the key is greater than all existing keys in the array.
249      */
append(long key, long value)250     public void append(long key, long value) {
251         if (mSize != 0 && key <= mKeys[mSize - 1]) {
252             put(key, value);
253             return;
254         }
255 
256         mKeys = GrowingArrayUtils.append(mKeys, mSize, key);
257         mValues = GrowingArrayUtils.append(mValues, mSize, value);
258         mSize++;
259     }
260 
261     /**
262      * {@inheritDoc}
263      *
264      * <p>This implementation composes a string by iterating over its mappings.
265      */
266     @Override
toString()267     public String toString() {
268         if (size() <= 0) {
269             return "{}";
270         }
271 
272         StringBuilder buffer = new StringBuilder(mSize * 28);
273         buffer.append('{');
274         for (int i=0; i<mSize; i++) {
275             if (i > 0) {
276                 buffer.append(", ");
277             }
278             long key = keyAt(i);
279             buffer.append(key);
280             buffer.append('=');
281             long value = valueAt(i);
282             buffer.append(value);
283         }
284         buffer.append('}');
285         return buffer.toString();
286     }
287 
288     /**
289      * @hide
290      */
291     public static class Parcelling implements
292             com.android.internal.util.Parcelling<LongSparseLongArray> {
293         @Override
parcel(LongSparseLongArray array, Parcel dest, int parcelFlags)294         public void parcel(LongSparseLongArray array, Parcel dest, int parcelFlags) {
295             if (array == null) {
296                 dest.writeInt(-1);
297                 return;
298             }
299 
300             dest.writeInt(array.mSize);
301             dest.writeLongArray(array.mKeys);
302             dest.writeLongArray(array.mValues);
303         }
304 
305         @Override
unparcel(Parcel source)306         public LongSparseLongArray unparcel(Parcel source) {
307             int size = source.readInt();
308             if (size == -1) {
309                 return null;
310             }
311 
312             LongSparseLongArray array = new LongSparseLongArray(0);
313 
314             array.mSize = size;
315             array.mKeys = source.createLongArray();
316             array.mValues = source.createLongArray();
317 
318             // Make sure array is valid
319             Preconditions.checkArgument(array.mKeys.length >= size);
320             Preconditions.checkArgument(array.mValues.length >= size);
321 
322             if (size > 0) {
323                 long last = array.mKeys[0];
324                 for (int i = 1; i < size; i++) {
325                     Preconditions.checkArgument(last < array.mKeys[i]);
326                 }
327             }
328 
329             return array;
330         }
331     }
332 }
333