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