1cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn/* 2ac5fe7c617c66850fff75a9fce9979c6e5674b0fAurimas Liutikas * Copyright 2018 The Android Open Source Project 3cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 4cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 5cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * you may not use this file except in compliance with the License. 6cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * You may obtain a copy of the License at 7cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 8cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 9cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * 10cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Unless required by applicable law or agreed to in writing, software 11cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 12cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * See the License for the specific language governing permissions and 14cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * limitations under the License. 15cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 16cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 17ac5fe7c617c66850fff75a9fce9979c6e5674b0fAurimas Liutikaspackage androidx.collection; 18cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 19cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn/** 20df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * SparseArrays map integers to Objects. Unlike a normal array of Objects, 21df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * there can be gaps in the indices. It is intended to be more memory efficient 22df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * than using a HashMap to map Integers to Objects, both because it avoids 23df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * auto-boxing keys and its data structure doesn't rely on an extra entry object 24df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * for each mapping. 25df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * 26df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * <p>Note that this container keeps its mappings in an array data structure, 27df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * using a binary search to find keys. The implementation is not intended to be appropriate for 28df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * data structures 29df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * that may contain large numbers of items. It is generally slower than a traditional 30df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * HashMap, since lookups require a binary search and adds and removes require inserting 31df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * and deleting entries in the array. For containers holding up to hundreds of items, 32df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * the performance difference is not significant, less than 50%.</p> 33df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * 34df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * <p>To help with performance, the container includes an optimization when removing 35df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * keys: instead of compacting its array immediately, it leaves the removed entry marked 36df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * as deleted. The entry can then be re-used for the same key, or compacted later in 37df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * a single garbage collection step of all removed entries. This garbage collection will 38df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * need to be performed at any time the array needs to be grown or the the map size or 39df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * entry values are retrieved.</p> 40df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * 41df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * <p>It is possible to iterate over the items in this container using 42df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using 43df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * <code>keyAt(int)</code> with ascending values of the index will return the 44df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * keys in ascending order, or the values corresponding to the keys in ascending 45df3c42068dd979a9738c3dad87fa3165b61bb8a3Jake Wharton * order in the case of <code>valueAt(int)</code>.</p> 46cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 472290993eddf5262a8df7fc9478daed52401e325aDianne Hackbornpublic class SparseArrayCompat<E> implements Cloneable { 48cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private static final Object DELETED = new Object(); 49cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private boolean mGarbage = false; 50cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 512290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private int[] mKeys; 522290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private Object[] mValues; 532290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn private int mSize; 542290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 55cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 56cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Creates a new SparseArray containing no mappings. 57cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 58346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public SparseArrayCompat() { 59cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn this(10); 60cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 61cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 62cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 63cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Creates a new SparseArray containing no mappings that will not 64cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * require any additional memory allocation to store the specified 652290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * number of mappings. If you supply an initial capacity of 0, the 662290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * sparse array will be initialized with a light-weight representation 672290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * not requiring any additional array allocations. 68cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 69346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public SparseArrayCompat(int initialCapacity) { 702290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (initialCapacity == 0) { 712290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = ContainerHelpers.EMPTY_INTS; 722290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = ContainerHelpers.EMPTY_OBJECTS; 732290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 742290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn initialCapacity = ContainerHelpers.idealIntArraySize(initialCapacity); 752290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mKeys = new int[initialCapacity]; 762290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn mValues = new Object[initialCapacity]; 772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 78cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = 0; 79cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 80cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 812290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 822290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 832290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public SparseArrayCompat<E> clone() { 842290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn SparseArrayCompat<E> clone = null; 852290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn try { 862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone = (SparseArrayCompat<E>) super.clone(); 872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone.mKeys = mKeys.clone(); 882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn clone.mValues = mValues.clone(); 892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } catch (CloneNotSupportedException cnse) { 902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /* ignore */ 912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return clone; 932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn 95cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 96cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Gets the Object mapped from the specified key, or <code>null</code> 97cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * if no such mapping has been made. 98cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 99cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E get(int key) { 100cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return get(key, null); 101cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 102cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 103cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 104cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Gets the Object mapped from the specified key, or the specified Object 105cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * if no such mapping has been made. 106cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 1072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 108cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E get(int key, E valueIfKeyNotFound) { 1092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 110cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 111cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i < 0 || mValues[i] == DELETED) { 112cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return valueIfKeyNotFound; 113cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } else { 114cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return (E) mValues[i]; 115cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 116cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 117cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 118cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 119cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes the mapping from the specified key, if there was any. 120cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 121cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void delete(int key) { 1222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 123cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 124cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i >= 0) { 125cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[i] != DELETED) { 126cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = DELETED; 127cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = true; 128cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 129cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 130cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 131cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 132cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 133cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Alias for {@link #delete(int)}. 134cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 135cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void remove(int key) { 136cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn delete(key); 137cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 138cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 139cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 140cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes the mapping at the specified index. 141cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 142cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void removeAt(int index) { 143cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[index] != DELETED) { 144cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[index] = DELETED; 145cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = true; 146cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 147cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 148346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 149346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell /** 150346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * Remove a range of mappings as a batch. 151346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * 152346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * @param index Index to begin at 153346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * @param size Number of mappings to remove 154346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell */ 155346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell public void removeAtRange(int index, int size) { 156346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell final int end = Math.min(mSize, index + size); 157346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell for (int i = index; i < end; i++) { 158346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell removeAt(i); 159346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell } 160346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell } 161346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 162cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn private void gc() { 163cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "gc start with " + mSize); 164cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 165cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int n = mSize; 166cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int o = 0; 167cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] keys = mKeys; 168cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] values = mValues; 169cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 170cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < n; i++) { 171cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object val = values[i]; 172cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 173cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (val != DELETED) { 174cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i != o) { 175cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn keys[o] = keys[i]; 176cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn values[o] = val; 1772290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn values[i] = null; 178cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 179cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 180cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn o++; 181cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 182cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 183cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 184cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = false; 185cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = o; 186cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 187cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "gc end with " + mSize); 188cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 189cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 190cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 191cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Adds a mapping from the specified key to the specified value, 192cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * replacing the previous mapping from the specified key if there 193cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * was one. 194cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 195cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void put(int key, E value) { 1962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 197cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 198cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i >= 0) { 199cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 200cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } else { 201cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn i = ~i; 202cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 203cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (i < mSize && mValues[i] == DELETED) { 204cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[i] = key; 205cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 206cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return; 207cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 208cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 209cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 210cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 211cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 212cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Search again because indices may have changed. 2132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn i = ~ ContainerHelpers.binarySearch(mKeys, mSize, key); 214cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 215cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 216cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize >= mKeys.length) { 2172290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealIntArraySize(mSize + 1); 218cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 219cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] nkeys = new int[n]; 220cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] nvalues = new Object[n]; 221cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 222cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 223cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 224cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 225cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 226cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys = nkeys; 227cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues = nvalues; 228cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 229cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 230cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize - i != 0) { 231cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "move " + (mSize - i)); 232cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 233cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 234cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 235cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 236cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[i] = key; 237cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[i] = value; 238cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize++; 239cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 240cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 241cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 242cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 243cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns the number of key-value mappings that this SparseArray 244cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * currently stores. 245cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 246cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int size() { 247cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 248cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 249cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 250cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 251cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return mSize; 252cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 253cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 254cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 2557e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu * Return true if size() is 0. 2567e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu * @return true if size() is 0. 2577e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu */ 2587e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu public boolean isEmpty() { 2597e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu return size() == 0; 2607e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu } 2617e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu 2627e3bf2d2ce4d509c75d88efdb7fa1d0ea73c648bDavid Ogutu /** 263cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 264cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the key from the <code>index</code>th key-value mapping that this 265346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 266cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 267cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int keyAt(int index) { 268cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 269cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 270cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 271cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 272cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return mKeys[index]; 273cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 274346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 275cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 276cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, returns 277cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the value from the <code>index</code>th key-value mapping that this 278346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 279cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 2802290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @SuppressWarnings("unchecked") 281cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public E valueAt(int index) { 282cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 283cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 284cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 285cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 286cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return (E) mValues[index]; 287cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 288cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 289cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 290cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Given an index in the range <code>0...size()-1</code>, sets a new 291cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * value for the <code>index</code>th key-value mapping that this 292346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell * SparseArray stores. 293cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 294cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void setValueAt(int index, E value) { 295cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 296cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 297cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 298cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 299cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[index] = value; 300cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 301346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 302cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 303cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns the index for which {@link #keyAt} would return the 304cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified key, or a negative number if the specified 305cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * key is not mapped. 306cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 307cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int indexOfKey(int key) { 308cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 309cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 310cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 311cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 3122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return ContainerHelpers.binarySearch(mKeys, mSize, key); 313cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 314cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 315cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 316cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Returns an index for which {@link #valueAt} would return the 317cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified key, or a negative number if no keys map to the 318cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * specified value. 3192290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Beware that this is a linear search, unlike lookups by key, 320cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * and that multiple keys can map to the same value and this will 321cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * find only one of them. 3222290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>Note also that unlike most collections' {@code indexOf} methods, 3232290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this method compares values using {@code ==} rather than {@code equals}. 324cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 325cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public int indexOfValue(E value) { 326cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage) { 327cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 328cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 329cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 330cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < mSize; i++) 331cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mValues[i] == value) 332cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return i; 333cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 334cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return -1; 335cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 336cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 337cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 338cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Removes all key-value mappings from this SparseArray. 339cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 340cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void clear() { 341cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int n = mSize; 342cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] values = mValues; 343cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 344cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn for (int i = 0; i < n; i++) { 345cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn values[i] = null; 346cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 347cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 348cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = 0; 349cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mGarbage = false; 350cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 351cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 352cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn /** 353cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * Puts a key/value pair into the array, optimizing for the case where 354cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn * the key is greater than all existing keys in the array. 355cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn */ 356cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn public void append(int key, E value) { 357cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mSize != 0 && key <= mKeys[mSize - 1]) { 358cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn put(key, value); 359cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn return; 360cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 361cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 362cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (mGarbage && mSize >= mKeys.length) { 363cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn gc(); 364cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 365cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 366cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int pos = mSize; 367cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn if (pos >= mKeys.length) { 3682290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int n = ContainerHelpers.idealIntArraySize(pos + 1); 369cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 370cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn int[] nkeys = new int[n]; 371cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn Object[] nvalues = new Object[n]; 372cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 373cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 374cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 375cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 376cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 377cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys = nkeys; 378cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues = nvalues; 379cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 380cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 381cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mKeys[pos] = key; 382cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mValues[pos] = value; 383cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn mSize = pos + 1; 384cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 385346e2f2390f0d743fd10e7d01a015df6b32292cdAdam Powell 3862290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn /** 3872290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * {@inheritDoc} 3882290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * 3892290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * <p>This implementation composes a string by iterating over its mappings. If 3902290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * this map contains itself as a value, the string "(this Map)" 3912290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn * will appear in its place. 3922290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn */ 3932290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn @Override 3942290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn public String toString() { 3952290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (size() <= 0) { 3962290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return "{}"; 397cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 398cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn 3992290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn StringBuilder buffer = new StringBuilder(mSize * 28); 4002290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('{'); 4012290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn for (int i=0; i<mSize; i++) { 4022290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (i > 0) { 4032290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(", "); 4042290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4052290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn int key = keyAt(i); 4062290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(key); 4072290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('='); 4082290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn Object value = valueAt(i); 4092290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn if (value != this) { 4102290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append(value); 4112290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } else { 4122290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append("(this Map)"); 4132290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4142290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn } 4152290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn buffer.append('}'); 4162290993eddf5262a8df7fc9478daed52401e325aDianne Hackborn return buffer.toString(); 417cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn } 418cba2e2c881e8e16ea5025b564c94320174d65f01Dianne Hackborn} 419