1 /*
2 * Copyright (C) 2010 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkNotNull;
18
19 import com.google.common.annotations.Beta;
20 import com.google.common.annotations.GwtCompatible;
21 import com.google.common.base.Function;
22 import java.util.Collections;
23 import java.util.Comparator;
24 import java.util.List;
25 import java.util.RandomAccess;
26 import org.checkerframework.checker.nullness.qual.Nullable;
27
28 /**
29 * Static methods pertaining to sorted {@link List} instances.
30 *
31 * <p>In this documentation, the terms <i>greatest</i>, <i>greater</i>, <i>least</i>, and
32 * <i>lesser</i> are considered to refer to the comparator on the elements, and the terms
33 * <i>first</i> and <i>last</i> are considered to refer to the elements' ordering in a list.
34 *
35 * @author Louis Wasserman
36 */
37 @GwtCompatible
38 @Beta
39 final class SortedLists {
40 private SortedLists() {}
41
42 /**
43 * A specification for which index to return if the list contains at least one element that
44 * compares as equal to the key.
45 */
46 enum KeyPresentBehavior {
47 /**
48 * Return the index of any list element that compares as equal to the key. No guarantees are
49 * made as to which index is returned, if more than one element compares as equal to the key.
50 */
51 ANY_PRESENT {
52 @Override
53 <E> int resultIndex(
54 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
55 return foundIndex;
56 }
57 },
58 /** Return the index of the last list element that compares as equal to the key. */
59 LAST_PRESENT {
60 @Override
61 <E> int resultIndex(
62 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
63 // Of course, we have to use binary search to find the precise
64 // breakpoint...
65 int lower = foundIndex;
66 int upper = list.size() - 1;
67 // Everything between lower and upper inclusive compares at >= 0.
68 while (lower < upper) {
69 int middle = (lower + upper + 1) >>> 1;
70 int c = comparator.compare(list.get(middle), key);
71 if (c > 0) {
72 upper = middle - 1;
73 } else { // c == 0
74 lower = middle;
75 }
76 }
77 return lower;
78 }
79 },
80 /** Return the index of the first list element that compares as equal to the key. */
81 FIRST_PRESENT {
82 @Override
83 <E> int resultIndex(
84 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
85 // Of course, we have to use binary search to find the precise
86 // breakpoint...
87 int lower = 0;
88 int upper = foundIndex;
89 // Of course, we have to use binary search to find the precise breakpoint...
90 // Everything between lower and upper inclusive compares at <= 0.
91 while (lower < upper) {
92 int middle = (lower + upper) >>> 1;
93 int c = comparator.compare(list.get(middle), key);
94 if (c < 0) {
95 lower = middle + 1;
96 } else { // c == 0
97 upper = middle;
98 }
99 }
100 return lower;
101 }
102 },
103 /**
104 * Return the index of the first list element that compares as greater than the key, or {@code
105 * list.size()} if there is no such element.
106 */
107 FIRST_AFTER {
108 @Override
109 public <E> int resultIndex(
110 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
111 return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
112 }
113 },
114 /**
115 * Return the index of the last list element that compares as less than the key, or {@code -1}
116 * if there is no such element.
117 */
118 LAST_BEFORE {
119 @Override
120 public <E> int resultIndex(
121 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
122 return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
123 }
124 };
125
126 abstract <E> int resultIndex(
127 Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex);
128 }
129
130 /**
131 * A specification for which index to return if the list contains no elements that compare as
132 * equal to the key.
133 */
134 enum KeyAbsentBehavior {
135 /**
136 * Return the index of the next lower element in the list, or {@code -1} if there is no such
137 * element.
138 */
139 NEXT_LOWER {
140 @Override
141 int resultIndex(int higherIndex) {
142 return higherIndex - 1;
143 }
144 },
145 /**
146 * Return the index of the next higher element in the list, or {@code list.size()} if there is
147 * no such element.
148 */
149 NEXT_HIGHER {
150 @Override
151 public int resultIndex(int higherIndex) {
152 return higherIndex;
153 }
154 },
155 /**
156 * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at which
157 * the key would be inserted into the list: the index of the next higher element in the list, or
158 * {@code list.size()} if there is no such element.
159 *
160 * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
161 * list that compares as equal to the key.
162 *
163 * <p>This is equivalent to the behavior of {@link java.util.Collections#binarySearch(List,
164 * Object)} when the key isn't present, since {@code ~insertionIndex} is equal to {@code -1 -
165 * insertionIndex}.
166 */
167 INVERTED_INSERTION_INDEX {
168 @Override
169 public int resultIndex(int higherIndex) {
170 return ~higherIndex;
171 }
172 };
173
174 abstract int resultIndex(int higherIndex);
175 }
176
177 /**
178 * Searches the specified naturally ordered list for the specified object using the binary search
179 * algorithm.
180 *
181 * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
182 * KeyAbsentBehavior)} using {@link Ordering#natural}.
183 */
184 public static <E extends Comparable> int binarySearch(
185 List<? extends E> list,
186 E e,
187 KeyPresentBehavior presentBehavior,
188 KeyAbsentBehavior absentBehavior) {
189 checkNotNull(e);
190 return binarySearch(list, e, Ordering.natural(), presentBehavior, absentBehavior);
191 }
192
193 /**
194 * Binary searches the list for the specified key, using the specified key function.
195 *
196 * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
197 * KeyAbsentBehavior)} using {@link Ordering#natural}.
198 */
199 public static <E, K extends Comparable> int binarySearch(
200 List<E> list,
201 Function<? super E, K> keyFunction,
202 @Nullable K key,
203 KeyPresentBehavior presentBehavior,
204 KeyAbsentBehavior absentBehavior) {
205 return binarySearch(
206 list, keyFunction, key, Ordering.natural(), presentBehavior, absentBehavior);
207 }
208
209 /**
210 * Binary searches the list for the specified key, using the specified key function.
211 *
212 * <p>Equivalent to {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior,
213 * KeyAbsentBehavior)} using {@link Lists#transform(List, Function) Lists.transform(list,
214 * keyFunction)}.
215 */
216 public static <E, K> int binarySearch(
217 List<E> list,
218 Function<? super E, K> keyFunction,
219 @Nullable K key,
220 Comparator<? super K> keyComparator,
221 KeyPresentBehavior presentBehavior,
222 KeyAbsentBehavior absentBehavior) {
223 return binarySearch(
224 Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
225 }
226
227 /**
228 * Searches the specified list for the specified object using the binary search algorithm. The
229 * list must be sorted into ascending order according to the specified comparator (as by the
230 * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior to
231 * making this call. If it is not sorted, the results are undefined.
232 *
233 * <p>If there are elements in the list which compare as equal to the key, the choice of {@link
234 * KeyPresentBehavior} decides which index is returned. If no elements compare as equal to the
235 * key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
236 *
237 * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
238 * access to each list element.
239 *
240 * @param list the list to be searched.
241 * @param key the value to be searched for.
242 * @param comparator the comparator by which the list is ordered.
243 * @param presentBehavior the specification for what to do if at least one element of the list
244 * compares as equal to the key.
245 * @param absentBehavior the specification for what to do if no elements of the list compare as
246 * equal to the key.
247 * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
248 * otherwise the index determined by the {@code KeyAbsentBehavior}.
249 */
250 public static <E> int binarySearch(
251 List<? extends E> list,
252 @Nullable E key,
253 Comparator<? super E> comparator,
254 KeyPresentBehavior presentBehavior,
255 KeyAbsentBehavior absentBehavior) {
256 checkNotNull(comparator);
257 checkNotNull(list);
258 checkNotNull(presentBehavior);
259 checkNotNull(absentBehavior);
260 if (!(list instanceof RandomAccess)) {
261 list = Lists.newArrayList(list);
262 }
263 // TODO(lowasser): benchmark when it's best to do a linear search
264
265 int lower = 0;
266 int upper = list.size() - 1;
267
268 while (lower <= upper) {
269 int middle = (lower + upper) >>> 1;
270 int c = comparator.compare(key, list.get(middle));
271 if (c < 0) {
272 upper = middle - 1;
273 } else if (c > 0) {
274 lower = middle + 1;
275 } else {
276 return lower
277 + presentBehavior.resultIndex(
278 comparator, key, list.subList(lower, upper + 1), middle - lower);
279 }
280 }
281 return absentBehavior.resultIndex(lower);
282 }
283 }