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; 20fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 21fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy/** 229c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * SparseArray mapping longs to Objects. Unlike a normal array of Objects, 23fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * there can be gaps in the indices. It is intended to be more efficient 24fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * than using a HashMap to map Longs to Objects. 25fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 269c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackbornpublic class LongSparseArray<E> implements Cloneable { 27fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private static final Object DELETED = new Object(); 28fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private boolean mGarbage = false; 29fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 309c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private long[] mKeys; 319c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private Object[] mValues; 329c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn private int mSize; 339c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 34fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 359c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Creates a new LongSparseArray containing no mappings. 36fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 37fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public LongSparseArray() { 38fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy this(10); 39fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 40fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 41fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 429c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Creates a new LongSparseArray containing no mappings that will not 43fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * require any additional memory allocation to store the specified 44fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * number of mappings. 45fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 46fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public LongSparseArray(int initialCapacity) { 479c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 48fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 49fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys = new long[initialCapacity]; 50fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues = new Object[initialCapacity]; 51fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = 0; 52fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 539c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 549c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @Override 559c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 569c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn public LongSparseArray<E> clone() { 579c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn LongSparseArray<E> clone = null; 589c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn try { 599c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone = (LongSparseArray<E>) super.clone(); 609c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone.mKeys = mKeys.clone(); 619c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn clone.mValues = mValues.clone(); 629c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } catch (CloneNotSupportedException cnse) { 639c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn /* ignore */ 648f1bfe1a7cef702fd74e5405443e9fdb7c5e7556Adam Powell } 659c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn return clone; 668f1bfe1a7cef702fd74e5405443e9fdb7c5e7556Adam Powell } 67fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 68fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 69fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Gets the Object mapped from the specified key, or <code>null</code> 70fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * if no such mapping has been made. 71fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 72fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E get(long key) { 73fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return get(key, null); 74fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 75fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 76fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 77fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Gets the Object mapped from the specified key, or the specified Object 78fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * if no such mapping has been made. 79fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 809c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 81fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E get(long key, E valueIfKeyNotFound) { 82fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int i = binarySearch(mKeys, 0, mSize, key); 83fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 84fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i < 0 || mValues[i] == DELETED) { 85fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return valueIfKeyNotFound; 86fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } else { 87fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return (E) mValues[i]; 88fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 89fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 90fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 91fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 92fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Removes the mapping from the specified key, if there was any. 93fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 94fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void delete(long key) { 95fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int i = binarySearch(mKeys, 0, mSize, key); 96fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 97fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i >= 0) { 98fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mValues[i] != DELETED) { 99fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = DELETED; 100fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = true; 101fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 102fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 103fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 104fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 105fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 106fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Alias for {@link #delete(long)}. 107fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 108fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void remove(long key) { 109fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy delete(key); 110fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 111fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 1129c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn /** 1139c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Removes the mapping at the specified index. 1149c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn */ 1159c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn public void removeAt(int index) { 1169c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn if (mValues[index] != DELETED) { 1179c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn mValues[index] = DELETED; 1189c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn mGarbage = true; 1199c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } 1209c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn } 1219c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn 122fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private void gc() { 123fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "gc start with " + mSize); 124fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 125fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int n = mSize; 126fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int o = 0; 127fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy long[] keys = mKeys; 128fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] values = mValues; 129fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 130fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < n; i++) { 131fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object val = values[i]; 132fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 133fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (val != DELETED) { 134fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i != o) { 135fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy keys[o] = keys[i]; 136fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy values[o] = val; 1379c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn values[i] = null; 138fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 139fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 140fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy o++; 141fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 142fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 143fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 144fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = false; 145fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = o; 146fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 147fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "gc end with " + mSize); 148fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 149fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 150fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 151fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Adds a mapping from the specified key to the specified value, 152fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * replacing the previous mapping from the specified key if there 153fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * was one. 154fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 155fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void put(long key, E value) { 156fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int i = binarySearch(mKeys, 0, mSize, key); 157fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 158fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i >= 0) { 159fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = value; 160fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } else { 161fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy i = ~i; 162fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 163fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (i < mSize && mValues[i] == DELETED) { 164fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys[i] = key; 165fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = value; 166fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return; 167fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 168fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 169fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage && mSize >= mKeys.length) { 170fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 171fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 172fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Search again because indices may have changed. 173fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy i = ~binarySearch(mKeys, 0, mSize, key); 174fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 175fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 176fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mSize >= mKeys.length) { 1779c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn int n = ArrayUtils.idealLongArraySize(mSize + 1); 178fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 179fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy long[] nkeys = new long[n]; 180fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] nvalues = new Object[n]; 181fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 182fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 183fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 184fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 185fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 186fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys = nkeys; 187fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues = nvalues; 188fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 189fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 190fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mSize - i != 0) { 191fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "move " + (mSize - i)); 192fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 193fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 194fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 195fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 196fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys[i] = key; 197fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[i] = value; 198fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize++; 199fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 200fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 201fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 202fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 2039c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Returns the number of key-value mappings that this LongSparseArray 204fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * currently stores. 205fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 206fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int size() { 207fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 208fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 209fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 210fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 211fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return mSize; 212fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 213fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 214fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 215fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, returns 216fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the key from the <code>index</code>th key-value mapping that this 2179c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 218fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 219fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public long keyAt(int index) { 220fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 221fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 222fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 223fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 224fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return mKeys[index]; 225fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 226fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 227fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 228fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, returns 229fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the value from the <code>index</code>th key-value mapping that this 2309c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 231fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 2329c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn @SuppressWarnings("unchecked") 233fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public E valueAt(int index) { 234fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 235fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 236fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 237fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 238fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return (E) mValues[index]; 239fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 240fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 241fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 242fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Given an index in the range <code>0...size()-1</code>, sets a new 243fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * value for the <code>index</code>th key-value mapping that this 2449c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * LongSparseArray stores. 245fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 246fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void setValueAt(int index, E value) { 247fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 248fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 249fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 250fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 251fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[index] = value; 252fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 253fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 254fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 255fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Returns the index for which {@link #keyAt} would return the 256fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified key, or a negative number if the specified 257fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * key is not mapped. 258fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 259fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int indexOfKey(long key) { 260fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 261fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 262fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 263fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 264fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return binarySearch(mKeys, 0, mSize, key); 265fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 266fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 267fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 268fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Returns an index for which {@link #valueAt} would return the 269fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified key, or a negative number if no keys map to the 270fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * specified value. 271fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Beware that this is a linear search, unlike lookups by key, 272fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * and that multiple keys can map to the same value and this will 273fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * find only one of them. 274fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 275fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public int indexOfValue(E value) { 276fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage) { 277fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 278fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 279fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 280fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < mSize; i++) 281fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mValues[i] == value) 282fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return i; 283fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 284fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return -1; 285fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 286fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 287fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 2889c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn * Removes all key-value mappings from this LongSparseArray. 289fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 290fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void clear() { 291fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int n = mSize; 292fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] values = mValues; 293fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 294fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy for (int i = 0; i < n; i++) { 295fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy values[i] = null; 296fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 297fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 298fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = 0; 299fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mGarbage = false; 300fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 301fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 302fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy /** 303fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * Puts a key/value pair into the array, optimizing for the case where 304fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy * the key is greater than all existing keys in the array. 305fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy */ 306fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy public void append(long key, E value) { 307fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mSize != 0 && key <= mKeys[mSize - 1]) { 308fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy put(key, value); 309fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return; 310fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 311fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 312fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (mGarbage && mSize >= mKeys.length) { 313fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy gc(); 314fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 315fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 316fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int pos = mSize; 317fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (pos >= mKeys.length) { 3189c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn int n = ArrayUtils.idealLongArraySize(pos + 1); 319fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 320fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy long[] nkeys = new long[n]; 321fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy Object[] nvalues = new Object[n]; 322fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 323fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 324fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 325fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 326fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 327fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys = nkeys; 328fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues = nvalues; 329fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 330fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 331fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mKeys[pos] = key; 332fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mValues[pos] = value; 333fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy mSize = pos + 1; 334fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 335fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 336fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy private static int binarySearch(long[] a, int start, int len, long key) { 337fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy int high = start + len, low = start - 1, guess; 338fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 339fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy while (high - low > 1) { 340fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy guess = (high + low) / 2; 341fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 342fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (a[guess] < key) 343fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy low = guess; 344fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy else 345fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy high = guess; 346fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 347fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy 348fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy if (high == start + len) 349fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return ~(start + len); 350fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy else if (a[high] == key) 351fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return high; 352fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy else 353fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy return ~high; 354fdbf6a7eac39a23e0e910c29678fe00d4eb56c99Romain Guy } 3559c1d2980f2c7c73f098d551499c4fd48cdc96b4dDianne Hackborn} 356