SparseIntArray.java revision 5934004fe3c1e9617793aa120e88f5df1b651c14
1/* 2 * Copyright (C) 2006 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 17/* 18 * As per the Apache license requirements, this file has been modified 19 * from its original state. 20 * 21 * Such modifications are Copyright (C) 2010 Ben Gruver, and are released 22 * under the original license 23 */ 24 25package org.jf.dexlib.Util; 26 27/** 28 * SparseIntArrays map integers to integers. Unlike a normal array of integers, 29 * there can be gaps in the indices. It is intended to be more efficient 30 * than using a HashMap to map Integers to Integers. 31 */ 32public class SparseIntArray { 33 /** 34 * Creates a new SparseIntArray containing no mappings. 35 */ 36 public SparseIntArray() { 37 this(10); 38 } 39 40 /** 41 * Creates a new SparseIntArray containing no mappings that will not 42 * require any additional memory allocation to store the specified 43 * number of mappings. 44 */ 45 public SparseIntArray(int initialCapacity) { 46 mKeys = new int[initialCapacity]; 47 mValues = new int[initialCapacity]; 48 mSize = 0; 49 } 50 51 /** 52 * Gets the int mapped from the specified key, or <code>0</code> 53 * if no such mapping has been made. 54 */ 55 public int get(int key) { 56 return get(key, 0); 57 } 58 59 /** 60 * Gets the int mapped from the specified key, or the specified value 61 * if no such mapping has been made. 62 */ 63 public int get(int key, int valueIfKeyNotFound) { 64 int i = binarySearch(mKeys, 0, mSize, key); 65 66 if (i < 0) { 67 return valueIfKeyNotFound; 68 } else { 69 return mValues[i]; 70 } 71 } 72 73 /** 74 * Gets the int mapped from the specified key, or if not present, the 75 * closest key that is less than the specified key. 76 */ 77 public int getClosestSmaller(int key) { 78 int i = binarySearch(mKeys, 0, mSize, key); 79 80 if (i < 0) { 81 i = ~i; 82 if (i > 0) { 83 i--; 84 } 85 return mValues[i]; 86 } else { 87 return mValues[i]; 88 } 89 } 90 91 /** 92 * Removes the mapping from the specified key, if there was any. 93 */ 94 public void delete(int key) { 95 int i = binarySearch(mKeys, 0, mSize, key); 96 97 if (i >= 0) { 98 removeAt(i); 99 } 100 } 101 102 /** 103 * Removes the mapping at the given index. 104 */ 105 public void removeAt(int index) { 106 System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 107 System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 108 mSize--; 109 } 110 111 /** 112 * Adds a mapping from the specified key to the specified value, 113 * replacing the previous mapping from the specified key if there 114 * was one. 115 */ 116 public void put(int key, int value) { 117 int i = binarySearch(mKeys, 0, mSize, key); 118 119 if (i >= 0) { 120 mValues[i] = value; 121 } else { 122 i = ~i; 123 124 if (mSize >= mKeys.length) { 125 int n = Math.max(mSize + 1, mKeys.length * 2); 126 127 int[] nkeys = new int[n]; 128 int[] nvalues = new int[n]; 129 130 // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 131 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 132 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 133 134 mKeys = nkeys; 135 mValues = nvalues; 136 } 137 138 if (mSize - i != 0) { 139 // Log.e("SparseIntArray", "move " + (mSize - i)); 140 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 141 System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 142 } 143 144 mKeys[i] = key; 145 mValues[i] = value; 146 mSize++; 147 } 148 } 149 150 /** 151 * Returns the number of key-value mappings that this SparseIntArray 152 * currently stores. 153 */ 154 public int size() { 155 return mSize; 156 } 157 158 /** 159 * Given an index in the range <code>0...size()-1</code>, returns 160 * the key from the <code>index</code>th key-value mapping that this 161 * SparseIntArray stores. 162 */ 163 public int keyAt(int index) { 164 return mKeys[index]; 165 } 166 167 /** 168 * Given an index in the range <code>0...size()-1</code>, returns 169 * the value from the <code>index</code>th key-value mapping that this 170 * SparseIntArray stores. 171 */ 172 public int valueAt(int index) { 173 return mValues[index]; 174 } 175 176 /** 177 * Returns the index for which {@link #keyAt} would return the 178 * specified key, or a negative number if the specified 179 * key is not mapped. 180 */ 181 public int indexOfKey(int key) { 182 return binarySearch(mKeys, 0, mSize, key); 183 } 184 185 /** 186 * Returns an index for which {@link #valueAt} would return the 187 * specified key, or a negative number if no keys map to the 188 * specified value. 189 * Beware that this is a linear search, unlike lookups by key, 190 * and that multiple keys can map to the same value and this will 191 * find only one of them. 192 */ 193 public int indexOfValue(int value) { 194 for (int i = 0; i < mSize; i++) 195 if (mValues[i] == value) 196 return i; 197 198 return -1; 199 } 200 201 /** 202 * Removes all key-value mappings from this SparseIntArray. 203 */ 204 public void clear() { 205 mSize = 0; 206 } 207 208 /** 209 * Puts a key/value pair into the array, optimizing for the case where 210 * the key is greater than all existing keys in the array. 211 */ 212 public void append(int key, int value) { 213 if (mSize != 0 && key <= mKeys[mSize - 1]) { 214 put(key, value); 215 return; 216 } 217 218 int pos = mSize; 219 if (pos >= mKeys.length) { 220 int n = Math.max(pos + 1, mKeys.length * 2); 221 222 int[] nkeys = new int[n]; 223 int[] nvalues = new int[n]; 224 225 // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 226 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 227 System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 228 229 mKeys = nkeys; 230 mValues = nvalues; 231 } 232 233 mKeys[pos] = key; 234 mValues[pos] = value; 235 mSize = pos + 1; 236 } 237 238 private static int binarySearch(int[] a, int start, int len, int key) { 239 int high = start + len, low = start - 1, guess; 240 241 while (high - low > 1) { 242 guess = (high + low) / 2; 243 244 if (a[guess] < key) 245 low = guess; 246 else 247 high = guess; 248 } 249 250 if (high == start + len) 251 return ~(start + len); 252 else if (a[high] == key) 253 return high; 254 else 255 return ~high; 256 } 257 258 private int[] mKeys; 259 private int[] mValues; 260 private int mSize; 261} 262