Modifier and Type	Class and Description
pack-priv static enum	SortedLists.KeyAbsentBehavior A specification for which index to return if the list contains no elements that compare as equal to the key.
pack-priv static enum	SortedLists.KeyPresentBehavior A specification for which index to return if the list contains at least one element that compares as equal to the key.

Access	Constructor and Description
private	SortedLists()

Method Summary

Modifier and Type	Method and Description
public static <E extends Comparable<T>> int	binarySearch(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.
public static <E extends @Nullable Object, K extends Comparable<T>> int	binarySearch(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.
public static <E extends @Nullable Object, K extends @Nullable Object> int	binarySearch(List<E> list, Function<? super E, K> keyFunction, K key, Comparator<? super K> keyComparator, SortedLists.KeyPresentBehavior presentBehavior, SortedLists.KeyAbsentBehavior absentBehavior) Binary searches the list for the specified key, using the specified key function.
public static <E extends @Nullable Object> int	Returns: the index determined by the `KeyPresentBehavior`, if the key is in the list; otherwise the index determined by the `KeyAbsentBehavior`. binarySearch(List<? extends E> the list to be searched. list, E the value to be searched for. key, Comparator<? super E> the comparator by which the list is ordered. comparator, SortedLists.KeyPresentBehavior the specification for what to do if at least one element of the list compares as equal to the key. presentBehavior, SortedLists.KeyAbsentBehavior the specification for what to do if no elements of the list compare as equal to the key. absentBehavior) Searches the specified list for the specified object using the binary search algorithm.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

SortedLists	back to summary
private SortedLists()

Method Detail

binarySearch back to summary

binarySearch	back to summary
public static <E extends Comparable<T>> int binarySearch(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)` using `Ordering#natural`.

public static <E extends Comparable<T>> int binarySearch(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) using Ordering#natural.

binarySearch back to summary

binarySearch	back to summary
public static <E extends @Nullable Object, K extends Comparable<T>> int binarySearch(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)` using `Ordering#natural`.

public static <E extends @Nullable Object, K extends Comparable<T>> int binarySearch(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) using Ordering#natural.

binarySearch back to summary

binarySearch	back to summary
public static <E extends @Nullable Object, K extends @Nullable Object> int binarySearch(List<E> list, Function<? super E, K> keyFunction, K key, 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)` using `Lists.transform(list, keyFunction)`.

public static <E extends @Nullable Object, K extends @Nullable Object> int binarySearch(List<E> list, Function<? super E, K> keyFunction, K key, 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) using Lists.transform(list, keyFunction).

binarySearch back to summary

binarySearch	back to summary
public static <E extends @Nullable Object> int binarySearch(List<? extends E> list, E key, 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 the `Collections.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 `KeyPresentBehavior` decides which index is returned. If no elements compare as equal to the key, the choice of `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:List<? extends E> the list to be searched. key:E the value to be searched for. comparator:Comparator<? super E> the comparator by which the list is ordered. presentBehavior:SortedLists.KeyPresentBehavior the specification for what to do if at least one element of the list compares as equal to the key. absentBehavior:SortedLists.KeyAbsentBehavior the specification for what to do if no elements of the list compare as equal to the key. Returns:int the index determined by the `KeyPresentBehavior`, if the key is in the list; otherwise the index determined by the `KeyAbsentBehavior`.

public static <E extends @Nullable Object> int binarySearch(List<? extends E> list, E key, 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 the Collections.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 KeyPresentBehavior decides which index is returned. If no elements compare as equal to the key, the choice of 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:List<? extends E>: the list to be searched.
key:E: the value to be searched for.
comparator:Comparator<? super E>: the comparator by which the list is ordered.
presentBehavior:SortedLists.KeyPresentBehavior: the specification for what to do if at least one element of the list compares as equal to the key.
absentBehavior:SortedLists.KeyAbsentBehavior: the specification for what to do if no elements of the list compare as equal to the key.

Returns:int

the index determined by the KeyPresentBehavior, if the key is in the list; otherwise the index determined by the KeyAbsentBehavior.

com.google.common.collect back to summary

pack-priv sealed Enum SortedLists.KeyAbsentBehavior

Class Inheritance

extends Enum<SortedLists.KeyAbsentBehavior>

java.lang.Object
java.lang.Enum
com.google.common.collect.SortedLists.KeyAbsentBehavior

A specification for which index to return if the list contains no elements that compare as equal to the key.

Field Summary

Modifier and Type	Field and Description
public static final SortedLists.KeyAbsentBehavior	INVERTED_INSERTION_INDEX Return `~insertionIndex`, where `insertionIndex` is defined as the point at which the key would be inserted into the list: the index of the next higher element in the list, or `list.size()` if there is no such element.
public static final SortedLists.KeyAbsentBehavior	NEXT_HIGHER Return the index of the next higher element in the list, or `list.size()` if there is no such element.
public static final SortedLists.KeyAbsentBehavior	NEXT_LOWER Return the index of the next lower element in the list, or `-1` if there is no such element.

Constructor Summary

Access	Constructor and Description
private	KeyAbsentBehavior()

Method Summary

Modifier and Type	Method and Description
pack-priv abstract int	resultIndex(int higherIndex)
public static SortedLists.KeyAbsentBehavior	valueOf(String name)
public static SortedLists.KeyAbsentBehavior[]	values()

Inherited from java.lang.Enum:: clone compareTo describeConstable equals finalize getDeclaringClass hashCode name ordinal toString valueOf

Field Detail

INVERTED_INSERTION_INDEX back to summary

INVERTED_INSERTION_INDEX	back to summary
public static final SortedLists.KeyAbsentBehavior INVERTED_INSERTION_INDEX Return `~insertionIndex`, where `insertionIndex` is defined as the point at which the key would be inserted into the list: the index of the next higher element in the list, or `list.size()` if there is no such element. Note that the return value will be `>= 0` if and only if there is an element of the list that compares as equal to the key. This is equivalent to the behavior of `java.util.Collections#binarySearch(List, Object)` when the key isn't present, since `~insertionIndex` is equal to `-1 - insertionIndex`.

public static final SortedLists.KeyAbsentBehavior INVERTED_INSERTION_INDEX

Return ~insertionIndex, where insertionIndex is defined as the point at which the key would be inserted into the list: the index of the next higher element in the list, or list.size() if there is no such element.

Note that the return value will be >= 0 if and only if there is an element of the list that compares as equal to the key.

This is equivalent to the behavior of java.util.Collections#binarySearch(List, Object) when the key isn't present, since ~insertionIndex is equal to -1 - insertionIndex.

NEXT_HIGHER	back to summary
public static final SortedLists.KeyAbsentBehavior NEXT_HIGHER Return the index of the next higher element in the list, or `list.size()` if there is no such element.

NEXT_LOWER	back to summary
public static final SortedLists.KeyAbsentBehavior NEXT_LOWER Return the index of the next lower element in the list, or `-1` if there is no such element.

Constructor Detail

KeyAbsentBehavior	back to summary
private KeyAbsentBehavior()

Method Detail

resultIndex	back to summary
pack-priv abstract int resultIndex(int higherIndex)

valueOf	back to summary
public static SortedLists.KeyAbsentBehavior valueOf(String name)

values	back to summary
public static SortedLists.KeyAbsentBehavior[] values()

com.google.common.collect back to summary

pack-priv sealed Enum SortedLists.KeyPresentBehavior

Class Inheritance

extends Enum<SortedLists.KeyPresentBehavior>

java.lang.Object
java.lang.Enum
com.google.common.collect.SortedLists.KeyPresentBehavior

A specification for which index to return if the list contains at least one element that compares as equal to the key.

Field Summary

Modifier and Type	Field and Description
public static final SortedLists.KeyPresentBehavior	ANY_PRESENT Return the index of any list element that compares as equal to the key.
public static final SortedLists.KeyPresentBehavior	FIRST_AFTER Return the index of the first list element that compares as greater than the key, or `list.size()` if there is no such element.
public static final SortedLists.KeyPresentBehavior	FIRST_PRESENT Return the index of the first list element that compares as equal to the key.
public static final SortedLists.KeyPresentBehavior	LAST_BEFORE Return the index of the last list element that compares as less than the key, or `-1` if there is no such element.
public static final SortedLists.KeyPresentBehavior	LAST_PRESENT Return the index of the last list element that compares as equal to the key.

Constructor Summary

Access	Constructor and Description
private	KeyPresentBehavior()

Method Summary

Modifier and Type	Method and Description
pack-priv abstract <E extends @Nullable Object> int	resultIndex(Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex)
public static SortedLists.KeyPresentBehavior	valueOf(String name)
public static SortedLists.KeyPresentBehavior[]	values()

Inherited from java.lang.Enum:: clone compareTo describeConstable equals finalize getDeclaringClass hashCode name ordinal toString valueOf

Field Detail

ANY_PRESENT	back to summary
public static final SortedLists.KeyPresentBehavior ANY_PRESENT Return the index of any list element that compares as equal to the key. No guarantees are made as to which index is returned, if more than one element compares as equal to the key.

FIRST_AFTER	back to summary
public static final SortedLists.KeyPresentBehavior FIRST_AFTER Return the index of the first list element that compares as greater than the key, or `list.size()` if there is no such element.

FIRST_PRESENT	back to summary
public static final SortedLists.KeyPresentBehavior FIRST_PRESENT Return the index of the first list element that compares as equal to the key.

LAST_BEFORE	back to summary
public static final SortedLists.KeyPresentBehavior LAST_BEFORE Return the index of the last list element that compares as less than the key, or `-1` if there is no such element.

LAST_PRESENT	back to summary
public static final SortedLists.KeyPresentBehavior LAST_PRESENT Return the index of the last list element that compares as equal to the key.

Constructor Detail

KeyPresentBehavior	back to summary
private KeyPresentBehavior()

Method Detail

resultIndex	back to summary
pack-priv abstract <E extends @Nullable Object> int resultIndex(Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex)

valueOf	back to summary
public static SortedLists.KeyPresentBehavior valueOf(String name)

values	back to summary
public static SortedLists.KeyPresentBehavior[] values()

pack-priv final Class SortedLists

Nested and Inner Type Summary

Constructor Summary

Method Summary

Constructor Detail

Method Detail

pack-priv sealed Enum SortedLists.KeyAbsentBehavior

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv sealed Enum SortedLists.KeyPresentBehavior

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail