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