11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2010 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the License 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or implied. See the License for the specific language governing permissions and limitations under 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.RandomAccess; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Static methods pertaining to sorted {@link List} instances. 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * In this documentation, the terms <i>greatest</i>, <i>greater</i>, <i>least</i>, and 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <i>lesser</i> are considered to refer to the comparator on the elements, and the terms 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <i>first</i> and <i>last</i> are considered to refer to the elements' ordering in a 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * list. 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta final class SortedLists { 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private SortedLists() {} 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A specification for which index to return if the list contains at least one element that 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * compares as equal to the key. 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public enum KeyPresentBehavior { 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of any list element that compares as equal to the key. No guarantees are 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * made as to which index is returned, if more than one element compares as equal to the key. 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ANY_PRESENT { 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert <E> int resultIndex( 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) { 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return foundIndex; 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the last list element that compares as equal to the key. 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LAST_PRESENT { 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert <E> int resultIndex( 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) { 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Of course, we have to use binary search to find the precise 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // breakpoint... 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int lower = foundIndex; 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int upper = list.size() - 1; 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Everything between lower and upper inclusive compares at >= 0. 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (lower < upper) { 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int middle = (lower + upper + 1) >>> 1; 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int c = comparator.compare(list.get(middle), key); 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (c > 0) { 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert upper = middle - 1; 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { // c == 0 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert lower = middle; 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return lower; 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the first list element that compares as equal to the key. 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FIRST_PRESENT { 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert <E> int resultIndex( 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) { 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Of course, we have to use binary search to find the precise 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // breakpoint... 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int lower = 0; 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int upper = foundIndex; 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Of course, we have to use binary search to find the precise breakpoint... 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Everything between lower and upper inclusive compares at <= 0. 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (lower < upper) { 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int middle = (lower + upper) >>> 1; 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int c = comparator.compare(list.get(middle), key); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (c < 0) { 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert lower = middle + 1; 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { // c == 0 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert upper = middle; 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return lower; 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the first list element that compares as greater than the key, or {@code 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * list.size()} if there is no such element. 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FIRST_AFTER { 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E> int resultIndex( 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) { 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1; 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the last list element that compares as less than the key, or {@code -1} 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * if there is no such element. 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LAST_BEFORE { 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E> int resultIndex( 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) { 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1; 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract <E> int resultIndex( 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex); 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A specification for which index to return if the list contains no elements that compare as 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equal to the key. 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public enum KeyAbsentBehavior { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the next lower element in the list, or {@code -1} if there is no such 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element. 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NEXT_LOWER { 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert <E> int resultIndex(int higherIndex) { 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return higherIndex - 1; 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return the index of the next higher element in the list, or {@code list.size()} if there is 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * no such element. 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NEXT_HIGHER { 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E> int resultIndex(int higherIndex) { 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return higherIndex; 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }, 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which the key would be inserted into the list: the index of the next higher element in the 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * list, or {@code list.size()} if there is no such element. 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * list that compares as equal to the key. 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This is equivalent to the behavior of 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link java.util.Collections#binarySearch(List, Object)} when the key isn't present, since 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code ~insertionIndex} is equal to {@code -1 - insertionIndex}. 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert INVERTED_INSERTION_INDEX { 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public <E> int resultIndex(int higherIndex) { 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ~higherIndex; 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract <E> int resultIndex(int higherIndex); 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Searches the specified naturally ordered list for the specified object using the binary search 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * algorithm. 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior, 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * KeyAbsentBehavior)} using {@link Ordering#natural}. 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E extends Comparable> int binarySearch(List<? extends E> list, E e, 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) { 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(e); 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return binarySearch( 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list, checkNotNull(e), Ordering.natural(), presentBehavior, absentBehavior); 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Binary searches the list for the specified key, using the specified key function. 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior, 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * KeyAbsentBehavior)} using {@link Ordering#natural}. 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E, K extends Comparable> int binarySearch(List<E> list, 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<? super E, K> keyFunction, K key, KeyPresentBehavior presentBehavior, 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyAbsentBehavior absentBehavior) { 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return binarySearch( 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list, 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert keyFunction, 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert key, 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Ordering.natural(), 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert presentBehavior, 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert absentBehavior); 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Binary searches the list for the specified key, using the specified key function. 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Equivalent to 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)} using 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Lists#transform(List, Function) Lists.transform(list, keyFunction)}. 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E, K> int binarySearch( 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<E> list, 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Function<? super E, K> keyFunction, 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K key, 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super K> keyComparator, 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyPresentBehavior presentBehavior, 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyAbsentBehavior absentBehavior) { 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return binarySearch( 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Searches the specified list for the specified object using the binary search algorithm. The 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * list must be sorted into ascending order according to the specified comparator (as by the 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to making this call. If it is not sorted, the results are undefined. 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If there are elements in the list which compare as equal to the key, the choice of 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the key, the choice of {@link KeyAbsentBehavior} decides which index is returned. 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * access to each list element. 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param list the list to be searched. 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param key the value to be searched for. 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param comparator the comparator by which the list is ordered. 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param presentBehavior the specification for what to do if at least one element of the list 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * compares as equal to the key. 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param absentBehavior the specification for what to do if no elements of the list compare as 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equal to the key. 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list; 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * otherwise the index determined by the {@code KeyAbsentBehavior}. 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> int binarySearch(List<? extends E> list, @Nullable E key, 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Comparator<? super E> comparator, KeyPresentBehavior presentBehavior, 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert KeyAbsentBehavior absentBehavior) { 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(comparator); 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(list); 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(presentBehavior); 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(absentBehavior); 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!(list instanceof RandomAccess)) { 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list = Lists.newArrayList(list); 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): benchmark when it's best to do a linear search 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int lower = 0; 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int upper = list.size() - 1; 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (lower <= upper) { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int middle = (lower + upper) >>> 1; 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int c = comparator.compare(key, list.get(middle)); 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (c < 0) { 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert upper = middle - 1; 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (c > 0) { 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert lower = middle + 1; 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return lower + presentBehavior.resultIndex( 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert comparator, key, list.subList(lower, upper + 1), middle - lower); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return absentBehavior.resultIndex(lower); 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 285