1 /**
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy
6  * 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, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations
14  * under the License.
15  */
16 
17 package android.app.usage;
18 
19 import android.util.LongSparseArray;
20 
21 /**
22  * An array that indexes by a long timestamp, representing milliseconds since the epoch.
23  *
24  * {@hide}
25  */
26 public class TimeSparseArray<E> extends LongSparseArray<E> {
TimeSparseArray()27     public TimeSparseArray() {
28         super();
29     }
30 
TimeSparseArray(int initialCapacity)31     public TimeSparseArray(int initialCapacity) {
32         super(initialCapacity);
33     }
34 
35     /**
36      * Finds the index of the first element whose timestamp is greater or equal to
37      * the given time.
38      *
39      * @param time The timestamp for which to search the array.
40      * @return The index of the matched element, or -1 if no such match exists.
41      */
closestIndexOnOrAfter(long time)42     public int closestIndexOnOrAfter(long time) {
43         // This is essentially a binary search, except that if no match is found
44         // the closest index is returned.
45         final int size = size();
46         int lo = 0;
47         int hi = size - 1;
48         int mid = -1;
49         long key = -1;
50         while (lo <= hi) {
51             mid = lo + ((hi - lo) / 2);
52             key = keyAt(mid);
53 
54             if (time > key) {
55                 lo = mid + 1;
56             } else if (time < key) {
57                 hi = mid - 1;
58             } else {
59                 return mid;
60             }
61         }
62 
63         if (time < key) {
64             return mid;
65         } else if (time > key && lo < size) {
66             return lo;
67         } else {
68             return -1;
69         }
70     }
71 
72     /**
73      * Finds the index of the first element whose timestamp is less than or equal to
74      * the given time.
75      *
76      * @param time The timestamp for which to search the array.
77      * @return The index of the matched element, or -1 if no such match exists.
78      */
closestIndexOnOrBefore(long time)79     public int closestIndexOnOrBefore(long time) {
80         final int index = closestIndexOnOrAfter(time);
81         if (index < 0) {
82             // Everything is larger, so we use the last element, or -1 if the list is empty.
83             return size() - 1;
84         }
85 
86         if (keyAt(index) == time) {
87             return index;
88         }
89         return index - 1;
90     }
91 }
92