1 /* 2 * Copyright 2013, Google LLC 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google LLC nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 package com.android.tools.smali.util; 32 33 import java.util.Comparator; 34 import java.util.List; 35 36 public class LinearSearch { 37 /** 38 * Performs a linear search in a sorted list for key, starting at initialGuess 39 * 40 * @param list The sorted list to search 41 * @param comparator The comparator to use 42 * @param key The key to search for 43 * @param initialGuess An initial guess of the location. 44 * @return If found, the index of the item. If not found, -return + 1 is the index at which the item would be 45 * inserted 46 */ linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess)47 public static <T> int linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess) { 48 int guess = initialGuess; 49 if (guess >= list.size()) { 50 guess = list.size()-1; 51 } 52 int comparison = comparator.compare(list.get(guess), key); 53 if (comparison == 0) { 54 return guess; 55 } 56 if (comparison < 0) { 57 guess++; 58 while (guess < list.size()) { 59 comparison = comparator.compare(list.get(guess), key); 60 if (comparison == 0) { 61 return guess; 62 } 63 if (comparison > 0) { 64 return -(guess+1); 65 } 66 guess++; 67 } 68 return -(list.size()+1); 69 } else { 70 guess--; 71 while (guess >= 0) { 72 comparison = comparator.compare(list.get(guess), key); 73 if (comparison == 0) { 74 return guess; 75 } 76 if (comparison < 0) { 77 return -(guess+2); 78 } 79 guess--; 80 } 81 return -1; 82 } 83 } 84 } 85