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/** 202290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * SparseArray mapping longs to Objects, a version of the platform's 212290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@link android.util.LongSparseArray} that can be used on older versions of the 222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * platform. Unlike a normal array of Objects, 238d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * there can be gaps in the indices. It is intended to be more memory efficient 248d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * than using a HashMap to map Longs to Objects, both because it avoids 258d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * auto-boxing keys and its data structure doesn't rely on an extra entry object 268d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * for each mapping. 278d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * 288d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * <p>Note that this container keeps its mappings in an array data structure, 298d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * using a binary search to find keys. The implementation is not intended to be appropriate for 308d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * data structures 318d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * that may contain large numbers of items. It is generally slower than a traditional 328d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * HashMap, since lookups require a binary search and adds and removes require inserting 338d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * and deleting entries in the array. For containers holding up to hundreds of items, 348d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * the performance difference is not significant, less than 50%.</p> 358d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * 368d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * <p>To help with performance, the container includes an optimization when removing 378d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * keys: instead of compacting its array immediately, it leaves the removed entry marked 388d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * as deleted. The entry can then be re-used for the same key, or compacted later in 398d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * a single garbage collection step of all removed entries. This garbage collection will 408d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * need to be performed at any time the array needs to be grown or the the map size or 418d7d110766d38d445d83e5801b2acec678969016Dianne Hackborn * entry values are retrieved.</p> 4297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 4397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackbornpublic class LongSparseArray<E> implements Cloneable { 4497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private static final Object DELETED = new Object(); 4597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private boolean mGarbage = false; 4697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 4797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private long[] mKeys; 4897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private Object[] mValues; 4997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private int mSize; 5097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 5197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 5297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Creates a new LongSparseArray containing no mappings. 5397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 5497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray() { 5597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn this(10); 5697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 5797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 5897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 5997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Creates a new LongSparseArray containing no mappings that will not 6097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * require any additional memory allocation to store the specified 612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * number of mappings. If you supply an initial capacity of 0, the 622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * sparse array will be initialized with a light-weight representation 632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * not requiring any additional array allocations. 6497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 6597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray(int initialCapacity) { 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (initialCapacity == 0) { 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = ContainerHelpers.EMPTY_LONGS; 682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = ContainerHelpers.EMPTY_OBJECTS; 692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn initialCapacity = ContainerHelpers.idealLongArraySize(initialCapacity); 712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = new long[initialCapacity]; 722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = new Object[initialCapacity]; 732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 7497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = 0; 7597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 7697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 7797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @Override 7897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 7997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public LongSparseArray<E> clone() { 8097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn LongSparseArray<E> clone = null; 8197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn try { 8297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone = (LongSparseArray<E>) super.clone(); 8397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone.mKeys = mKeys.clone(); 8497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn clone.mValues = mValues.clone(); 8597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } catch (CloneNotSupportedException cnse) { 8697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /* ignore */ 8797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 8897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return clone; 8997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 9097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 9197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 9297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Gets the Object mapped from the specified key, or <code>null</code> 9397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * if no such mapping has been made. 9497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 9597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E get(long key) { 9697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return get(key, null); 9797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 9897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 9997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 10097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Gets the Object mapped from the specified key, or the specified Object 10197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * if no such mapping has been made. 10297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 10397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 10497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E get(long key, E valueIfKeyNotFound) { 1052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 10697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 10797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i < 0 || mValues[i] == DELETED) { 10897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return valueIfKeyNotFound; 10997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } else { 11097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return (E) mValues[i]; 11197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 11297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 11397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 11497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 11597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes the mapping from the specified key, if there was any. 11697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 11797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void delete(long key) { 1182290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 11997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 12097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i >= 0) { 12197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[i] != DELETED) { 12297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = DELETED; 12397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = true; 12497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 12597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 12697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 12797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 12897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 12997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Alias for {@link #delete(long)}. 13097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 13197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void remove(long key) { 13297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn delete(key); 13397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 13497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 13597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 13697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes the mapping at the specified index. 13797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 13897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void removeAt(int index) { 13997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[index] != DELETED) { 14097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[index] = DELETED; 14197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = true; 14297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 14397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 14497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 14597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn private void gc() { 14697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "gc start with " + mSize); 14797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 14897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = mSize; 14997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int o = 0; 15097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] keys = mKeys; 15197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] values = mValues; 15297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 15397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < n; i++) { 15497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object val = values[i]; 15597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 15697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (val != DELETED) { 15797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i != o) { 15897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn keys[o] = keys[i]; 15997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[o] = val; 16097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[i] = null; 16197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 16297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 16397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn o++; 16497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 16597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 16697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 16797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = false; 16897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = o; 16997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 17097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "gc end with " + mSize); 17197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 17297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 17397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 17497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Adds a mapping from the specified key to the specified value, 17597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * replacing the previous mapping from the specified key if there 17697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * was one. 17797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 17897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void put(long key, E value) { 1792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 18097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 18197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i >= 0) { 18297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 18397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } else { 18497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn i = ~i; 18597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 18697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (i < mSize && mValues[i] == DELETED) { 18797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[i] = key; 18897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 18997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return; 19097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 19197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 19397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 19497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Search again because indices may have changed. 1962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); 19797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 19897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 19997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize >= mKeys.length) { 2002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealLongArraySize(mSize + 1); 20197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 20297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] nkeys = new long[n]; 20397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] nvalues = new Object[n]; 20497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 20597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 20697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 20797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 20897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 20997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys = nkeys; 21097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues = nvalues; 21197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 21297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 21397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize - i != 0) { 21497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "move " + (mSize - i)); 21597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 21697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 21797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 21897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 21997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[i] = key; 22097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[i] = value; 22197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize++; 22297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 22397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 22497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 22597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 22697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns the number of key-value mappings that this LongSparseArray 22797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * currently stores. 22897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 22997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int size() { 23097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 23197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 23297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 23397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 23497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return mSize; 23597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 23697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 23797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 23897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 23997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the key from the <code>index</code>th key-value mapping that this 24097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 24197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 24297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public long keyAt(int index) { 24397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 24497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 24597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 24697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 24797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return mKeys[index]; 24897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 24997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 25097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 25197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 25297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the value from the <code>index</code>th key-value mapping that this 25397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 25497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 25597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn @SuppressWarnings("unchecked") 25697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public E valueAt(int index) { 25797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 25897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 25997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 26097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 26197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return (E) mValues[index]; 26297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 26397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 26497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 26597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, sets a new 26697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * value for the <code>index</code>th key-value mapping that this 26797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * LongSparseArray stores. 26897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 26997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void setValueAt(int index, E value) { 27097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 27197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 27297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 27397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 27497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[index] = value; 27597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 27697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 27797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 27897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns the index for which {@link #keyAt} would return the 27997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified key, or a negative number if the specified 28097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * key is not mapped. 28197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 28297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int indexOfKey(long key) { 28397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 28497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 28597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 28697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 2872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ContainerHelpers.binarySearch(mKeys, mSize, key); 28897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 28997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 29097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 29197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Returns an index for which {@link #valueAt} would return the 29297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified key, or a negative number if no keys map to the 29397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * specified value. 29497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Beware that this is a linear search, unlike lookups by key, 29597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * and that multiple keys can map to the same value and this will 29697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * find only one of them. 29797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 29897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public int indexOfValue(E value) { 29997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage) { 30097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 30197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 30297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 30397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < mSize; i++) 30497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mValues[i] == value) 30597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return i; 30697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 30797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return -1; 30897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 30997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 31097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 31197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Removes all key-value mappings from this LongSparseArray. 31297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 31397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void clear() { 31497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int n = mSize; 31597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] values = mValues; 31697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 31797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn for (int i = 0; i < n; i++) { 31897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn values[i] = null; 31997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 32097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 32197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = 0; 32297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mGarbage = false; 32397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 32497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 32597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn /** 32697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * Puts a key/value pair into the array, optimizing for the case where 32797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn * the key is greater than all existing keys in the array. 32897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn */ 32997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn public void append(long key, E value) { 33097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mSize != 0 && key <= mKeys[mSize - 1]) { 33197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn put(key, value); 33297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn return; 33397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 33497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 33597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 33697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn gc(); 33797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 33897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 33997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn int pos = mSize; 34097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn if (pos >= mKeys.length) { 3412290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealLongArraySize(pos + 1); 34297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 34397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn long[] nkeys = new long[n]; 34497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn Object[] nvalues = new Object[n]; 34597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 34697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 34797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 34897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 34997b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 35097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys = nkeys; 35197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues = nvalues; 35297b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 35397b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 35497b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mKeys[pos] = key; 35597b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mValues[pos] = value; 35697b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn mSize = pos + 1; 35797b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 35897b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 3592290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3602290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 3612290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3622290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 3632290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this map contains itself as a value, the string "(this Map)" 3642290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will appear in its place. 3652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 3672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public String toString() { 3682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size() <= 0) { 3692290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return "{}"; 37097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 37197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn 3722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 3732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('{'); 3742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 3752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (i > 0) { 3762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(", "); 3772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3782290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn long key = keyAt(i); 3792290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(key); 3802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('='); 3812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = valueAt(i); 3822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value != this) { 3832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(value); 3842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 3852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 3862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 3882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('}'); 3892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return buffer.toString(); 39097b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn } 39197b687d492c63a6a016f420835d5457d8b4b55b1Dianne Hackborn} 392