Class SortedLists
- java.lang.Object
-
- com.google.common.collect.SortedLists
-
@GwtCompatible @Beta final class SortedLists extends java.lang.Object
Static methods pertaining to sortedList
instances.In this documentation, the terms greatest, greater, least, and lesser are considered to refer to the comparator on the elements, and the terms first and last are considered to refer to the elements' ordering in a list.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
SortedLists.KeyAbsentBehavior
A specification for which index to return if the list contains no elements that compare as equal to the key.(package private) static class
SortedLists.KeyPresentBehavior
A specification for which index to return if the list contains at least one element that compares as equal to the key.
-
Constructor Summary
Constructors Modifier Constructor Description private
SortedLists()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <E extends java.lang.Comparable>
intbinarySearch(java.util.List<? extends E> list, E e, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Searches the specified naturally ordered list for the specified object using the binary search algorithm.static <E> int
binarySearch(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Searches the specified list for the specified object using the binary search algorithm.static <E,K extends java.lang.Comparable>
intbinarySearch(java.util.List<E> list, Function<? super E,K> keyFunction, K key, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Binary searches the list for the specified key, using the specified key function.static <E,K>
intbinarySearch(java.util.List<E> list, Function<? super E,K> keyFunction, K key, java.util.Comparator<? super K> keyComparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Binary searches the list for the specified key, using the specified key function.
-
-
-
Method Detail
-
binarySearch
public static <E extends java.lang.Comparable> int binarySearch(java.util.List<? extends E> list, E e, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Searches the specified naturally ordered list for the specified object using the binary search algorithm.Equivalent to
binarySearch(List, Function, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)
usingOrdering.natural()
.
-
binarySearch
public static <E,K extends java.lang.Comparable> int binarySearch(java.util.List<E> list, Function<? super E,K> keyFunction, K key, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Binary searches the list for the specified key, using the specified key function.Equivalent to
binarySearch(List, Function, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)
usingOrdering.natural()
.
-
binarySearch
public static <E,K> int binarySearch(java.util.List<E> list, Function<? super E,K> keyFunction, K key, java.util.Comparator<? super K> keyComparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Binary searches the list for the specified key, using the specified key function.Equivalent to
binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)
usingLists.transform(list, keyFunction)
.
-
binarySearch
public static <E> int binarySearch(java.util.List<? extends E> list, E key, java.util.Comparator<? super E> comparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior)
Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator (as by theCollections.sort(List, Comparator)
method), prior to making this call. If it is not sorted, the results are undefined.If there are elements in the list which compare as equal to the key, the choice of
SortedLists.KeyPresentBehavior
decides which index is returned. If no elements compare as equal to the key, the choice ofSortedLists.KeyAbsentBehavior
decides which index is returned.This method runs in log(n) time on random-access lists, which offer near-constant-time access to each list element.
- Parameters:
list
- the list to be searched.key
- the value to be searched for.comparator
- the comparator by which the list is ordered.presentBehavior
- the specification for what to do if at least one element of the list compares as equal to the key.absentBehavior
- the specification for what to do if no elements of the list compare as equal to the key.- Returns:
- the index determined by the
KeyPresentBehavior
, if the key is in the list; otherwise the index determined by theKeyAbsentBehavior
.
-
-