13e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn/* 23e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * Copyright (C) 2013 The Android Open Source Project 33e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * 43e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * Licensed under the Apache License, Version 2.0 (the "License"); 53e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * you may not use this file except in compliance with the License. 63e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * You may obtain a copy of the License at 73e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * 83e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * http://www.apache.org/licenses/LICENSE-2.0 93e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * 103e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * Unless required by applicable law or agreed to in writing, software 113e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * distributed under the License is distributed on an "AS IS" BASIS, 123e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 133e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * See the License for the specific language governing permissions and 143e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn * limitations under the License. 153e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn */ 163e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 173e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackbornpackage android.util; 183e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 193e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackbornclass ContainerHelpers { 203e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 213e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn // This is Arrays.binarySearch(), but doesn't do any argument validation. 223e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn static int binarySearch(int[] array, int size, int value) { 233e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int lo = 0; 243e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int hi = size - 1; 253e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 263e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn while (lo <= hi) { 273e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn final int mid = (lo + hi) >>> 1; 283e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn final int midVal = array[mid]; 293e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 303e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (midVal < value) { 313e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn lo = mid + 1; 323e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } else if (midVal > value) { 333e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn hi = mid - 1; 343e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } else { 353e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return mid; // value found 363e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 373e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 383e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return ~lo; // value not present 393e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 403e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 413e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn static int binarySearch(long[] array, int size, long value) { 423e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int lo = 0; 433e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn int hi = size - 1; 443e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 453e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn while (lo <= hi) { 463e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn final int mid = (lo + hi) >>> 1; 473e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn final long midVal = array[mid]; 483e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn 493e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn if (midVal < value) { 503e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn lo = mid + 1; 513e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } else if (midVal > value) { 523e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn hi = mid - 1; 533e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } else { 543e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return mid; // value found 553e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 563e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 573e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn return ~lo; // value not present 583e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn } 593e82ba1a67b0c756ab6a289985f4cfc53725b311Dianne Hackborn} 60