SparseLongArray.java revision b993f41eb2f165425dfdf0f93ea0b1e354eca837
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.util; 18 19import com.android.internal.util.ArrayUtils; 20 21/** 22 * SparseLongArrays map integers to longs. Unlike a normal array of longs, 23 * there can be gaps in the indices. It is intended to be more memory efficient 24 * than using a HashMap to map Integers to Longs, both because it avoids 25 * auto-boxing keys and values and its data structure doesn't rely on an extra entry object 26 * for each mapping. 27 * 28 * <p>Note that this container keeps its mappings in an array data structure, 29 * using a binary search to find keys. The implementation is not intended to be appropriate for 30 * data structures 31 * that may contain large numbers of items. It is generally slower than a traditional 32 * HashMap, since lookups require a binary search and adds and removes require inserting 33 * and deleting entries in the array. For containers holding up to hundreds of items, 34 * the performance difference is not significant, less than 50%.</p> 35 */ 36public class SparseLongArray implements Cloneable { 37 static final long[] EMPTY_LONGS = new long[0]; 38 39 private int[] mKeys; 40 private long[] mValues; 41 private int mSize; 42 43 /** 44 * Creates a new SparseLongArray containing no mappings. 45 */ 46 public SparseLongArray() { 47 this(10); 48 } 49 50 /** 51 * Creates a new SparseLongArray containing no mappings that will not 52 * require any additional memory allocation to store the specified 53 * number of mappings. If you supply an initial capacity of 0, the 54 * sparse array will be initialized with a light-weight representation 55 * not requiring any additional array allocations. 56 */ 57 public SparseLongArray(int initialCapacity) { 58 if (initialCapacity == 0) { 59 mKeys = SparseArray.EMPTY_INTS; 60 mValues = EMPTY_LONGS; 61 } else { 62 initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 63 mKeys = new int[initialCapacity]; 64 mValues = new long[initialCapacity]; 65 } 66 mSize = 0; 67 } 68 69 @Override 70 public SparseLongArray clone() { 71 SparseLongArray clone = null; 72 try { 73 clone = (SparseLongArray) super.clone(); 74 clone.mKeys = mKeys.clone(); 75 clone.mValues = mValues.clone(); 76 } catch (CloneNotSupportedException cnse) { 77 /* ignore */ 78 } 79 return clone; 80 } 81 82 /** 83 * Gets the long mapped from the specified key, or <code>0</code> 84 * if no such mapping has been made. 85 */ 86 public long get(int key) { 87 return get(key, 0); 88 } 89 90 /** 91 * Gets the long mapped from the specified key, or the specified value 92 * if no such mapping has been made. 93 */ 94 public long get(int key, long valueIfKeyNotFound) { 95 int i = SparseArray.binarySearch(mKeys, mSize, key); 96 97 if (i < 0) { 98 return valueIfKeyNotFound; 99 } else { 100 return mValues[i]; 101 } 102 } 103 104 /** 105 * Removes the mapping from the specified key, if there was any. 106 */ 107 public void delete(int key) { 108 int i = SparseArray.binarySearch(mKeys, mSize, key); 109 110 if (i >= 0) { 111 removeAt(i); 112 } 113 } 114 115 /** 116 * Removes the mapping at the given index. 117 */ 118 public void removeAt(int index) { 119 System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 120 System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 121 mSize--; 122 } 123 124 /** 125 * Adds a mapping from the specified key to the specified value, 126 * replacing the previous mapping from the specified key if there 127 * was one. 128 */ 129 public void put(int key, long value) { 130 int i = SparseArray.binarySearch(mKeys, mSize, key); 131 132 if (i >= 0) { 133 mValues[i] = value; 134 } else { 135 i = ~i; 136 137 if (mSize >= mKeys.length) { 138 growKeyAndValueArrays(mSize + 1); 139 } 140 141 if (mSize - i != 0) { 142 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 143 System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 144 } 145 146 mKeys[i] = key; 147 mValues[i] = value; 148 mSize++; 149 } 150 } 151 152 /** 153 * Returns the number of key-value mappings that this SparseIntArray 154 * currently stores. 155 */ 156 public int size() { 157 return mSize; 158 } 159 160 /** 161 * Given an index in the range <code>0...size()-1</code>, returns 162 * the key from the <code>index</code>th key-value mapping that this 163 * SparseLongArray stores. 164 */ 165 public int keyAt(int index) { 166 return mKeys[index]; 167 } 168 169 /** 170 * Given an index in the range <code>0...size()-1</code>, returns 171 * the value from the <code>index</code>th key-value mapping that this 172 * SparseLongArray stores. 173 */ 174 public long valueAt(int index) { 175 return mValues[index]; 176 } 177 178 /** 179 * Returns the index for which {@link #keyAt} would return the 180 * specified key, or a negative number if the specified 181 * key is not mapped. 182 */ 183 public int indexOfKey(int key) { 184 return SparseArray.binarySearch(mKeys, mSize, key); 185 } 186 187 /** 188 * Returns an index for which {@link #valueAt} would return the 189 * specified key, or a negative number if no keys map to the 190 * specified value. 191 * Beware that this is a linear search, unlike lookups by key, 192 * and that multiple keys can map to the same value and this will 193 * find only one of them. 194 */ 195 public int indexOfValue(long value) { 196 for (int i = 0; i < mSize; i++) 197 if (mValues[i] == value) 198 return i; 199 200 return -1; 201 } 202 203 /** 204 * Removes all key-value mappings from this SparseIntArray. 205 */ 206 public void clear() { 207 mSize = 0; 208 } 209 210 /** 211 * Puts a key/value pair into the array, optimizing for the case where 212 * the key is greater than all existing keys in the array. 213 */ 214 public void append(int key, long value) { 215 if (mSize != 0 && key <= mKeys[mSize - 1]) { 216 put(key, value); 217 return; 218 } 219 220 int pos = mSize; 221 if (pos >= mKeys.length) { 222 growKeyAndValueArrays(pos + 1); 223 } 224 225 mKeys[pos] = key; 226 mValues[pos] = value; 227 mSize = pos + 1; 228 } 229 230 private void growKeyAndValueArrays(int minNeededSize) { 231 int n = ArrayUtils.idealLongArraySize(minNeededSize); 232 233 int[] nkeys = new int[n]; 234 long[] nvalues = new long[n]; 235 236 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 237 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 238 239 mKeys = nkeys; 240 mValues = nvalues; 241 } 242} 243