19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2006 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.util; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectimport com.android.internal.util.ArrayUtils; 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * SparseIntArrays map integers to integers. Unlike a normal array of integers, 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * there can be gaps in the indices. It is intended to be more efficient 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * than using a HashMap to map Integers to Integers. 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2635bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganovpublic class SparseIntArray implements Cloneable { 2735bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov 2835bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov private int[] mKeys; 2935bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov private int[] mValues; 3035bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov private int mSize; 3135bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Creates a new SparseIntArray containing no mappings. 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public SparseIntArray() { 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project this(10); 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Creates a new SparseIntArray containing no mappings that will not 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * require any additional memory allocation to store the specified 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * number of mappings. 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public SparseIntArray(int initialCapacity) { 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = new int[initialCapacity]; 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = new int[initialCapacity]; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = 0; 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 5235bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov @Override 5335bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov public SparseIntArray clone() { 5435bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov SparseIntArray clone = null; 5535bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov try { 5635bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone = (SparseIntArray) super.clone(); 5735bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone.mKeys = mKeys.clone(); 5835bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone.mValues = mValues.clone(); 5935bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } catch (CloneNotSupportedException cnse) { 6035bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov /* ignore */ 6135bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } 6235bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov return clone; 6335bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } 6435bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Gets the int mapped from the specified key, or <code>0</code> 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * if no such mapping has been made. 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int get(int key) { 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return get(key, 0); 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Gets the int mapped from the specified key, or the specified value 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * if no such mapping has been made. 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int get(int key, int valueIfKeyNotFound) { 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i < 0) { 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return valueIfKeyNotFound; 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mValues[i]; 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Removes the mapping from the specified key, if there was any. 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void delete(int key) { 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project removeAt(i); 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Removes the mapping at the given index. 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void removeAt(int index) { 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize--; 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Adds a mapping from the specified key to the specified value, 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * replacing the previous mapping from the specified key if there 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * was one. 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void put(int key, int value) { 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[i] = value; 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project i = ~i; 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize >= mKeys.length) { 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int n = ArrayUtils.idealIntArraySize(mSize + 1); 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nkeys = new int[n]; 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nvalues = new int[n]; 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = nkeys; 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = nvalues; 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize - i != 0) { 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseIntArray", "move " + (mSize - i)); 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys[i] = key; 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[i] = value; 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize++; 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the number of key-value mappings that this SparseIntArray 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * currently stores. 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int size() { 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mSize; 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Given an index in the range <code>0...size()-1</code>, returns 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the key from the <code>index</code>th key-value mapping that this 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * SparseIntArray stores. 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int keyAt(int index) { 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mKeys[index]; 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Given an index in the range <code>0...size()-1</code>, returns 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the value from the <code>index</code>th key-value mapping that this 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * SparseIntArray stores. 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int valueAt(int index) { 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mValues[index]; 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the index for which {@link #keyAt} would return the 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified key, or a negative number if the specified 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * key is not mapped. 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int indexOfKey(int key) { 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return binarySearch(mKeys, 0, mSize, key); 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns an index for which {@link #valueAt} would return the 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified key, or a negative number if no keys map to the 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified value. 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Beware that this is a linear search, unlike lookups by key, 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * and that multiple keys can map to the same value and this will 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * find only one of them. 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int indexOfValue(int value) { 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < mSize; i++) 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mValues[i] == value) 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return i; 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return -1; 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Removes all key-value mappings from this SparseIntArray. 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void clear() { 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = 0; 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Puts a key/value pair into the array, optimizing for the case where 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the key is greater than all existing keys in the array. 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void append(int key, int value) { 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize != 0 && key <= mKeys[mSize - 1]) { 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project put(key, value); 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return; 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int pos = mSize; 2159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (pos >= mKeys.length) { 2169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int n = ArrayUtils.idealIntArraySize(pos + 1); 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nkeys = new int[n]; 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nvalues = new int[n]; 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = nkeys; 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = nvalues; 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys[pos] = key; 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[pos] = value; 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = pos + 1; 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static int binarySearch(int[] a, int start, int len, int key) { 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int high = start + len, low = start - 1, guess; 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (high - low > 1) { 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project guess = (high + low) / 2; 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (a[guess] < key) 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project low = guess; 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project high = guess; 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (high == start + len) 2479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ~(start + len); 2489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else if (a[high] == key) 2499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return high; 2509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ~high; 2529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 254