1fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy/* 2fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Copyright (C) 2009 The Android Open Source Project 3fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * 4fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Licensed under the Apache License, Version 2.0 (the "License"); 5fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * you may not use this file except in compliance with the License. 6fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * You may obtain a copy of the License at 7fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * 8fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * http://www.apache.org/licenses/LICENSE-2.0 9fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * 10fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Unless required by applicable law or agreed to in writing, software 11fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * distributed under the License is distributed on an "AS IS" BASIS, 12fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * See the License for the specific language governing permissions and 14fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * limitations under the License. 15fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 16fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 17fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guypackage android.util; 18fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 19fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guyimport com.android.internal.util.ArrayUtils; 20776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport com.android.internal.util.GrowingArrayUtils; 21776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski 22776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinskiimport libcore.util.EmptyArray; 23fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 24fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy/** 259c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * SparseArray mapping longs to Objects. Unlike a normal array of Objects, 26b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * there can be gaps in the indices. It is intended to be more memory efficient 27b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * than using a HashMap to map Longs to Objects, both because it avoids 28b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * auto-boxing keys and its data structure doesn't rely on an extra entry object 29b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * for each mapping. 30b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * 31b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * <p>Note that this container keeps its mappings in an array data structure, 32b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * using a binary search to find keys. The implementation is not intended to be appropriate for 33b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * data structures 34b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 35b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 36b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 37b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 38b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * 39b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * <p>To help with performance, the container includes an optimization when removing 40b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * keys: instead of compacting its array immediately, it leaves the removed entry marked 41b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * as deleted. The entry can then be re-used for the same key, or compacted later in 42b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * a single garbage collection step of all removed entries. This garbage collection will 43b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * need to be performed at any time the array needs to be grown or the the map size or 44b993f41eb2f165425dfdf0f93ea0b1e354eca837Dianne Hackborn * entry values are retrieved.</p> 455771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 465771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>It is possible to iterate over the items in this container using 475771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using 485771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <code>keyAt(int)</code> with ascending values of the index will return the 495771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * keys in ascending order, or the values corresponding to the keys in ascending 50ebb47950f21d3c41955a591000dfb1f195e746feNewton Allen * order in the case of <code>valueAt(int)</code>.</p> 51fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 529c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackbornpublic class LongSparseArray<E> implements Cloneable { 53fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private static final Object DELETED = new Object(); 54fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private boolean mGarbage = false; 55fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 569c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private long[] mKeys; 579c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private Object[] mValues; 589c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private int mSize; 599c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 60fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 619c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Creates a new LongSparseArray containing no mappings. 62fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 63fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public LongSparseArray() { 64fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy this(10); 65fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 66fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 67fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 689c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Creates a new LongSparseArray containing no mappings that will not 69fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * require any additional memory allocation to store the specified 70f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * number of mappings. If you supply an initial capacity of 0, the 71f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * sparse array will be initialized with a light-weight representation 72f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn * not requiring any additional array allocations. 73fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 74fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public LongSparseArray(int initialCapacity) { 75f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (initialCapacity == 0) { 76776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = EmptyArray.LONG; 77776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = EmptyArray.OBJECT; 78f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } else { 79776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = ArrayUtils.newUnpaddedLongArray(initialCapacity); 80776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); 81f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 82fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = 0; 83fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 849c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 859c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @Override 869c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 879c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn public LongSparseArray<E> clone() { 889c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn LongSparseArray<E> clone = null; 899c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn try { 909c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone = (LongSparseArray<E>) super.clone(); 919c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone.mKeys = mKeys.clone(); 929c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone.mValues = mValues.clone(); 939c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } catch (CloneNotSupportedException cnse) { 949c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn /* ignore */ 958f1bfe1a7cef702fd74e5405443e9fdb7c5e7556Adam Powell } 969c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn return clone; 978f1bfe1a7cef702fd74e5405443e9fdb7c5e7556Adam Powell } 98fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 99fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 100fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Gets the Object mapped from the specified key, or <code>null</code> 101fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * if no such mapping has been made. 102fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 103fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E get(long key) { 104fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return get(key, null); 105fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 106fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 107fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 108fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Gets the Object mapped from the specified key, or the specified Object 109fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * if no such mapping has been made. 110fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 1119c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 112fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E get(long key, E valueIfKeyNotFound) { 1133e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 114fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 115fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i < 0 || mValues[i] == DELETED) { 116fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return valueIfKeyNotFound; 117fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } else { 118fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return (E) mValues[i]; 119fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 120fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 121fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 122fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 123fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Removes the mapping from the specified key, if there was any. 124fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 125fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void delete(long key) { 1263e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 127fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 128fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i >= 0) { 129fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mValues[i] != DELETED) { 130fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = DELETED; 131fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = true; 132fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 133fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 134fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 135fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 136fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 137fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Alias for {@link #delete(long)}. 138fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 139fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void remove(long key) { 140fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy delete(key); 141fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 142fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 1439c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn /** 1449c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Removes the mapping at the specified index. 1459c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn */ 1469c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn public void removeAt(int index) { 1479c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn if (mValues[index] != DELETED) { 1489c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn mValues[index] = DELETED; 1499c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn mGarbage = true; 1509c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } 1519c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } 1529c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 153fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private void gc() { 154fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "gc start with " + mSize); 155fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 156fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int n = mSize; 157fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int o = 0; 158fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy long[] keys = mKeys; 159fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] values = mValues; 160fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 161fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < n; i++) { 162fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object val = values[i]; 163fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 164fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (val != DELETED) { 165fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i != o) { 166fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy keys[o] = keys[i]; 167fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy values[o] = val; 1689c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn values[i] = null; 169fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 170fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 171fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy o++; 172fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 173fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 174fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 175fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = false; 176fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = o; 177fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 178fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "gc end with " + mSize); 179fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 180fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 181fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 182fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Adds a mapping from the specified key to the specified value, 183fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * replacing the previous mapping from the specified key if there 184fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * was one. 185fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 186fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void put(long key, E value) { 1873e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 188fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 189fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i >= 0) { 190fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = value; 191fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } else { 192fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy i = ~i; 193fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 194fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i < mSize && mValues[i] == DELETED) { 195fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys[i] = key; 196fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = value; 197fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return; 198fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 199fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 200fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage && mSize >= mKeys.length) { 201fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 202fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 203fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Search again because indices may have changed. 2043e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); 205fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 206fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 207776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 208776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 209fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize++; 210fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 211fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 212fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 213fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 2149c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Returns the number of key-value mappings that this LongSparseArray 215fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * currently stores. 216fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 217fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int size() { 218fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 219fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 220fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 221fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 222fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return mSize; 223fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 224fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 225fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 226fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, returns 227fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the key from the <code>index</code>th key-value mapping that this 2289c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 2295771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 2305771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>The keys corresponding to indices in ascending order are guaranteed to 2315771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * be in ascending order, e.g., <code>keyAt(0)</code> will return the 2325771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * smallest key and <code>keyAt(size()-1)</code> will return the largest 2335771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * key.</p> 234fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 235fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public long keyAt(int index) { 236fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 237fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 238fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 239fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 240fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return mKeys[index]; 241fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 242fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 243fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 244fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, returns 245fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the value from the <code>index</code>th key-value mapping that this 2469c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 2475771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * 2485771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <p>The values corresponding to indices in ascending order are guaranteed 2495771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * to be associated with keys in ascending order, e.g., 2505771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * <code>valueAt(0)</code> will return the value associated with the 2515771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * smallest key and <code>valueAt(size()-1)</code> will return the value 2525771302ca13c31cb85f17bc58da8f6f8227c9b85Flavio Lerda * associated with the largest key.</p> 253fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 2549c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 255fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E valueAt(int index) { 256fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 257fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 258fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 259fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 260fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return (E) mValues[index]; 261fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 262fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 263fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 264fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, sets a new 265fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * value for the <code>index</code>th key-value mapping that this 2669c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 267fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 268fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void setValueAt(int index, E value) { 269fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 270fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 271fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 272fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 273fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[index] = value; 274fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 275fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 276fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 277fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Returns the index for which {@link #keyAt} would return the 278fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified key, or a negative number if the specified 279fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * key is not mapped. 280fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 281fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int indexOfKey(long key) { 282fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 283fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 284fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 285fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 2863e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return ContainerHelpers.binarySearch(mKeys, mSize, key); 287fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 288fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 289fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 290fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Returns an index for which {@link #valueAt} would return the 291fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified key, or a negative number if no keys map to the 292fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified value. 293fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Beware that this is a linear search, unlike lookups by key, 294fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * and that multiple keys can map to the same value and this will 295fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * find only one of them. 296fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 297fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int indexOfValue(E value) { 298fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 299fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 300fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 301fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 302fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < mSize; i++) 303fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mValues[i] == value) 304fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return i; 305fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 306fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return -1; 307fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 308fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 309fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 3109c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Removes all key-value mappings from this LongSparseArray. 311fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 312fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void clear() { 313fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int n = mSize; 314fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] values = mValues; 315fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 316fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < n; i++) { 317fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy values[i] = null; 318fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 319fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 320fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = 0; 321fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = false; 322fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 323fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 324fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 325fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Puts a key/value pair into the array, optimizing for the case where 326fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the key is greater than all existing keys in the array. 327fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 328fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void append(long key, E value) { 329fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mSize != 0 && key <= mKeys[mSize - 1]) { 330fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy put(key, value); 331fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return; 332fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 333fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 334fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage && mSize >= mKeys.length) { 335fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 336fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 337fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 338776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mKeys = GrowingArrayUtils.append(mKeys, mSize, key); 339776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mValues = GrowingArrayUtils.append(mValues, mSize, value); 340776abc24cdd18610232a50b997cce3cffa74609bAdam Lesinski mSize++; 341fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 342fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 3433e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn /** 3443e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * {@inheritDoc} 3453e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * 3463e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 3473e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * this map contains itself as a value, the string "(this Map)" 3483e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * will appear in its place. 3493e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn */ 3503e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn @Override 3513e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn public String toString() { 3523e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (size() <= 0) { 3533e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return "{}"; 354fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 355fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 3563e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 3573e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('{'); 3583e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn for (int i=0; i<mSize; i++) { 3593e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (i > 0) { 3603e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(", "); 3613e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 3623e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn long key = keyAt(i); 3633e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(key); 3643e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('='); 3653e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn Object value = valueAt(i); 3663e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (value != this) { 3673e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append(value); 3683e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } else { 3693e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append("(this Map)"); 3703e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 3713e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 3723e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn buffer.append('}'); 3733e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return buffer.toString(); 374fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 3759c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn} 376