LongSparseArray.java revision 8d7d110766d38d445d83e5801b2acec678969016
197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn/* 297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Copyright (C) 2009 The Android Open Source Project 397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * 497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * you may not use this file except in compliance with the License. 697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * You may obtain a copy of the License at 797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * 897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * 1097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Unless required by applicable law or agreed to in writing, software 1197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 1297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * See the License for the specific language governing permissions and 1497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * limitations under the License. 1597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 1697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 1797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackbornpackage android.support.v4.util; 1897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 1997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn/** 2097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * SparseArray mapping longs to Objects. Unlike a normal array of Objects, 218d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * there can be gaps in the indices. It is intended to be more memory efficient 228d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * than using a HashMap to map Longs to Objects, both because it avoids 238d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * auto-boxing keys and its data structure doesn't rely on an extra entry object 248d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * for each mapping. 258d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * 268d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * <p>Note that this container keeps its mappings in an array data structure, 278d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * using a binary search to find keys. The implementation is not intended to be appropriate for 288d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * data structures 298d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 308d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 318d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 328d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 338d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * 348d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * <p>To help with performance, the container includes an optimization when removing 358d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * keys: instead of compacting its array immediately, it leaves the removed entry marked 368d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * as deleted. The entry can then be re-used for the same key, or compacted later in 378d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * a single garbage collection step of all removed entries. This garbage collection will 388d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * need to be performed at any time the array needs to be grown or the the map size or 398d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * entry values are retrieved.</p> 4097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 4197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackbornpublic class LongSparseArray<E> implements Cloneable { 4297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private static final Object DELETED = new Object(); 4397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private boolean mGarbage = false; 4497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 4597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private long[] mKeys; 4697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private Object[] mValues; 4797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private int mSize; 4897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 4997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 5097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Creates a new LongSparseArray containing no mappings. 5197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 5297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray() { 5397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn this(10); 5497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 5597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 5697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 5797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Creates a new LongSparseArray containing no mappings that will not 5897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * require any additional memory allocation to store the specified 5997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * number of mappings. 6097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 6197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray(int initialCapacity) { 6297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn initialCapacity = idealLongArraySize(initialCapacity); 6397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 6497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys = new long[initialCapacity]; 6597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues = new Object[initialCapacity]; 6697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = 0; 6797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 6897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 6997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @Override 7097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 7197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray<E> clone() { 7297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn LongSparseArray<E> clone = null; 7397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn try { 7497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone = (LongSparseArray<E>) super.clone(); 7597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone.mKeys = mKeys.clone(); 7697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone.mValues = mValues.clone(); 7797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } catch (CloneNotSupportedException cnse) { 7897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /* ignore */ 7997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 8097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return clone; 8197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 8297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 8397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 8497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Gets the Object mapped from the specified key, or <code>null</code> 8597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * if no such mapping has been made. 8697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 8797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E get(long key) { 8897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return get(key, null); 8997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 9097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 9197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 9297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Gets the Object mapped from the specified key, or the specified Object 9397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * if no such mapping has been made. 9497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 9597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 9697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E get(long key, E valueIfKeyNotFound) { 9797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int i = binarySearch(mKeys, 0, mSize, key); 9897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 9997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i < 0 || mValues[i] == DELETED) { 10097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return valueIfKeyNotFound; 10197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } else { 10297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return (E) mValues[i]; 10397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 10497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 10597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 10697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 10797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes the mapping from the specified key, if there was any. 10897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 10997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void delete(long key) { 11097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int i = binarySearch(mKeys, 0, mSize, key); 11197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 11297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i >= 0) { 11397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[i] != DELETED) { 11497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = DELETED; 11597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = true; 11697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 11797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 11897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 11997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 12097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 12197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Alias for {@link #delete(long)}. 12297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 12397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void remove(long key) { 12497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn delete(key); 12597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 12697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 12797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 12897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes the mapping at the specified index. 12997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 13097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void removeAt(int index) { 13197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[index] != DELETED) { 13297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[index] = DELETED; 13397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = true; 13497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 13597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 13697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 13797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private void gc() { 13897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "gc start with " + mSize); 13997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 14097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = mSize; 14197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int o = 0; 14297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] keys = mKeys; 14397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] values = mValues; 14497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 14597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < n; i++) { 14697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object val = values[i]; 14797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 14897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (val != DELETED) { 14997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i != o) { 15097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn keys[o] = keys[i]; 15197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[o] = val; 15297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[i] = null; 15397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 15497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 15597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn o++; 15697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 15797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 15897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 15997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = false; 16097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = o; 16197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 16297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "gc end with " + mSize); 16397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 16497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 16597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 16697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Adds a mapping from the specified key to the specified value, 16797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * replacing the previous mapping from the specified key if there 16897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * was one. 16997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 17097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void put(long key, E value) { 17197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int i = binarySearch(mKeys, 0, mSize, key); 17297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 17397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i >= 0) { 17497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 17597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } else { 17697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn i = ~i; 17797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 17897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i < mSize && mValues[i] == DELETED) { 17997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[i] = key; 18097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 18197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return; 18297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 18397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 18497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 18597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 18697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 18797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Search again because indices may have changed. 18897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn i = ~binarySearch(mKeys, 0, mSize, key); 18997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 19097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize >= mKeys.length) { 19297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = idealLongArraySize(mSize + 1); 19397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] nkeys = new long[n]; 19597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] nvalues = new Object[n]; 19697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 19897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 19997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 20097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 20197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys = nkeys; 20297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues = nvalues; 20397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 20497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 20597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize - i != 0) { 20697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "move " + (mSize - i)); 20797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 20897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 20997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 21097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 21197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[i] = key; 21297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 21397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize++; 21497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 21597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 21697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 21797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 21897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns the number of key-value mappings that this LongSparseArray 21997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * currently stores. 22097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 22197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int size() { 22297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 22397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 22497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 22597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 22697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return mSize; 22797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 22897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 22997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 23097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 23197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the key from the <code>index</code>th key-value mapping that this 23297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 23397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 23497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public long keyAt(int index) { 23597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 23697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 23797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 23897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 23997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return mKeys[index]; 24097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 24197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 24297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 24397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 24497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the value from the <code>index</code>th key-value mapping that this 24597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 24697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 24797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 24897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E valueAt(int index) { 24997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 25097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 25197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 25297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 25397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return (E) mValues[index]; 25497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 25597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 25697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 25797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, sets a new 25897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * value for the <code>index</code>th key-value mapping that this 25997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 26097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 26197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void setValueAt(int index, E value) { 26297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 26397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 26497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 26597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 26697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[index] = value; 26797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 26897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 26997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 27097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns the index for which {@link #keyAt} would return the 27197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified key, or a negative number if the specified 27297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * key is not mapped. 27397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 27497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int indexOfKey(long key) { 27597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 27697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 27797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 27897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 27997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return binarySearch(mKeys, 0, mSize, key); 28097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 28197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 28297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 28397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns an index for which {@link #valueAt} would return the 28497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified key, or a negative number if no keys map to the 28597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified value. 28697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Beware that this is a linear search, unlike lookups by key, 28797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * and that multiple keys can map to the same value and this will 28897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * find only one of them. 28997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 29097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int indexOfValue(E value) { 29197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 29297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 29397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 29497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 29597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < mSize; i++) 29697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[i] == value) 29797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return i; 29897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 29997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return -1; 30097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 30197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 30297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 30397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes all key-value mappings from this LongSparseArray. 30497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 30597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void clear() { 30697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = mSize; 30797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] values = mValues; 30897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 30997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < n; i++) { 31097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[i] = null; 31197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 31297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 31397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = 0; 31497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = false; 31597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 31697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 31797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 31897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Puts a key/value pair into the array, optimizing for the case where 31997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the key is greater than all existing keys in the array. 32097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 32197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void append(long key, E value) { 32297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize != 0 && key <= mKeys[mSize - 1]) { 32397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn put(key, value); 32497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return; 32597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 32697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 32797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 32897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 32997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 33097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 33197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int pos = mSize; 33297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (pos >= mKeys.length) { 33397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = idealLongArraySize(pos + 1); 33497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 33597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] nkeys = new long[n]; 33697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] nvalues = new Object[n]; 33797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 33897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 33997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 34097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 34197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 34297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys = nkeys; 34397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues = nvalues; 34497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 34597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 34697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[pos] = key; 34797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[pos] = value; 34897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = pos + 1; 34997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 35097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 35197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private static int binarySearch(long[] a, int start, int len, long key) { 35297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int high = start + len, low = start - 1, guess; 35397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 35497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn while (high - low > 1) { 35597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn guess = (high + low) / 2; 35697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 35797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (a[guess] < key) 35897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn low = guess; 35997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn else 36097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn high = guess; 36197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 36297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 36397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (high == start + len) 36497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return ~(start + len); 36597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn else if (a[high] == key) 36697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return high; 36797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn else 36897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return ~high; 36997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 37097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 37197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public static int idealByteArraySize(int need) { 37297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 4; i < 32; i++) 37397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (need <= (1 << i) - 12) 37497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return (1 << i) - 12; 37597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 37697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return need; 37797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 37897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 37997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public static int idealLongArraySize(int need) { 38097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return idealByteArraySize(need * 8) / 8; 38197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 38297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn} 383