13168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy/* 23168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Copyright (C) 2011 The Android Open Source Project 33168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * 43168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Licensed under the Apache License, Version 2.0 (the "License"); 53168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * you may not use this file except in compliance with the License. 63168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * You may obtain a copy of the License at 73168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * 83168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * http://www.apache.org/licenses/LICENSE-2.0 93168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * 103168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Unless required by applicable law or agreed to in writing, software 113168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * distributed under the License is distributed on an "AS IS" BASIS, 123168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * See the License for the specific language governing permissions and 143168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * limitations under the License. 153168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 163168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 173168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedypackage com.android.mail.utils; 183168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 193168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy/** 203168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * SparseLongArrays map integers to longs. Unlike a normal array of longs, 213168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * there can be gaps in the indices. It is intended to be more efficient 223168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * than using a HashMap to map Integers to Longs. 233168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * 243168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * TODO: Remove this when there's an equivalent in the support library. This was changed slightly 253168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * to remove the dependency on com.android.internal.util.ArrayUtils. 263168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 273168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedypublic class SparseLongArray implements Cloneable { 283168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 293168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy private int[] mKeys; 303168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy private long[] mValues; 313168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy private int mSize; 323168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 333168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 343168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Creates a new SparseLongArray containing no mappings. 353168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 363168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public SparseLongArray() { 373168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy this(10); 383168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 393168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 403168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 413168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Creates a new SparseLongArray containing no mappings that will not 423168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * require any additional memory allocation to store the specified 433168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * number of mappings. 443168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 453168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public SparseLongArray(int initialCapacity) { 463168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mKeys = new int[initialCapacity]; 473168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mValues = new long[initialCapacity]; 483168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mSize = 0; 493168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 503168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 513168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy @Override 523168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public SparseLongArray clone() { 533168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy SparseLongArray clone = null; 543168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy try { 553168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy clone = (SparseLongArray) super.clone(); 563168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy clone.mKeys = mKeys.clone(); 573168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy clone.mValues = mValues.clone(); 583168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } catch (CloneNotSupportedException cnse) { 593168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /* ignore */ 603168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 613168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return clone; 623168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 633168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 643168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 653168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Gets the long mapped from the specified key, or <code>0</code> 663168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * if no such mapping has been made. 673168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 683168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public long get(int key) { 693168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return get(key, 0); 703168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 713168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 723168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 733168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Gets the long mapped from the specified key, or the specified value 743168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * if no such mapping has been made. 753168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 763168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public long get(int key, long valueIfKeyNotFound) { 773168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int i = binarySearch(mKeys, 0, mSize, key); 783168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 793168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (i < 0) { 803168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return valueIfKeyNotFound; 813168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } else { 823168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return mValues[i]; 833168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 843168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 853168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 863168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 873168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Removes the mapping from the specified key, if there was any. 883168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 893168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public void delete(int key) { 903168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int i = binarySearch(mKeys, 0, mSize, key); 913168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 923168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (i >= 0) { 933168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy removeAt(i); 943168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 953168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 963168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 973168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 983168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Removes the mapping at the given index. 993168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1003168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public void removeAt(int index) { 1013168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); 1023168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1)); 1033168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mSize--; 1043168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1053168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1063168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1073168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Adds a mapping from the specified key to the specified value, 1083168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * replacing the previous mapping from the specified key if there 1093168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * was one. 1103168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1113168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public void put(int key, long value) { 1123168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int i = binarySearch(mKeys, 0, mSize, key); 1133168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1143168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (i >= 0) { 1153168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mValues[i] = value; 1163168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } else { 1173168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy i = ~i; 1183168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1193168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (mSize >= mKeys.length) { 1203168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy growKeyAndValueArrays(mSize + 1); 1213168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1223168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1233168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (mSize - i != 0) { 1243168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); 1253168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mValues, i, mValues, i + 1, mSize - i); 1263168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1273168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1283168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mKeys[i] = key; 1293168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mValues[i] = value; 1303168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mSize++; 1313168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1323168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1333168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1343168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1353168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Returns the number of key-value mappings that this SparseIntArray 1363168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * currently stores. 1373168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1383168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public int size() { 1393168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return mSize; 1403168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1413168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1423168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1433168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Given an index in the range <code>0...size()-1</code>, returns 1443168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * the key from the <code>index</code>th key-value mapping that this 1453168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * SparseLongArray stores. 1463168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1473168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public int keyAt(int index) { 1483168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return mKeys[index]; 1493168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1503168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1513168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1523168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Given an index in the range <code>0...size()-1</code>, returns 1533168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * the value from the <code>index</code>th key-value mapping that this 1543168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * SparseLongArray stores. 1553168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1563168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public long valueAt(int index) { 1573168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return mValues[index]; 1583168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1593168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1603168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1613168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Returns the index for which {@link #keyAt} would return the 1623168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * specified key, or a negative number if the specified 1633168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * key is not mapped. 1643168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1653168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public int indexOfKey(int key) { 1663168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return binarySearch(mKeys, 0, mSize, key); 1673168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1683168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1693168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1703168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Returns an index for which {@link #valueAt} would return the 1713168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * specified key, or a negative number if no keys map to the 1723168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * specified value. 1733168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Beware that this is a linear search, unlike lookups by key, 1743168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * and that multiple keys can map to the same value and this will 1753168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * find only one of them. 1763168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1773168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public int indexOfValue(long value) { 1783168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy for (int i = 0; i < mSize; i++) 1793168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (mValues[i] == value) 1803168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return i; 1813168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1823168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return -1; 1833168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1843168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1853168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1863168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Removes all key-value mappings from this SparseIntArray. 1873168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1883168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public void clear() { 1893168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mSize = 0; 1903168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 1913168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 1923168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy /** 1933168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * Puts a key/value pair into the array, optimizing for the case where 1943168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy * the key is greater than all existing keys in the array. 1953168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy */ 1963168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy public void append(int key, long value) { 1973168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (mSize != 0 && key <= mKeys[mSize - 1]) { 1983168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy put(key, value); 1993168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return; 2003168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2013168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2023168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int pos = mSize; 2033168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (pos >= mKeys.length) { 2043168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy growKeyAndValueArrays(pos + 1); 2053168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2063168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2073168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mKeys[pos] = key; 2083168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mValues[pos] = value; 2093168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mSize = pos + 1; 2103168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2113168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2123168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy private void growKeyAndValueArrays(int minNeededSize) { 2133168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int n = minNeededSize; 2143168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2153168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int[] nkeys = new int[n]; 2163168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy long[] nvalues = new long[n]; 2173168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2183168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); 2193168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy System.arraycopy(mValues, 0, nvalues, 0, mValues.length); 2203168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2213168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mKeys = nkeys; 2223168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy mValues = nvalues; 2233168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2243168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2253168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy private static int binarySearch(int[] a, int start, int len, long key) { 2263168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy int high = start + len, low = start - 1, guess; 2273168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2283168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy while (high - low > 1) { 2293168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy guess = (high + low) / 2; 2303168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2313168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (a[guess] < key) 2323168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy low = guess; 2333168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy else 2343168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy high = guess; 2353168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2363168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy 2373168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy if (high == start + len) 2383168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return ~(start + len); 2393168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy else if (a[high] == key) 2403168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return high; 2413168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy else 2423168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy return ~high; 2433168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy } 2443168c2a75edbf597932ab9edfd96037ceba99b35Scott Kennedy} 245