Home | History | Annotate | Download | only in util
      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      */
     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      */
     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
     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      */
     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      */
     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      */
    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 */
    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      */
    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      */
    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      */
    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      */
    179     public boolean valueAt(int index) {
    180         return mValues[index];
    181     }
    182 
    183     /** @hide */
    184     public void setValueAt(int index, boolean value) {
    185         mValues[index] = value;
    186     }
    187 
    188     /** @hide */
    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      */
    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      */
    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      */
    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      */
    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
    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
    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
    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