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