1ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver/* 2ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Copyright 2013, Google Inc. 3ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * All rights reserved. 4ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * 5ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Redistribution and use in source and binary forms, with or without 6ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * modification, are permitted provided that the following conditions are 7ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * met: 8ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * 9ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * * Redistributions of source code must retain the above copyright 10ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * notice, this list of conditions and the following disclaimer. 11ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * * Redistributions in binary form must reproduce the above 12ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * copyright notice, this list of conditions and the following disclaimer 13ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * in the documentation and/or other materials provided with the 14ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * distribution. 15ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * * Neither the name of Google Inc. nor the names of its 16ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * contributors may be used to endorse or promote products derived from 17ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * this software without specific prior written permission. 18ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * 19ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 31ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 32ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruverpackage org.jf.util; 33ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 34ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver/** 35ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * SparseIntArrays map integers to integers. Unlike a normal array of integers, 36ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * there can be gaps in the indices. It is intended to be more efficient 37ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * than using a HashMap to map Integers to Integers. 38ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 39ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruverpublic class SparseIntArray { 40ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 41ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Creates a new SparseIntArray containing no mappings. 42ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 43ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public SparseIntArray() { 44ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver this(10); 45ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 46ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 47ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 48ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Creates a new SparseIntArray containing no mappings that will not 49ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * require any additional memory allocation to store the specified 50ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * number of mappings. 51ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 52ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public SparseIntArray(int initialCapacity) { 53ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mKeys = new int[initialCapacity]; 54ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues = new int[initialCapacity]; 55ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mSize = 0; 56ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 57ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 58ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 59ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Gets the int mapped from the specified key, or <code>0</code> 60ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * if no such mapping has been made. 61ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 62ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int get(int key) { 63ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return get(key, 0); 64ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 65ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 66ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 67ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Gets the int mapped from the specified key, or the specified value 68ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * if no such mapping has been made. 69ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 70ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int get(int key, int valueIfKeyNotFound) { 71ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int i = binarySearch(mKeys, 0, mSize, key); 72ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 73ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (i < 0) { 74ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return valueIfKeyNotFound; 75ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } else { 76ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mValues[i]; 77ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 78ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 79ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 80ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 81ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Gets the int mapped from the specified key, or if not present, the 82ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * closest key that is less than the specified key. 83ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 84ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int getClosestSmaller(int key) { 85ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int i = binarySearch(mKeys, 0, mSize, key); 86ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 87ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (i < 0) { 88ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver i = ~i; 89ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (i > 0) { 90ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver i--; 91ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 92ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mValues[i]; 93ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } else { 94ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mValues[i]; 95ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 96ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 97ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 98ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 99ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Removes the mapping from the specified key, if there was any. 100ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 101ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public void delete(int key) { 102ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int i = binarySearch(mKeys, 0, mSize, key); 103ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 104ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (i >= 0) { 105ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver removeAt(i); 106ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 107ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 108ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 109ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 110ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Removes the mapping at the given index. 111ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 112ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public void removeAt(int index) { 113ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 114ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 115ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mSize--; 116ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 117ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 118ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 119ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Adds a mapping from the specified key to the specified value, 120ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * replacing the previous mapping from the specified key if there 121ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * was one. 122ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 123ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public void put(int key, int value) { 124ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int i = binarySearch(mKeys, 0, mSize, key); 125ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 126ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (i >= 0) { 127ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues[i] = value; 128ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } else { 129ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver i = ~i; 130ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 131ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (mSize >= mKeys.length) { 132ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int n = Math.max(mSize + 1, mKeys.length * 2); 133ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 134ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int[] nkeys = new int[n]; 135ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int[] nvalues = new int[n]; 136ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 137ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 138ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 139ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 140ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 141ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mKeys = nkeys; 142ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues = nvalues; 143ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 144ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 145ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (mSize - i != 0) { 146ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver // Log.e("SparseIntArray", "move " + (mSize - i)); 147ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 148ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 149ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 150ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 151ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mKeys[i] = key; 152ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues[i] = value; 153ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mSize++; 154ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 155ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 156ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 157ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 158ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Returns the number of key-value mappings that this SparseIntArray 159ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * currently stores. 160ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 161ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int size() { 162ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mSize; 163ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 164ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 165ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 166ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Given an index in the range <code>0...size()-1</code>, returns 167ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * the key from the <code>index</code>th key-value mapping that this 168ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * SparseIntArray stores. 169ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 170ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int keyAt(int index) { 171ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mKeys[index]; 172ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 173ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 174ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 175ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Given an index in the range <code>0...size()-1</code>, returns 176ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * the value from the <code>index</code>th key-value mapping that this 177ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * SparseIntArray stores. 178ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 179ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int valueAt(int index) { 180ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return mValues[index]; 181ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 182ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 183ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 184ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Returns the index for which {@link #keyAt} would return the 185ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * specified key, or a negative number if the specified 186ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * key is not mapped. 187ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 188ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int indexOfKey(int key) { 189ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return binarySearch(mKeys, 0, mSize, key); 190ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 191ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 192ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 193ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Returns an index for which {@link #valueAt} would return the 194ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * specified key, or a negative number if no keys map to the 195ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * specified value. 196ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Beware that this is a linear search, unlike lookups by key, 197ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * and that multiple keys can map to the same value and this will 198ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * find only one of them. 199ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 200ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public int indexOfValue(int value) { 201ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver for (int i = 0; i < mSize; i++) 202ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (mValues[i] == value) 203ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return i; 204ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 205ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return -1; 206ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 207ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 208ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 209ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Removes all key-value mappings from this SparseIntArray. 210ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 211ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public void clear() { 212ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mSize = 0; 213ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 214ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 215ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver /** 216ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * Puts a key/value pair into the array, optimizing for the case where 217ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver * the key is greater than all existing keys in the array. 218ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver */ 219ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver public void append(int key, int value) { 220ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (mSize != 0 && key <= mKeys[mSize - 1]) { 221ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver put(key, value); 222ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return; 223ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 224ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 225ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int pos = mSize; 226ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (pos >= mKeys.length) { 227ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int n = Math.max(pos + 1, mKeys.length * 2); 228ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 229ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int[] nkeys = new int[n]; 230ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int[] nvalues = new int[n]; 231ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 232ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); 233ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 234ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 235ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 236ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mKeys = nkeys; 237ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues = nvalues; 238ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 239ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 240ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mKeys[pos] = key; 241ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mValues[pos] = value; 242ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver mSize = pos + 1; 243ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 244ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 245ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver private static int binarySearch(int[] a, int start, int len, int key) { 246ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver int high = start + len, low = start - 1, guess; 247ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 248ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver while (high - low > 1) { 249ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver guess = (high + low) / 2; 250ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 251ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (a[guess] < key) 252ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver low = guess; 253ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver else 254ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver high = guess; 255ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 256ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 257ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver if (high == start + len) 258ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return ~(start + len); 259ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver else if (a[high] == key) 260ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return high; 261ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver else 262ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver return ~high; 263ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver } 264ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver 265ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver private int[] mKeys; 266ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver private int[] mValues; 267ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver private int mSize; 268ffe82bdcb5c914b3a60b630c6d3abe6fc9229decBen Gruver} 269