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 * SparseBooleanArrays map integers to booleans. 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unlike a normal array of booleans 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * there can be gaps in the indices. It is intended to be more efficient 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * than using a HashMap to map Integers to Booleans. 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 2735bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganovpublic class SparseBooleanArray implements Cloneable { 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Creates a new SparseBooleanArray containing no mappings. 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public SparseBooleanArray() { 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project this(10); 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Creates a new SparseBooleanArray containing no mappings that will not 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * require any additional memory allocation to store the specified 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * number of mappings. 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public SparseBooleanArray(int initialCapacity) { 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity); 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = new int[initialCapacity]; 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = new boolean[initialCapacity]; 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = 0; 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 4835bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov @Override 4935bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov public SparseBooleanArray clone() { 5035bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov SparseBooleanArray clone = null; 5135bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov try { 5235bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone = (SparseBooleanArray) super.clone(); 5335bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone.mKeys = mKeys.clone(); 5435bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov clone.mValues = mValues.clone(); 5535bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } catch (CloneNotSupportedException cnse) { 5635bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov /* ignore */ 5735bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } 5835bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov return clone; 5935bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov } 6035bfedeaba724aeadc6f6c890269cb6bf7ef42f5Svetoslav Ganov 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Gets the boolean mapped from the specified key, or <code>false</code> 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * if no such mapping has been made. 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public boolean get(int key) { 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return get(key, false); 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Gets the boolean mapped from the specified key, or the specified value 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * if no such mapping has been made. 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public boolean get(int key, boolean valueIfKeyNotFound) { 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i < 0) { 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return valueIfKeyNotFound; 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mValues[i]; 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Removes the mapping from the specified key, if there was any. 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void delete(int key) { 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1)); 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, i + 1, mValues, i, mSize - (i + 1)); 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize--; 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Adds a mapping from the specified key to the specified value, 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * replacing the previous mapping from the specified key if there 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * was one. 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void put(int key, boolean value) { 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i = binarySearch(mKeys, 0, mSize, key); 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (i >= 0) { 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[i] = value; 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project i = ~i; 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize >= mKeys.length) { 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int n = ArrayUtils.idealIntArraySize(mSize + 1); 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nkeys = new int[n]; 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean[] nvalues = new boolean[n]; 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n); 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = nkeys; 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = nvalues; 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize - i != 0) { 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseBooleanArray", "move " + (mSize - i)); 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys[i] = key; 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[i] = value; 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize++; 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the number of key-value mappings that this SparseBooleanArray 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * currently stores. 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int size() { 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mSize; 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Given an index in the range <code>0...size()-1</code>, returns 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the key from the <code>index</code>th key-value mapping that this 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * SparseBooleanArray stores. 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int keyAt(int index) { 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mKeys[index]; 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Given an index in the range <code>0...size()-1</code>, returns 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the value from the <code>index</code>th key-value mapping that this 1559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * SparseBooleanArray stores. 1569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public boolean valueAt(int index) { 1589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return mValues[index]; 1599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns the index for which {@link #keyAt} would return the 1639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified key, or a negative number if the specified 1649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * key is not mapped. 1659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int indexOfKey(int key) { 1679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return binarySearch(mKeys, 0, mSize, key); 1689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Returns an index for which {@link #valueAt} would return the 1729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified key, or a negative number if no keys map to the 1739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * specified value. 1749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Beware that this is a linear search, unlike lookups by key, 1759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * and that multiple keys can map to the same value and this will 1769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * find only one of them. 1779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public int indexOfValue(boolean value) { 1799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (int i = 0; i < mSize; i++) 1809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mValues[i] == value) 1819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return i; 1829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return -1; 1849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Removes all key-value mappings from this SparseBooleanArray. 1889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void clear() { 1909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = 0; 1919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 1949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Puts a key/value pair into the array, optimizing for the case where 1959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * the key is greater than all existing keys in the array. 1969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project public void append(int key, boolean value) { 1989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (mSize != 0 && key <= mKeys[mSize - 1]) { 1999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project put(key, value); 2009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return; 2019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int pos = mSize; 2049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (pos >= mKeys.length) { 2059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int n = ArrayUtils.idealIntArraySize(pos + 1); 2069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int[] nkeys = new int[n]; 2089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project boolean[] nvalues = new boolean[n]; 2099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Log.e("SparseBooleanArray", "grow " + mKeys.length + " to " + n); 2119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 2129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 2139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys = nkeys; 2159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues = nvalues; 2169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mKeys[pos] = key; 2199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mValues[pos] = value; 2209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project mSize = pos + 1; 2219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private static int binarySearch(int[] a, int start, int len, int key) { 2249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int high = start + len, low = start - 1, guess; 2259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project while (high - low > 1) { 2279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project guess = (high + low) / 2; 2289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (a[guess] < key) 2309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project low = guess; 2319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project high = guess; 2339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (high == start + len) 2369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ~(start + len); 2379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else if (a[high] == key) 2389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return high; 2399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project else 2409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return ~high; 2419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 2429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 2439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private int[] mKeys; 2449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private boolean[] mValues; 2459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project private int mSize; 2469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 247