1021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov/* 2021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Copyright (C) 2011 The Android Open Source Project 3021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 4021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Licensed under the Apache License, Version 2.0 (the "License"); 5021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * you may not use this file except in compliance with the License. 6021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * You may obtain a copy of the License at 7021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 8021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * http://www.apache.org/licenses/LICENSE-2.0 9021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 10021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Unless required by applicable law or agreed to in writing, software 11021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * distributed under the License is distributed on an "AS IS" BASIS, 12021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * See the License for the specific language governing permissions and 14021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * limitations under the License. 15021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 16021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 17021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovpackage android.util; 18021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 19021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovimport com.android.internal.util.ArrayUtils; 20021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 21021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov/** 22021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArrays map integers to longs. Unlike a normal array of longs, 23021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * there can be gaps in the indices. It is intended to be more efficient 24021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * than using a HashMap to map Integers to Longs. 25021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * 26021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * @hide 27021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 28021078554b902179442a345a9d080a165c3b5139Svetoslav Ganovpublic class SparseLongArray implements Cloneable { 29021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 30021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private int[] mKeys; 31021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private long[] mValues; 32021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private int mSize; 33021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 34021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 35021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Creates a new SparseLongArray containing no mappings. 36021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 37021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray() { 38021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov this(10); 39021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 40021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 41021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 42021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Creates a new SparseLongArray containing no mappings that will not 43021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * require any additional memory allocation to store the specified 44021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * number of mappings. 45021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 46021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray(int initialCapacity) { 47021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity); 48021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 49021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys = new int[initialCapacity]; 50021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues = new long[initialCapacity]; 51021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = 0; 52021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 53021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 54021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov @Override 55021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public SparseLongArray clone() { 56021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov SparseLongArray clone = null; 57021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov try { 58021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone = (SparseLongArray) super.clone(); 59021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone.mKeys = mKeys.clone(); 60021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov clone.mValues = mValues.clone(); 61021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } catch (CloneNotSupportedException cnse) { 62021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /* ignore */ 63021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 64021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return clone; 65021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 66021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 67021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 68021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Gets the long mapped from the specified key, or <code>0</code> 69021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * if no such mapping has been made. 70021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 71021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long get(int key) { 72021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return get(key, 0); 73021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 74021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 75021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 76021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Gets the long mapped from the specified key, or the specified value 77021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * if no such mapping has been made. 78021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 79021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long get(int key, long valueIfKeyNotFound) { 80021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int i = binarySearch(mKeys, 0, mSize, key); 81021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 82021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i < 0) { 83021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return valueIfKeyNotFound; 84021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } else { 85021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mValues[i]; 86021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 87021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 88021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 89021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 90021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes the mapping from the specified key, if there was any. 91021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 92021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void delete(int key) { 93021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int i = binarySearch(mKeys, 0, mSize, key); 94021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 95021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i >= 0) { 96021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov removeAt(i); 97021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 98021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 99021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 100021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 101021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes the mapping at the given index. 102021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 103021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void removeAt(int index) { 104021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 105021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 106021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize--; 107021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 108021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 109021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 110021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Adds a mapping from the specified key to the specified value, 111021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * replacing the previous mapping from the specified key if there 112021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * was one. 113021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 114021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void put(int key, long value) { 115021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int i = binarySearch(mKeys, 0, mSize, key); 116021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 117021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (i >= 0) { 118021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[i] = value; 119021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } else { 120021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov i = ~i; 121021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 122021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize >= mKeys.length) { 123021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov growKeyAndValueArrays(mSize + 1); 124021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 125021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 126021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize - i != 0) { 127021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 128021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 129021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 130021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 131021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys[i] = key; 132021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[i] = value; 133021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize++; 134021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 135021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 136021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 137021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 138021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns the number of key-value mappings that this SparseIntArray 139021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * currently stores. 140021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 141021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int size() { 142021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mSize; 143021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 144021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 145021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 146021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Given an index in the range <code>0...size()-1</code>, returns 147021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the key from the <code>index</code>th key-value mapping that this 148021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArray stores. 149021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 150021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int keyAt(int index) { 151021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mKeys[index]; 152021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 153021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 154021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 155021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Given an index in the range <code>0...size()-1</code>, returns 156021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the value from the <code>index</code>th key-value mapping that this 157021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * SparseLongArray stores. 158021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 159021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public long valueAt(int index) { 160021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return mValues[index]; 161021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 162021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 163021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 164021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns the index for which {@link #keyAt} would return the 165021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified key, or a negative number if the specified 166021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * key is not mapped. 167021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 168021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int indexOfKey(int key) { 169021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return binarySearch(mKeys, 0, mSize, key); 170021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 171021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 172021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 173021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Returns an index for which {@link #valueAt} would return the 174021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified key, or a negative number if no keys map to the 175021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * specified value. 176021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Beware that this is a linear search, unlike lookups by key, 177021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * and that multiple keys can map to the same value and this will 178021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * find only one of them. 179021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 180021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public int indexOfValue(long value) { 181021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov for (int i = 0; i < mSize; i++) 182021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mValues[i] == value) 183021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return i; 184021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 185021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return -1; 186021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 187021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 188021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 189021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Removes all key-value mappings from this SparseIntArray. 190021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 191021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void clear() { 192021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = 0; 193021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 194021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 195021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov /** 196021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * Puts a key/value pair into the array, optimizing for the case where 197021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov * the key is greater than all existing keys in the array. 198021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov */ 199021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov public void append(int key, long value) { 200021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (mSize != 0 && key <= mKeys[mSize - 1]) { 201021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov put(key, value); 202021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return; 203021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 204021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 205021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int pos = mSize; 206021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (pos >= mKeys.length) { 207021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov growKeyAndValueArrays(pos + 1); 208021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 209021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 210021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys[pos] = key; 211021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues[pos] = value; 212021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mSize = pos + 1; 213021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 214021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 215021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private void growKeyAndValueArrays(int minNeededSize) { 216021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int n = ArrayUtils.idealLongArraySize(minNeededSize); 217021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 218021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int[] nkeys = new int[n]; 219021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov long[] nvalues = new long[n]; 220021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 221021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 222021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 223021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 224021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mKeys = nkeys; 225021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov mValues = nvalues; 226021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 227021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 228021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov private static int binarySearch(int[] a, int start, int len, long key) { 229021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov int high = start + len, low = start - 1, guess; 230021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 231021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov while (high - low > 1) { 232021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov guess = (high + low) / 2; 233021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 234021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (a[guess] < key) 235021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov low = guess; 236021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov else 237021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov high = guess; 238021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 239021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov 240021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov if (high == start + len) 241021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return ~(start + len); 242021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov else if (a[high] == key) 243021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return high; 244021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov else 245021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov return ~high; 246021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov } 247021078554b902179442a345a9d080a165c3b5139Svetoslav Ganov} 248