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 package android.util; 18 19 import android.compat.annotation.UnsupportedAppUsage; 20 21 import com.android.internal.util.ArrayUtils; 22 import com.android.internal.util.GrowingArrayUtils; 23 24 import libcore.util.EmptyArray; 25 26 /** 27 * SparseBooleanArrays map integers to booleans. 28 * Unlike a normal array of booleans 29 * there can be gaps in the indices. It is intended to be more memory efficient 30 * than using a HashMap to map Integers to Booleans, both because it avoids 31 * auto-boxing keys and values and its data structure doesn't rely on an extra entry object 32 * for each mapping. 33 * 34 * <p>Note that this container keeps its mappings in an array data structure, 35 * using a binary search to find keys. The implementation is not intended to be appropriate for 36 * data structures 37 * that may contain large numbers of items. It is generally slower than a traditional 38 * HashMap, since lookups require a binary search and adds and removes require inserting 39 * and deleting entries in the array. For containers holding up to hundreds of items, 40 * the performance difference is not significant, less than 50%.</p> 41 * 42 * <p>It is possible to iterate over the items in this container using 43 * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using 44 * <code>keyAt(int)</code> with ascending values of the index will return the 45 * keys in ascending order, or the values corresponding to the keys in ascending 46 * order in the case of <code>valueAt(int)</code>.</p> 47 */ 48 public class SparseBooleanArray implements Cloneable { 49 /** 50 * Creates a new SparseBooleanArray containing no mappings. 51 */ SparseBooleanArray()52 public SparseBooleanArray() { 53 this(10); 54 } 55 56 /** 57 * Creates a new SparseBooleanArray containing no mappings that will not 58 * require any additional memory allocation to store the specified 59 * number of mappings. If you supply an initial capacity of 0, the 60 * sparse array will be initialized with a light-weight representation 61 * not requiring any additional array allocations. 62 */ SparseBooleanArray(int initialCapacity)63 public SparseBooleanArray(int initialCapacity) { 64 if (initialCapacity == 0) { 65 mKeys = EmptyArray.INT; 66 mValues = EmptyArray.BOOLEAN; 67 } else { 68 mKeys = ArrayUtils.newUnpaddedIntArray(initialCapacity); 69 mValues = new boolean[mKeys.length]; 70 } 71 mSize = 0; 72 } 73 74 @Override clone()75 public SparseBooleanArray clone() { 76 SparseBooleanArray clone = null; 77 try { 78 clone = (SparseBooleanArray) super.clone(); 79 clone.mKeys = mKeys.clone(); 80 clone.mValues = mValues.clone(); 81 } catch (CloneNotSupportedException cnse) { 82 /* ignore */ 83 } 84 return clone; 85 } 86 87 /** 88 * Gets the boolean mapped from the specified key, or <code>false</code> 89 * if no such mapping has been made. 90 */ get(int key)91 public boolean get(int key) { 92 return get(key, false); 93 } 94 95 /** 96 * Gets the boolean mapped from the specified key, or the specified value 97 * if no such mapping has been made. 98 */ get(int key, boolean valueIfKeyNotFound)99 public boolean get(int key, boolean valueIfKeyNotFound) { 100 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 101 102 if (i < 0) { 103 return valueIfKeyNotFound; 104 } else { 105 return mValues[i]; 106 } 107 } 108 109 /** 110 * Removes the mapping from the specified key, if there was any. 111 */ delete(int key)112 public void delete(int key) { 113 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 114 115 if (i >= 0) { 116 System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1)); 117 System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1)); 118 mSize--; 119 } 120 } 121 122 /** 123 * Removes the mapping at the specified index. 124 * <p> 125 * For indices outside of the range {@code 0...size()-1}, the behavior is undefined. 126 */ removeAt(int index)127 public void removeAt(int index) { 128 System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 129 System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 130 mSize--; 131 } 132 133 /** 134 * Adds a mapping from the specified key to the specified value, 135 * replacing the previous mapping from the specified key if there 136 * was one. 137 */ put(int key, boolean value)138 public void put(int key, boolean value) { 139 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); 140 141 if (i >= 0) { 142 mValues[i] = value; 143 } else { 144 i = ~i; 145 146 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); 147 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 148 mSize++; 149 } 150 } 151 152 /** 153 * Returns the number of key-value mappings that this SparseBooleanArray 154 * currently stores. 155 */ size()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 * SparseBooleanArray stores. 164 * 165 * <p>The keys corresponding to indices in ascending order are guaranteed to 166 * be in ascending order, e.g., <code>keyAt(0)</code> will return the 167 * smallest key and <code>keyAt(size()-1)</code> will return the largest 168 * key.</p> 169 * 170 * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for 171 * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an 172 * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting 173 * {@link android.os.Build.VERSION_CODES#Q} and later.</p> 174 */ keyAt(int index)175 public int keyAt(int index) { 176 if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { 177 // The array might be slightly bigger than mSize, in which case, indexing won't fail. 178 // Check if exception should be thrown outside of the critical path. 179 throw new ArrayIndexOutOfBoundsException(index); 180 } 181 return mKeys[index]; 182 } 183 184 /** 185 * Given an index in the range <code>0...size()-1</code>, returns 186 * the value from the <code>index</code>th key-value mapping that this 187 * SparseBooleanArray stores. 188 * 189 * <p>The values corresponding to indices in ascending order are guaranteed 190 * to be associated with keys in ascending order, e.g., 191 * <code>valueAt(0)</code> will return the value associated with the 192 * smallest key and <code>valueAt(size()-1)</code> will return the value 193 * associated with the largest key.</p> 194 * 195 * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for 196 * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an 197 * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting 198 * {@link android.os.Build.VERSION_CODES#Q} and later.</p> 199 */ valueAt(int index)200 public boolean valueAt(int index) { 201 if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { 202 // The array might be slightly bigger than mSize, in which case, indexing won't fail. 203 // Check if exception should be thrown outside of the critical path. 204 throw new ArrayIndexOutOfBoundsException(index); 205 } 206 return mValues[index]; 207 } 208 209 /** 210 * Directly set the value at a particular index. 211 * 212 * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for 213 * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an 214 * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting 215 * {@link android.os.Build.VERSION_CODES#Q} and later.</p> 216 */ setValueAt(int index, boolean value)217 public void setValueAt(int index, boolean value) { 218 if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { 219 // The array might be slightly bigger than mSize, in which case, indexing won't fail. 220 // Check if exception should be thrown outside of the critical path. 221 throw new ArrayIndexOutOfBoundsException(index); 222 } 223 mValues[index] = value; 224 } 225 226 /** @hide */ setKeyAt(int index, int key)227 public void setKeyAt(int index, int key) { 228 if (index >= mSize) { 229 // The array might be slightly bigger than mSize, in which case, indexing won't fail. 230 throw new ArrayIndexOutOfBoundsException(index); 231 } 232 mKeys[index] = key; 233 } 234 235 /** 236 * Returns the index for which {@link #keyAt} would return the 237 * specified key, or a negative number if the specified 238 * key is not mapped. 239 */ indexOfKey(int key)240 public int indexOfKey(int key) { 241 return ContainerHelpers.binarySearch(mKeys, mSize, key); 242 } 243 244 /** 245 * Returns an index for which {@link #valueAt} would return the 246 * specified key, or a negative number if no keys map to the 247 * specified value. 248 * Beware that this is a linear search, unlike lookups by key, 249 * and that multiple keys can map to the same value and this will 250 * find only one of them. 251 */ indexOfValue(boolean value)252 public int indexOfValue(boolean value) { 253 for (int i = 0; i < mSize; i++) 254 if (mValues[i] == value) 255 return i; 256 257 return -1; 258 } 259 260 /** 261 * Removes all key-value mappings from this SparseBooleanArray. 262 */ clear()263 public void clear() { 264 mSize = 0; 265 } 266 267 /** 268 * Puts a key/value pair into the array, optimizing for the case where 269 * the key is greater than all existing keys in the array. 270 */ append(int key, boolean value)271 public void append(int key, boolean value) { 272 if (mSize != 0 && key <= mKeys[mSize - 1]) { 273 put(key, value); 274 return; 275 } 276 277 mKeys = GrowingArrayUtils.append(mKeys, mSize, key); 278 mValues = GrowingArrayUtils.append(mValues, mSize, value); 279 mSize++; 280 } 281 282 @Override hashCode()283 public int hashCode() { 284 int hashCode = mSize; 285 for (int i = 0; i < mSize; i++) { 286 hashCode = 31 * hashCode + mKeys[i] | (mValues[i] ? 1 : 0); 287 } 288 return hashCode; 289 } 290 291 @Override equals(Object that)292 public boolean equals(Object that) { 293 if (this == that) { 294 return true; 295 } 296 297 if (!(that instanceof SparseBooleanArray)) { 298 return false; 299 } 300 301 SparseBooleanArray other = (SparseBooleanArray) that; 302 if (mSize != other.mSize) { 303 return false; 304 } 305 306 for (int i = 0; i < mSize; i++) { 307 if (mKeys[i] != other.mKeys[i]) { 308 return false; 309 } 310 if (mValues[i] != other.mValues[i]) { 311 return false; 312 } 313 } 314 return true; 315 } 316 317 /** 318 * {@inheritDoc} 319 * 320 * <p>This implementation composes a string by iterating over its mappings. 321 */ 322 @Override toString()323 public String toString() { 324 if (size() <= 0) { 325 return "{}"; 326 } 327 328 StringBuilder buffer = new StringBuilder(mSize * 28); 329 buffer.append('{'); 330 for (int i=0; i<mSize; i++) { 331 if (i > 0) { 332 buffer.append(", "); 333 } 334 int key = keyAt(i); 335 buffer.append(key); 336 buffer.append('='); 337 boolean value = valueAt(i); 338 buffer.append(value); 339 } 340 buffer.append('}'); 341 return buffer.toString(); 342 } 343 344 @UnsupportedAppUsage(maxTargetSdk = 28) // Use keyAt(int) 345 private int[] mKeys; 346 @UnsupportedAppUsage(maxTargetSdk = 28) // Use valueAt(int), setValueAt(int, boolean) 347 private boolean[] mValues; 348 @UnsupportedAppUsage(maxTargetSdk = 28) // Use size() 349 private int mSize; 350 } 351