1 /*
2  * Copyright 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.pump.util;
18 
19 import androidx.annotation.AnyThread;
20 import androidx.annotation.NonNull;
21 import androidx.annotation.Nullable;
22 
23 import java.util.List;
24 
25 @AnyThread
26 public final class Collections {
Collections()27     private Collections() { }
28 
29     @FunctionalInterface
30     public interface LongKeyRetriever<T> {
getKey(@onNull T value)31         long getKey(@NonNull T value);
32     }
33 
find(@onNull List<T> list, long key, @NonNull LongKeyRetriever<T> keyRetriever)34     public static @Nullable <T> T find(@NonNull List<T> list, long key,
35             @NonNull LongKeyRetriever<T> keyRetriever) {
36         int index = binarySearch(list, key, keyRetriever);
37         if (index >= 0) {
38             return list.get(index);
39         }
40         return null;
41     }
42 
binarySearch(@onNull List<T> list, long key, @NonNull LongKeyRetriever<T> keyRetriever)43     public static <T> int binarySearch(@NonNull List<T> list, long key,
44             @NonNull LongKeyRetriever<T> keyRetriever) {
45         int lo = 0;
46         int hi = list.size() - 1;
47 
48         while (lo <= hi) {
49             int mid = lo + (hi - lo) / 2;
50             long midKey = keyRetriever.getKey(list.get(mid));
51 
52             if (midKey < key) {
53                 lo = mid + 1;
54             } else if (midKey > key) {
55                 hi = mid - 1;
56             } else {
57                 return mid;
58             }
59         }
60         return ~lo;
61     }
62 }
63