1fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com/* 2fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Copyright (C) 2006 The Android Open Source Project 3fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * 4fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Licensed under the Apache License, Version 2.0 (the "License"); 5fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * you may not use this file except in compliance with the License. 6fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * You may obtain a copy of the License at 7fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * 8fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * http://www.apache.org/licenses/LICENSE-2.0 9fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * 10fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Unless required by applicable law or agreed to in writing, software 11fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * distributed under the License is distributed on an "AS IS" BASIS, 12fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * See the License for the specific language governing permissions and 14fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * limitations under the License. 15fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 16fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 17128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com/* 18128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com * As per the Apache license requirements, this file has been modified 19128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com * from its original state. 20128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com * 21128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com * Such modifications are Copyright (C) 2010 Ben Gruver, and are released 22128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com * under the original license 23128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com */ 24128e8279c3cf44cc1d1c8f263035ba8e4044d5c6JesusFreke@JesusFreke.com 25fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.compackage org.jf.dexlib.Util; 26fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 27fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com/** 28fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * SparseIntArrays map integers to integers. Unlike a normal array of integers, 29fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * there can be gaps in the indices. It is intended to be more efficient 30fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * than using a HashMap to map Integers to Integers. 31fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 32fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.compublic class SparseIntArray { 33fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 34fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Creates a new SparseIntArray containing no mappings. 35fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 36fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public SparseIntArray() { 37fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com this(10); 38fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 39fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 40fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 41fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Creates a new SparseIntArray containing no mappings that will not 42fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * require any additional memory allocation to store the specified 43fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * number of mappings. 44fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 45fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public SparseIntArray(int initialCapacity) { 46fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mKeys = new int[initialCapacity]; 47fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues = new int[initialCapacity]; 48fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mSize = 0; 49fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 50fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 51fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 52fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Gets the int mapped from the specified key, or <code>0</code> 53fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * if no such mapping has been made. 54fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 55fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int get(int key) { 56fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return get(key, 0); 57fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 58fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 59fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 60fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Gets the int mapped from the specified key, or the specified value 61fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * if no such mapping has been made. 62fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 63fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int get(int key, int valueIfKeyNotFound) { 64fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int i = binarySearch(mKeys, 0, mSize, key); 65fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 66fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (i < 0) { 67fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return valueIfKeyNotFound; 68fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } else { 69fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return mValues[i]; 70fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 71fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 72fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 73fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 745934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver * Gets the int mapped from the specified key, or if not present, the 755934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver * closest key that is less than the specified key. 765934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver */ 775934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver public int getClosestSmaller(int key) { 785934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver int i = binarySearch(mKeys, 0, mSize, key); 795934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver 805934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver if (i < 0) { 815934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver i = ~i; 825934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver if (i > 0) { 835934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver i--; 845934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver } 855934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver return mValues[i]; 865934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver } else { 875934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver return mValues[i]; 885934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver } 895934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver } 905934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver 915934004fe3c1e9617793aa120e88f5df1b651c14Ben Gruver /** 92fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Removes the mapping from the specified key, if there was any. 93fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 94fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public void delete(int key) { 95fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int i = binarySearch(mKeys, 0, mSize, key); 96fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 97fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (i >= 0) { 98fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com removeAt(i); 99fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 100fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 101fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 102fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 103fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Removes the mapping at the given index. 104fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 105fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public void removeAt(int index) { 106fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 107fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 108fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mSize--; 109fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 110fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 111fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 112fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Adds a mapping from the specified key to the specified value, 113fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * replacing the previous mapping from the specified key if there 114fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * was one. 115fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 116fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public void put(int key, int value) { 117fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int i = binarySearch(mKeys, 0, mSize, key); 118fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 119fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (i >= 0) { 120fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues[i] = value; 121fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } else { 122fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com i = ~i; 123fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 124fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (mSize >= mKeys.length) { 125fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int n = Math.max(mSize + 1, mKeys.length * 2); 126fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 127fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int[] nkeys = new int[n]; 128fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int[] nvalues = new int[n]; 129fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 130fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 131fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 132fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 133fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 134fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mKeys = nkeys; 135fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues = nvalues; 136fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 137fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 138fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (mSize - i != 0) { 139fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com // Log.e("SparseIntArray", "move " + (mSize - i)); 140fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 141fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 142fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 143fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 144fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mKeys[i] = key; 145fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues[i] = value; 146fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mSize++; 147fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 148fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 149fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 150fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 151fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Returns the number of key-value mappings that this SparseIntArray 152fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * currently stores. 153fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 154fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int size() { 155fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return mSize; 156fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 157fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 158fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 159fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Given an index in the range <code>0...size()-1</code>, returns 160fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * the key from the <code>index</code>th key-value mapping that this 161fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * SparseIntArray stores. 162fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 163fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int keyAt(int index) { 164fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return mKeys[index]; 165fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 166fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 167fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 168fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Given an index in the range <code>0...size()-1</code>, returns 169fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * the value from the <code>index</code>th key-value mapping that this 170fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * SparseIntArray stores. 171fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 172fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int valueAt(int index) { 173fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return mValues[index]; 174fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 175fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 176fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 177fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Returns the index for which {@link #keyAt} would return the 178fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * specified key, or a negative number if the specified 179fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * key is not mapped. 180fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 181fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int indexOfKey(int key) { 182fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return binarySearch(mKeys, 0, mSize, key); 183fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 184fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 185fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 186fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Returns an index for which {@link #valueAt} would return the 187fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * specified key, or a negative number if no keys map to the 188fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * specified value. 189fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Beware that this is a linear search, unlike lookups by key, 190fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * and that multiple keys can map to the same value and this will 191fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * find only one of them. 192fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 193fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public int indexOfValue(int value) { 194fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com for (int i = 0; i < mSize; i++) 195fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (mValues[i] == value) 196fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return i; 197fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 198fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return -1; 199fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 200fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 201fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 202fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Removes all key-value mappings from this SparseIntArray. 203fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 204fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public void clear() { 205fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mSize = 0; 206fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 207fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 208fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com /** 209fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * Puts a key/value pair into the array, optimizing for the case where 210fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com * the key is greater than all existing keys in the array. 211fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com */ 212fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com public void append(int key, int value) { 213fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (mSize != 0 && key <= mKeys[mSize - 1]) { 214fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com put(key, value); 215fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return; 216fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 217fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 218fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int pos = mSize; 219fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (pos >= mKeys.length) { 220fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int n = Math.max(pos + 1, mKeys.length * 2); 221fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 222fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int[] nkeys = new int[n]; 223fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int[] nvalues = new int[n]; 224fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 225fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 226fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 227fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 228fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 229fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mKeys = nkeys; 230fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues = nvalues; 231fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 232fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 233fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mKeys[pos] = key; 234fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mValues[pos] = value; 235fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com mSize = pos + 1; 236fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 237fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 238fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com private static int binarySearch(int[] a, int start, int len, int key) { 239fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com int high = start + len, low = start - 1, guess; 240fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 241fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com while (high - low > 1) { 242fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com guess = (high + low) / 2; 243fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 244fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (a[guess] < key) 245fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com low = guess; 246fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com else 247fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com high = guess; 248fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 249fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 250fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com if (high == start + len) 251fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return ~(start + len); 252fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com else if (a[high] == key) 253fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return high; 254fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com else 255fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com return ~high; 256fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com } 257fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com 258fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com private int[] mKeys; 259fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com private int[] mValues; 260fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com private int mSize; 261fda2e631ac0b1ca092973b7fff4b2f38d2c23437JesusFreke@JesusFreke.com} 262