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