View Javadoc
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 javax.annotation.Nullable;
27  
28  /**
29   * Static methods pertaining to sorted {@link List} instances.
30   *
31   * 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
34   * list.
35   *
36   * @author Louis Wasserman
37   */
38  @GwtCompatible
39  @Beta 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     */ enum KeyPresentBehavior {
46      /**
47       * Return the index of any list element that compares as equal to the key. No guarantees are
48       * made as to which index is returned, if more than one element compares as equal to the key.
49       */
50      ANY_PRESENT {
51        @Override
52        <E> int resultIndex(
53            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
54          return foundIndex;
55        }
56      },
57      /**
58       * Return the index of the last list element that compares as equal to the key.
59       */
60      LAST_PRESENT {
61        @Override
62        <E> int resultIndex(
63            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
64          // Of course, we have to use binary search to find the precise
65          // breakpoint...
66          int lower = foundIndex;
67          int upper = list.size() - 1;
68          // Everything between lower and upper inclusive compares at >= 0.
69          while (lower < upper) {
70            int middle = (lower + upper + 1) >>> 1;
71            int c = comparator.compare(list.get(middle), key);
72            if (c > 0) {
73              upper = middle - 1;
74            } else { // c == 0
75              lower = middle;
76            }
77          }
78          return lower;
79        }
80      },
81      /**
82       * Return the index of the first list element that compares as equal to the key.
83       */
84      FIRST_PRESENT {
85        @Override
86        <E> int resultIndex(
87            Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
88          // Of course, we have to use binary search to find the precise
89          // breakpoint...
90          int lower = 0;
91          int upper = foundIndex;
92          // Of course, we have to use binary search to find the precise breakpoint...
93          // Everything between lower and upper inclusive compares at <= 0.
94          while (lower < upper) {
95            int middle = (lower + upper) >>> 1;
96            int c = comparator.compare(list.get(middle), key);
97            if (c < 0) {
98              lower = middle + 1;
99            } else { // c == 0
100             upper = middle;
101           }
102         }
103         return lower;
104       }
105     },
106     /**
107      * Return the index of the first list element that compares as greater than the key, or {@code
108      * list.size()} if there is no such element.
109      */
110     FIRST_AFTER {
111       @Override
112       public <E> int resultIndex(
113           Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
114         return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
115       }
116     },
117     /**
118      * Return the index of the last list element that compares as less than the key, or {@code -1}
119      * if there is no such element.
120      */
121     LAST_BEFORE {
122       @Override
123       public <E> int resultIndex(
124           Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
125         return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
126       }
127     };
128 
129     abstract <E> int resultIndex(
130         Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex);
131   }
132 
133   /**
134    * A specification for which index to return if the list contains no elements that compare as
135    * equal to the key.
136    */ enum KeyAbsentBehavior {
137     /**
138      * Return the index of the next lower element in the list, or {@code -1} if there is no such
139      * element.
140      */
141     NEXT_LOWER {
142       @Override
143       int resultIndex(int higherIndex) {
144         return higherIndex - 1;
145       }
146     },
147     /**
148      * Return the index of the next higher element in the list, or {@code list.size()} if there is
149      * no such element.
150      */
151     NEXT_HIGHER {
152       @Override
153       public int resultIndex(int higherIndex) {
154         return higherIndex;
155       }
156     },
157     /**
158      * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at
159      * which the key would be inserted into the list: the index of the next higher element in the
160      * list, or {@code list.size()} if there is no such element.
161      *
162      * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
163      * list that compares as equal to the key.
164      *
165      * <p>This is equivalent to the behavior of
166      * {@link java.util.Collections#binarySearch(List, Object)} when the key isn't present, since
167      * {@code ~insertionIndex} is equal to {@code -1 - insertionIndex}.
168      */
169     INVERTED_INSERTION_INDEX {
170       @Override
171       public int resultIndex(int higherIndex) {
172         return ~higherIndex;
173       }
174     };
175 
176     abstract int resultIndex(int higherIndex);
177   }
178 
179   /**
180    * Searches the specified naturally ordered list for the specified object using the binary search
181    * algorithm.
182    *
183    * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
184    * KeyAbsentBehavior)} using {@link Ordering#natural}.
185    */
186   public static <E extends Comparable> int binarySearch(
187       List<? extends E> list,
188       E e,
189       KeyPresentBehavior presentBehavior,
190       KeyAbsentBehavior absentBehavior) {
191     checkNotNull(e);
192     return binarySearch(list, e, Ordering.natural(), presentBehavior, absentBehavior);
193   }
194 
195   /**
196    * Binary searches the list for the specified key, using the specified key function.
197    *
198    * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
199    * KeyAbsentBehavior)} using {@link Ordering#natural}.
200    */
201   public static <E, K extends Comparable> int binarySearch(
202       List<E> list,
203       Function<? super E, K> keyFunction,
204       @Nullable K key,
205       KeyPresentBehavior presentBehavior,
206       KeyAbsentBehavior absentBehavior) {
207     return binarySearch(
208         list, keyFunction, key, Ordering.natural(), presentBehavior, absentBehavior);
209   }
210 
211   /**
212    * Binary searches the list for the specified key, using the specified key function.
213    *
214    * <p>Equivalent to
215    * {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior, KeyAbsentBehavior)} using
216    * {@link Lists#transform(List, Function) Lists.transform(list, keyFunction)}.
217    */
218   public static <E, K> int binarySearch(
219       List<E> list,
220       Function<? super E, K> keyFunction,
221       @Nullable K key,
222       Comparator<? super K> keyComparator,
223       KeyPresentBehavior presentBehavior,
224       KeyAbsentBehavior absentBehavior) {
225     return binarySearch(
226         Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
227   }
228 
229   /**
230    * Searches the specified list for the specified object using the binary search algorithm. The
231    * list must be sorted into ascending order according to the specified comparator (as by the
232    * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior
233    * to making this call. If it is not sorted, the results are undefined.
234    *
235    * <p>If there are elements in the list which compare as equal to the key, the choice of
236    * {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to
237    * the key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
238    *
239    * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
240    * access to each list element.
241    *
242    * @param list the list to be searched.
243    * @param key the value to be searched for.
244    * @param comparator the comparator by which the list is ordered.
245    * @param presentBehavior the specification for what to do if at least one element of the list
246    *        compares as equal to the key.
247    * @param absentBehavior the specification for what to do if no elements of the list compare as
248    *        equal to the key.
249    * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
250    *         otherwise the index determined by the {@code KeyAbsentBehavior}.
251    */
252   public static <E> int binarySearch(
253       List<? extends E> list,
254       @Nullable E key,
255       Comparator<? super E> comparator,
256       KeyPresentBehavior presentBehavior,
257       KeyAbsentBehavior absentBehavior) {
258     checkNotNull(comparator);
259     checkNotNull(list);
260     checkNotNull(presentBehavior);
261     checkNotNull(absentBehavior);
262     if (!(list instanceof RandomAccess)) {
263       list = Lists.newArrayList(list);
264     }
265     // TODO(lowasser): benchmark when it's best to do a linear search
266 
267     int lower = 0;
268     int upper = list.size() - 1;
269 
270     while (lower <= upper) {
271       int middle = (lower + upper) >>> 1;
272       int c = comparator.compare(key, list.get(middle));
273       if (c < 0) {
274         upper = middle - 1;
275       } else if (c > 0) {
276         lower = middle + 1;
277       } else {
278         return lower
279             + presentBehavior.resultIndex(
280                 comparator, key, list.subList(lower, upper + 1), middle - lower);
281       }
282     }
283     return absentBehavior.resultIndex(lower);
284   }
285 }