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 import android.util.Slog;
21 
22 /**
23  * An array that indexes by a long timestamp, representing milliseconds since the epoch.
24  *
25  * {@hide}
26  */
27 public class TimeSparseArray<E> extends LongSparseArray<E> {
28     private static final String TAG = TimeSparseArray.class.getSimpleName();
29 
30     private boolean mWtfReported;
31 
TimeSparseArray()32     public TimeSparseArray() {
33         super();
34     }
35 
36     /**
37      * Finds the index of the first element whose timestamp is greater or equal to
38      * the given time.
39      *
40      * @param time The timestamp for which to search the array.
41      * @return The index of the matched element, or -1 if no such match exists.
42      */
closestIndexOnOrAfter(long time)43     public int closestIndexOnOrAfter(long time) {
44         // This is essentially a binary search, except that if no match is found
45         // the closest index is returned.
46         final int size = size();
47         int lo = 0;
48         int hi = size - 1;
49         int mid = -1;
50         long key = -1;
51         while (lo <= hi) {
52             mid = lo + ((hi - lo) / 2);
53             key = keyAt(mid);
54 
55             if (time > key) {
56                 lo = mid + 1;
57             } else if (time < key) {
58                 hi = mid - 1;
59             } else {
60                 return mid;
61             }
62         }
63 
64         if (time < key) {
65             return mid;
66         } else if (time > key && lo < size) {
67             return lo;
68         } else {
69             return -1;
70         }
71     }
72 
73     /**
74      * {@inheritDoc}
75      *
76      * <p> As this container is being used only to keep {@link android.util.AtomicFile files},
77      * there should not be any collisions. Reporting a {@link Slog#wtf(String, String)} in case that
78      * happens, as that will lead to one whole file being dropped.
79      */
80     @Override
put(long key, E value)81     public void put(long key, E value) {
82         if (indexOfKey(key) >= 0) {
83             if (!mWtfReported) {
84                 Slog.wtf(TAG, "Overwriting value " + get(key) + " by " + value);
85                 mWtfReported = true;
86             }
87         }
88         super.put(key, value);
89     }
90 
91     /**
92      * Finds the index of the first element whose timestamp is less than or equal to
93      * the given time.
94      *
95      * @param time The timestamp for which to search the array.
96      * @return The index of the matched element, or -1 if no such match exists.
97      */
closestIndexOnOrBefore(long time)98     public int closestIndexOnOrBefore(long time) {
99         final int index = closestIndexOnOrAfter(time);
100         if (index < 0) {
101             // Everything is larger, so we use the last element, or -1 if the list is empty.
102             return size() - 1;
103         }
104 
105         if (keyAt(index) == time) {
106             return index;
107         }
108         return index - 1;
109     }
110 }
111